Editorial Codeforces 1525E

Educational Codeforces Round 109 - E. Assimilation IV

Deskripsi Singkat

Intinya diberikan ada $N$ kota, dan $M$ desa. jarak kota ke-$i$ dengan desa ke-$j$ ialah $d_{i,j}$. Perhatikan bahwa kita bisa membangun $N$ buah monumen, dengan monumen ke-$i$ memiliki power $i$. Jadi bakal dibangun semacam urutan permutasi untuk setiap kota, secara random. Bila ada monumen ke-$i$, pada kota ke-$n$, maka semua desa yang berada dalam jangkauan $i$ itu bisa diraih.

Pertanyaan: Berapa expected value desa yang bisa diraih, bila permutasi secara acak akan dilakukan?

Contoh Masukan

3 5
1 4 4 3 4
1 4 1 4 2
1 4 4 4 3

Contoh Keluaran

19/6

Solusi

Observasi 1

Pertama kita bisa mengetahui bahwa disini ada linear of expectation, jadi pada intinya setiap desa itu antara memberikan kontribusi pada suatu permutasi atau tidak sama sekali, dan tidak akan mempengaruhi desa lain.

Observasi 2

Selanjutnya, untuk setiap desanya kita bisa menghitung kontribusi berapa yang akan desa tersebut berikan bila kita berikan suatu permutasi yang acak. Kompleksitas akhirnya akan menjadi $O(M \times \text{count(Desa)})$.

Untuk suatu algoritma yang akan kita terapkan pada desa tersebut. Untuk $N$ yang kecil sebenarnya bisa kita lakukan Dynamic Programming dengan bitmask. Namun kita memerlukan observasi yang lebih.

Perhatikan bahwa permasalahannya sekarang menjadi kita diberikan sebuah array $A$, maka tentukan ada berapa array permutasi $B$ yang memenuhi setidaknya ada satu $A_i \leq B_i$. —Intuisinya ialah untuk setiap permutasi monumen, apakah kota ini mungkin dicapai—.

Untuk menghitung ini, kita dapat menggunakan prinsip inklusi-eksklusi. Namun mari kita cara lain yang lebih sederhana.

Untuk menghitung ini, kita dapat menggunakan teknik komplemen, sehingga kita hanya perlu menghitung $N!$ dikurangi ada berapa yang memenuhi semua $A_i > B_i \iff B_i < A_i$, mari kita ambil contoh array $A$ untuk desa sebagai berikut. Perhatikan bahwa urutannya tidak berpengaruh. \(2, 1, 3, 5, 1, 4, 2\) Perhatikan bahwa kita akan meletakkan $7$ monumen. Disini jelas bila bahwa ada $A_i = 1$, maka pasti setiap permutasi bisa tercapai. Karena setiap permutasinya tentu lebih besar dari $1$. Mari kita ambil contoh lain. \(2, 3, 3, 5, 6, 4, 2\) Nah, mari sekarang kita kerjakan. Misalkan kita akan meletakkan $1$ terlebih dahulu, maka kita bisa meletakkannya dimana saja, namun nanti untuk bilangan bilangan selanjutnya harus kita buat $>$ tidak akan terpenuhi untuk yang pertama dan terakhir. Mari kita urutkan terlebih dahulu agar lebih mudah. \(2, 2, 3, 3, 4, 5, 6\) Tambahan teknik lagi, mari kita kerjakan dari monumen yang syaratnya lebih ketat terlebih dahulu, yaitu dari monumen ke-$7$. Karena sepertinya bila dari depan tidak akan efektif, dan seperti yang kita ketahui, bila permutasi greedynya $1, 2, 3, 4, 5, 6, 7$ saja tidak memenuhi maka tidak akan ada cara menghitungnya.

Mari kita buat syarat yang sehingga kondisinya saat sorted strictly greater, untuk $A_i > B_i$. \(2,5,5,6,7,7,8\) Sekarang kombinasi $1,2,3,4,5,6,7$ strictly lebih kecil daripada array $A$, sehingga setidaknya akan ada satu kemungkinan.

• Perhatikan bahwa untuk monumen $7$ hanya bisa diletakkan untuk yang terakhir, interval $[7,7]$, kita $\times 1$ ke jawaban akhir.

• Selanjutnya untuk monumen $6$, bisa diletakkan pada interval $[5, 7]$ cara, perhatikan bahwa $8$ bisa saja diletakkan monumen $6$, tapi tadi sudah dipakai, pada monumen $7$. $\times 2$ ke jawaban akhir.
• Monumen $5$ bisa diletakkan untuk $[4, 7]$, tapi tadi sudah dipakai $2$ untuk interval yang sebelumnya, maka ada $\times 2$ cara.
• Monumen $4$, untuk interval $[2, 7]$ ada $\times 3$ cara.
• Monumen $3$, untuk interval $[2, 7]$ ada $\times 2$ cara
• Monumen $2$, untuk interval $[2, 7]$ ada $\times 1$ cara
• Monumen $1$, untuk interval $[1, 7]$ ada $\times 1$ cara.

Dengan intuisi lain, kita juga bisa dikerjakan dari depan, yaitu kita lihat desanya

• Desa pertama, hanya bisa diisi dengan $1$ monumen. $\times 1$
• Desa kedua, bisa diisi dengan $4$ monumen, tapi sudah dipakai satu monumen, $\times 3$
• .
• .
• Dan seterusnya

Dengan ini, maka kompleksitasnya menurun menjadi $O(N \log N)$ dengan sorting. Bisa ditulis pseudo code

sort(B);
ans = 1;
for i in [1 .. N]:
	ans *= B[i] - i < 0 ? 0 : B[i] - i;
total += ans;

Nantinya kita lakukan hal yang sama untuk setiap desa.