# Mindstorming Soal DP 1400-1800
## Sabtu 25 Jan 2025

### Soal 1

**Abridge Problem Statement**

Terdapat 2 buah *microwave* untuk menghangatkan makanan. Terdapat juga $N$ buah makanan. Makanan ke $i$ membutuhkan $T_i$ detik untuk dihangatkan. Satu buah microwave hanya bisa menghangatkan paling banyak 1 buah makanan pada suatu waktu

**Objective**

Tentukan waktu **minimal** untuk menghangatkan semua makanan tersebut

**Constraint**

- $1 ≤ N ≤ 100$
- $1 ≤ T_i ≤ 1000$

**Sample Input**

<pre>
5
8 3 7 2 5
</pre>

**Sample Output**

<pre>
13
</pre>

**Solution**

<details>
<summary>Hint 1</summary>
Selisih total waktu yang dibutuhkan microwave 1 dan microwave 2 untuk menghangatkan makanan yang dimasukkan ke dalamnya harus seminimal mungkin
</details>

<details>
<summary>Hint 2</summary>
Mulailah dari berpikir seperti berikut : Untuk sebuah makanan $i$, microwave mana yang akan digunakan untuk menghangatkan makanan ini?
</details>

<details>
<summary>Hint 3</summary>
Gimana kalo kita simpen total waktu semua makanan yang dimasukkan di sebuah microwave sebagai state DP?
</details>

<details>
<summary>Hint 4</summary>
Jika kita tau item mana yang sedang diconsider serta total semua waktu di salah satu microwave, maka kita pasti bisa tau total waktu di microwave satunya lagi. Dengan kata lain, kita cukup simpen salah satu total waktu microwave sebagai state DP
</details>

**Source Soal**

<details>
<summary>Link</summary>
<a href="https://portal.kokocoder.com/problems/76eb590a-ece8-41a0-a7ca-c847047247b0" target="_blank">Portal Roadmap Yellow 1-9 : Cooking</a>
</details>

---

### Soal 2

**Abridged Problem Statement**

Terdapat sebuah oven dan $N$ buah makanan. Diketahui oven tersebut dapat menampung makanan sebanyak tak hingga

Setiap makanan memiliki **waktu ideal** untuk dimasukkan ke dalam oven. Makanan ke $i$ idealnya dimasukkan ke dalam oven pada menit ke $t_i$

Pada suatu menit $x$, kamu hanya bisa memasukkan **maksimal** satu makanan ke dalam oven. Apabila kamu memasukkan makanan pada menit ke $x$, nilai **kelezatannya akan berkurang sebesar $|x-t_i|$**

**Objective**

Kamu diminta untuk mencari strategi sedemikian agar **jumlah** dari nilai kelezatan makanan yang berkurang bernilai **seminimal mungkin** setelah memasukkan **semua** makanan ke dalam oven

**Constraint**

- $1 ≤ N ≤ 200$
- $1 ≤ t_i ≤ N$

**Sample Input**

<pre>
6
4 2 4 4 5 2
</pre>

**Sample Output**

<pre>
4
</pre>

**Solution**

<details>
<summary>Hint 1</summary>
Pada suatu waktu, kita punya decision untuk memilih mau memasukkan makanan pada waktu tersebut atau tidak
</details>

<details>
<summary>Hint 2</summary>
Pada suatu waktu, akan optimal jika kita memilih memprioritaskan makanan yang memiliki $t_i$ lebih kecil daripada yang lebih besar, karena pada akhirnya semua makanan harus dimasukkan ke dalam oven
</details>

<details>
<summary>Hint 3</summary>
Total waktu yang dibutuhkan untuk memasukkan makanan ke dalam oven tidak mungkin melebihi $2N$, maka kita bisa menjadikannya sebagai state DP
</details>

**Source Soal**

<details>
<summary>Link</summary>
<a href="https://portal.kokocoder.com/problems/07249ac7-3af1-475a-be25-0cf6043b69d2" target="_blank">Portal Roadmap Yellow 1-9 : Chef Monocarp</a>
</details>

---

### Soal 3

**Abridged Problem Statement**

Diberikan grid berukuran $2 \times N$. Setiap petak pada grid bisa diberi salah satu warna dari **hitam** atau **putih**

Sebuah *connected component* didefinisikan sebagai sekumpulan petak yang bersebelahan dan memiliki warna sama (disini, bersebelahan maksudnya adalah bersebelahan di kiri/kanan/atas/bawah dengan petak lainnya)

**Objective**

Tentukan banyak **cara pewarnaan** yang valid apabila kita harus membentuk **tepat** sebanyak $M$ buah *connected component* berbeda

**Constraint**

- $1 ≤ N ≤ 1000$
- $1 ≤ M ≤ 2N$

**Contoh Input**

<pre>
3 4
</pre>

**Contoh Output**

<pre>
12
</pre>

Salah satu cara pewarnaan yang valid


**Solution**

<details>
<summary>Hint 1</summary>
Apabila kita mulai mewarnai dari kanan ke kiri, penambahan jumlah connected component baru hanya akan dipengaruhi dari 2 petak di kolom sebelah kanan dari kolom yang mau kita warnai sekarang
</details>

<details>
<summary>Hint 2</summary>
Hanya akan ada 16 kemungkinan penambahan jumlah connected component yang mungkin. Kita bisa simpan warna dari 2 kolom di sebelah kanan dan jumlah connected component yang sudah terbentuk pada saat ini
</details>

<details>
<summary>Hint 3</summary>
Kita bisa menyimpan state DP nya : kolom yang saat ini sedang mau kita warnai, banyak connected component sejauh ini, dan warna dari 2 petak sebelumnya yang kita warnai
</details>

**Source Soal**

<details>
<summary>Link</summary>
<a href="https://portal.kokocoder.com/problems/5336090a-3864-42e0-9b95-26e3433521fc" target="_blank">Portal Roadmap Yellow 1-9 : Bicolorings</a>
</details>

---

### Soal 4

**Abridged Problem Statement**

Diberikan $N$ buah pohon dan $M$ buah jenis warna berbeda. Setiap pohon memiliki warna $c_i$ (Jika $c_i = 0$ berarti pohon tersebut belum diwarnai, jika $c_i > 0$, berarti pohon tersebut berwarna $c_i$). Apabila kita mau mewarnai pohon $i$ dengan warna $j$, maka dibutuhkan biaya $p_{i, j}$

Definisikan sebuah **segmen** adalah sekumpulan pohon bersebelahan yang memiliki warna yang sama dan tergabung menjadi satu. Misal susunan pohon dengan warna $[1,1,2,2,2,2,1]$ terdiri dari $3$ buah segmen

**Objective**

Kita ingin mewarnai **semua** pohon yang ada dan membentuk **tepat** sebanyak $K$ buah segmen. Tentukan **biaya** minimal yang diperlukan

**Constraint**

- $1 ≤ K ≤ N ≤ 100$
- $1 ≤ M ≤ 100$
- $0 ≤ c_i ≤ M$
- $1 ≤ p_{i,j} ≤ 10^9$

**Contoh Input**

<pre>
3 2 2
0 0 0
1 2
3 4
5 6
</pre>

**Contoh Output**

<pre>
10
</pre>

**Solution**

<details>
<summary>Hint 1</summary>
Apabila kita mewarnai pohon dari kanan ke kiri, maka sebuah segmen baru hanya akan terbentuk apabila warna dari pohon yang sekarang mau kita warnai berbeda dengan warna pohon di sebelah kanannya
</details>

<details>
<summary>Hint 2</summary>
Pada suatu pohon, kita bisa memilih warna apa yang mau kita gunakan buat mewarnai pohon tersebut
</details>

<details>
<summary>Hint 3</summary>
Kita bisa menyimpan state DP nya : pohon yang sekarang kita mau warnai, banyak segmen yang sudah terbentuk, dan warna pohon yang sebelumnya kita warnai
</details>

**Source Soal**

<details>
<summary>Link</summary>
<a href="https://codeforces.com/problemset/problem/711/C" target="_blank">Codeforces 711C - Coloring Trees</a>
</details>

---

### Soal 5

**Abridged Problem Statement**

Diberikan sebuah array berisi $N$ buah elemen $a_1, a_2, \ldots, a_N$. Kamu ingin memilih sebuah subsekuens dari array tersebut sedemikian sehingga **jumlah elemen** dari subsekuens tersebut dapat habis dibagi $M$

**Objective**

Tentukan apakah subsekuens tersebut dapat ditemukan

**Constraints**

- $1 ≤ N ≤ 10^6$
- $1 ≤ M ≤ 10^3$
- $1 ≤ a_i ≤ 10^9$

**Contoh Input**

<pre>
5 8
4 15 9 13 2
</pre>

**Contoh Output**

<pre>
YES
</pre>

<details>
<summary>Source Soal</summary>
<a href="https://codeforces.com/problemset/problem/577/B">CF 577B - Modulo Sum</a>
</details>

---

### Soal 6

**Abridged Problem Statement**

Kamu diberikan 2 buah array $A$ dan $B$, masing-masing berukuran $N$, di kedua array tersebut, tidak ada elemen yang sama. Kemudian kamu hendak melakukan proses "penggabungan" sebagai berikut :

- Buat sebuah array baru $C$
- Kemudian, ulangi langkah langkah berikut :
- Bandingkan elemen paling depan pada array $A$ dan $B$, lalu ambil elemen yang lebih kecil dan pindahkan ke bagian belakang dari array $C$. Apabila salah satu array sudah kosong, maka pindahkan elemen dari array yang belum kosong
- Ulangi hingga kedua array tersebut kosong

**Objective**

Sekarang kamu diberikan array $C$ hasil penggabungan yang terdiri dari $2N$ elemen yang berbeda. Tentukan apakah ada array $A$ dan $B$ yang memenuhi untuk bisa membentuk array $C$. Ingat, kedua array tersebut harus berukuran $N$

**Constraints**

- $1 ≤ N ≤ 2000$
- Elemen elemen pada array yang diberikan dijamin **unik**

**Contoh Input**

<pre>
4
3 2 6 1 5 7 8 4
</pre>

**Contoh Output**

<pre>
BISA
</pre>

**Contoh Input 2**

<pre>
6
4 3 2 5 1 11 9 12 8 6 10 7
</pre>

**Contoh Output 2**

<pre>
TIDAK
</pre>

<details>
<summary>Source Soal</summary>
<a href="https://codeforces.com/problemset/problem/1382/D">CF 1382D - Unmerge</a>
</details>

---

### Soal 7

**Abridged Problem Statement**

Diberikan $N$ buah elemen pada array $a_1, a_2, \ldots, a_N$. Kamu bisa melakukan operasi berikut berkali-kali :

- Pilih sebuah subarray $[l, r]$ dimana $a_l = a_r$, kemudian buang semua elemen $a_l, a_{l+1}, ..., a_r$

**Objective**

Tentukan banyak maksimal elemen yang bisa dibuang

**Constraints**

- $1 ≤ N ≤ 200000$
- $1 ≤ a_i ≤ N$

**Contoh Input**

<pre>
5
1 2 2 3 3
</pre>

**Contoh Output**

<pre>
4
</pre>

<details>
<summary>Source Soal</summary>
<a href="https://codeforces.com/problemset/problem/1842/C">CF 1842C - Tenzing and Balls</a>
</details>