# 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₁, N₂, ..., N_K, maka banyak edgenya adalah N₁-1, N₂-1, ..., N_K-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


Contoh pewarnaan bracket tidak valid


<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_i ≤ l_i ≤ t_i
</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