---
# System prepended metadata

title: Mindstorming Session

---

# Mindstorming Session

## 5 Oktober 2024

### Soal 1 - Counting Connected Component

#### Abridged Problem Statement

Diberikan sebuah grid berukuran $N \times M$. Setiap petak bisa berwarna hitam atau putih. Berlaku hal berikut : 

- Untuk setiap petak hitam $a$ dan $b$, terdapat **maksimal** satu lintasan untuk pergi dari $a$ menuju $b$ dengan hanya bergerak ke kiri, kanan, atas, atau bawah tanpa melewati petak putih

- Apabila $a$ dan $b$ terhubung oleh sebuah lintasan, maka petak $a$ dan $b$ terhubung jadi satu connected component. Sebaliknya, jika tidak ada lintasan, mereka berada di connected component berbeda

#### Objective

Diberikan $Q$ buah query. Setiap query akan diberikan 4 buah bilangan $(atas, kiri, bawah, kanan)$. Kamu diminta untuk menghitung **banyaknya connected component berbeda** dari sub-grid yang dibatasi oleh $(atas, kiri, bawah, kanan)$ pada query tersebut

#### Constraints

- $1 ≤ N, M ≤ 2000$
- $1 ≤ Q ≤ 200\ 000$
- Untuk setiap petak hitam $a$ dan $b$ hanya terdapat **maksimal** satu lintasan berbeda untuk pergi dari $a$ menuju $b$

<details>
    <summary>Hint 1</summary>
    Setiap connected component membentuk sebuah tree
</details>

<details>
    <summary>Hint 2</summary>
    Jika ada N node dalam sebuah tree, banyak edge adalah N-1
</details>

<details>
    <summary>Hint 3</summary>
    Jika terdapat K buah tree yang berukuran N<sub>1</sub>, N<sub>2</sub>, ..., N<sub>K</sub>, maka banyak edgenya adalah N<sub>1</sub>-1, N<sub>2</sub>-1, ..., N<sub>K</sub>-1
<br>
Dari persamaan itu, kita tahu banyak node dikurangi banyak edge akan menghasilkan banyaknya tree
</details>

<details>
    <summary>Hint 4</summary>
    Bagaimana kita menghitung banyak node dan edge dalam sub-grid dengan cukup cepat?
</details>

<details>
    <summary>Source Soal</summary>
    https://atcoder.jp/contests/agc015/tasks/agc015_c
</details>

---

### Soal 2 - Membuka Pintu

#### Abridged Problem Statement

Terdapat $N$ buah pintu dinomori dari $1, 2, \ldots, N$. Setiap pintu bisa ada dalam keadaan **terbuka** maupun **terkunci**. Selain itu terdapat $M$ buah tombol. Tombol ke $i$ dapat mengubah keadaan dari pintu pintu $D_{i, 1}, D_{i, 2}, \ldots, D_{i, k}$

Diketahui berlaku bahwa **setiap pintu terhubung oleh TEPAT 2 buah tombol**

#### Objective

Untuk suatu susunan pintu dan tombol tersebut, tentukan apakah kamu bisa membuat semua pintu berada dalam keadaan **terbuka** atau tidak mungkin

#### Constraints
- $2 ≤ N ≤ 10^5$
- $2 ≤ M ≤ 10^5$
- Setiap pintu terhubung oleh **tepat** 2 buah tombol

<details>
    <summary>Hint 1</summary>
    Perhatikan kondisi dimana setiap pintu terhubung oleh tepat 2 buah tombol
</details>

<details>
    <summary>Hint 2</summary>
    Modelkan susunan diatas menjadi sebuah graph
</details>

<details>
    <summary>Hint 3</summary>
    Anggaplah pintu sebagai edge dan tombol sebagai node. Sekarang, perhatikan fakta bahwa menekan tombol 2 kali sama dengan tidak menekan tombol. Sekarang coba tandai node tombol dengan 1 apabila tombol itu ditekan dan 0 jika tidak ditekan
</details>

<details>
    <summary>Hint 4</summary>
    Apabila suatu pintu berada dalam keadaan <b>terbuka</b>, maka 2 tombol yang menghubungkannya harus memiliki tanda yang <b>sama</b> (supaya pintu tetap terbuka). Sebaliknya, apabila pintu dalam keadaan <b>terkunci</b>, maka 2 tombol yang menghubungkannya harus memiliki tanda yang <b>berbeda</b> (agar pintu menjadi terbuka)
</details>

<details>
    <summary>Source Soal</summary>
    https://codeforces.com/problemset/problem/776/D
</details>

---

### Soal 3 - Mewarnai Bracket

#### Abridged Problem Statement

Diberikan sebuah string _bracket_ $S$ yang terdiri dari kurung buka `(` dan kurung tutup `)` dijamin susunan tersebut merupakan susunan _balanced parenthesis_ (setiap kurung buka memiliki pasangan kurung tutup)

Kamu diminta untuk mewarnai setiap karakter pada string $S$ dengan ketentuan sebagai berikut : 
- Setiap karakter memiliki warna **merah**, **biru**, atau **tidak diwarnai**
- Apabila suatu karakter diwarnai, maka **pasangan kurungnya** harus tidak boleh diwarnai
- Apabila suatu karakter tidak diwarnai, maka **pasangan kurungnya** harus diwarnai
- Tidak boleh ada karakter bersebelahan yang memiliki warna yang sama

#### Objective

Tentukan banyak cara pewarnaan berbeda yang memenuhi syarat diatas di modulo $10^9 + 7$

#### Constraints

- $2 ≤ |S| ≤ 700$
- Dijamin susunan bracket pada $S$ merupakan _balanced parenthesis_

Contoh pewarnaan bracket valid

![Screenshot 2024-10-05 at 08.48.16](https://hackmd.io/_uploads/r1hyiGRRA.png)

Contoh pewarnaan bracket tidak valid

![Screenshot 2024-10-05 at 08.49.05](https://hackmd.io/_uploads/Sy2GifCRC.png)

<details>
    <summary>Hint 1</summary>
    Bagaimana kalau kita mulai dulu dari mencari tahu posisi dari pasangan kurung dari setiap karakter?
</details>

<details>
    <summary>Hint 2</summary>
    Saat kita sedang meng-consider untuk mewarnai salah satu karakter, maka warna dari pasangan karakter tersebut akan tergantung dari warna karakter tersebut
    
Sekarang, setelah kita mewarnainya, maka string ini akan terbagi menjadi 2 sub-problem berbeda. Banyak pewarnaan masing masing subproblem akan menjadi dependen (saling tergantung)
</details>

<details>
    <summary>Hint 3</summary>
    Karena string bisa dibagi jadi subproblem, maka kita bisa mulai dengan $dp$ dengan sejumlah state. Kira kira state apa saja yang perlu disimpan? Ingat bahwa karakter bersebelahan tidak boleh memiliki warna yang sama
</details>

<details>
    <summary>Hint 4</summary>
    Coba gunakan 4 state berikut : 
    <ul>
        <li>Batas kiri dan kanan dari string bracket sekarang</li>
        <li>Warna dari karakter di sebelah batas kiri dan batas kanan dari batas kiri dan kanan saat ini</li>
    </ul>
</details>

<details>
    <summary>Source Soal</summary>
    https://codeforces.com/problemset/problem/149/D
</details>

---

### Soal 4 - Mencari Median dalam Sub-rectangle

#### Abridged Problem Statement

Diberikan sebuah grid $G$ berukuran $N \times M$. Diberikan juga $Q$ buah query. Setiap query akan diberikan $(atas, kiri, bawah, kanan)$. Kamu diminta untuk menentukan **median** dari sub-grid yang dibatasi oleh $(atas, kiri, bawah, kanan)$ dari query tersebut

Definisi median
Jika terdapat $K$ buah elemen, maka median adalah elemen ke $\lfloor{\frac{K}{2}}\rfloor$ terkecil diantara elemen-elemen tersebut

#### Objective

Jawablah query tersebut dengan median dari angka-angka di dalam sub-grid yang ditanyakan

#### Constraints

- $1 ≤ N, M ≤ 100$
- $1 ≤ G_{i,j} ≤ 500$
- $1 ≤ Q ≤ 10^5$

<details>
    <summary>Hint 1</summary>
    Suatu bilangan bisa menjadi median dari sebuah himpunan berisi K buah elemen apabila terdapat setidaknya K/2 elemen yang memiliki nilai lebih kecil daripada bilangan tersebut
    
Sebaliknya, apabila banyak elemen yang lebih kecil tidak mencapai K/2, maka bilangan tersebut tidak mungkin menjadi median
</details>

<details>
    <summary>Hint 2</summary>
    Perhatikan bahwa setiap angka pada grid hanya bisa bernilai dari 1 sampai 500
</details>

<details>
    <summary>Hint 3</summary>
    Untuk suatu bilangan bulat x pada grid, bagaimana cara kita mengetahui ada berapa banyak bilangan yang ≤ x?
</details>

<details>
    <summary>Hint 4</summary>
    Mulailah berpikir untuk menghitung frekuensi dari setiap angka pada grid
</details>

<details>
    <summary>Source Soal</summary>
    https://codeforces.com/gym/101778/problem/F
</details>

---

### Soal 5 - Balok

#### Abridged Problem Statement

Diberikan $N$ buah balok dinomori dari $1, 2, \ldots, N$. Balok ke $i$ memiliki dimensi panjang, lebar, dan tinggi $(p_i, l_i, t_i)$

Sebuah balok $x$ bisa dimasukan ke dalam balok $y$ jika kita bisa merotasi balok $x$ sedemikian sehingga $p_x < p_y$, $l_x < l_y$, dan $t_x < t_y$

#### Objective 

Tentukanlah apakah ada sebuah balok yang bisa dimasukkan ke dalam balok yang lainnya

#### Constraints

- $1 ≤ N ≤ 200\ 000$
- $1 ≤ p_i, l_i, t_i ≤ 10^9$

<details>
    <summary>Hint 1</summary>
    Karena balok ini bisa dirotasi, maka kita selalu bisa mengatur dimensi sebuah balok sedemikian sehingga p<sub>i</sub> ≤ l<sub>i</sub> ≤ t<sub>i</sub>
</details>

<details>
    <summary>Hint 2</summary>
    Kita coba dulu mengurutkan balok berdasarkan nilai p dari kecil ke besar. Jika ada balok yang memiliki p yang sama, kita urutkan berdasarkan l dari besar ke kecil
    
Dengan demikian sudah pasti berlaku hal berikut : 
Untuk suatu balok i dan balok j dimana i < j, maka untuk memeriksa apakah balok i bisa masuk ke dalam balok j, kita hanya perlu melihat dari dua dimensi lebar dan tingginya saja karena dimensi pertama sudah terurut
</details>
    
<details>
    <summary>Hint 3</summary>    
    Untuk suatu balok yang memiliki lebar l, maka sebenarnya kita bisa menjawab pertanyaan berikut : 
    
Dari semua balok lain yang memiliki l lebih kecil, maka akan selalu optimal jika kita memilih nilai t terkecil yang mungkin 
</details>
    
<details>
    <summary>Hint 4</summary>    
    Bagaimana kita mencari suatu panjang minimal dari balok balok yang memiliki lebar lebih kecil?
</details>
    
<details>
    <summary>Source Soal</summary>    
    https://atcoder.jp/contests/abc309/tasks/abc309_f
</details>
    
---
    
### Soal 6
    
