### D. Breaking Board

Author: Winardi Kurniawan
Prepared By: Winardi Kurniawan, Felix Halim

I didn’t expect this problem to be one of the least solved problem in the contest (along with problem J). This problem was fully prepared by Winardi Kurniawan (the author himself), and Felix Halim who became the tester for this problem. I only discussed the problem (and the solution) a bit with the author.

First, notice that the input board can be very sparse, with 106 x 106 domain, but only ≤ 100 coins. Thus, the first thing you should do is compress the board by removing all empty rows and columns; in other words, only consider rows and columns which has at least one coin. The resulting board should be at most 100 x 100 in size. After compressing the board, the problem (should) become (much) easier, but not that easy. Remember that the goal of board breaking is to divide the board such that each side has a same coin type, swapping the coins if necessary. We can achieve this goal only if the number of coins in one side is equal to the number of coin with of a certain mark (either O or X), thus, it becomes possible to achieve the goal by swapping the coins.

Next, also notice that minimizing the number of needed swaps is equal to minimizing the number of different mark in one side of the board (those different mark will be swapped). Given the small constraint of N, it is possible to solve this problem using dynamic programming.

Let C be the number of coins with ‘O’ mark in the input board. Define the dynamic programming state dp[i][j][C] as the minimum number of coin ‘X’ will be collected when the board is broken from cell (i, j) and C is the remaining number of coins which should be collected from (i, j) until the end of the breaking. Starting from the top-left most corner, we can solve dp[i][j][C] by solving its subproblem: moving right, or moving down. If we move right, then we collect all coins in previous column. If we move down, then we did not collect any coin. Notice that we should precompute the number of coins which will be collected if we move right at (i, j) to fasten up the program. You also need to precompute the number of ‘X’ coins. These precomputation can be done in O(N2).

Notice that in previous paragraph, we tried to collect ‘O’ on the left side of the board (minimizing ‘X’). We should also do the other alternative: collect ‘X’ on the left side. Thus, twice the DP.

Felix Halim commented on this problem that contestant should be careful with the indexes. It’s easy to have an off-by-one error in this problem. If you check the scoreboard, there are no team which solves this problem in their first attempt.

There are 31 submissions have been made for this problem, in which 3 teams managed to get accepted. The first team who solve this problem is BerinGAS (minute 180) from University of Indonesia. The other two are Sylph (Bina Nusantara University) at minute 249 and DELAPAN.3gp (Institut Teknologi Bandung) at minute 279.

### 27 Responses to “ACM-ICPC INC 2014”

1. “One popular approach was by first sorting all the strings and pair each succesive string whenever possible”, kode saya spt itu, hanya saja pasangkan dr yg terpanjang http://ideone.com/PGjPAq

2. komen untuk prob J

βOne popular approach was by first sorting all the strings and pair each succesive string whenever possibleβ, kode saya spt itu, hanya saja pasangkan dr yg terpanjang http://ideone.com/PGjPAq

• koreksi, prob G

• Ngga, kode kamu nggak seperti itu. Approach kamu itu jadi sama dengan approach greedy yang bener (pasangin dari leaves) — string yang paling panjang saat itu pasti leaf.

Yang dimaksud “pair each succesive string whenever possible” itu comparenya bener-bener cuma sama 1 string di sebelahnya aja (sorted); sedangkan kamu compare dengan yang panjangnya lebih pendek.

3. a bit curious about problem H. Did you use the real Kawal Pemilu data for judge’s test case? π

• According to the author: YES π

• Nice π

4. nice problem, nice editorial, pretty helpful, thx π

5. saya penasaran dgn problem yg blm sempat saya kerjakan (dan AC), apakah mungkin akan diupload ke situs online judge ?

saya dpt ide sederhana utk problem J dgn menelusuri apakah suatu nilai bisa jadi pivot (menjadi ‘L’), setelah itu cek apakah bs dr index tersebut menjadi good segment, jika tidak cetak impossible, kode saya : [[REMOVED]]

thx koreksinya π

• Lho, cara handle mod-nya (line 30, 41 – 43) jelas salah donk? Kenapa cuma consider pivot L yang ga punya pair-mod nya di dalam array input? Yang diminta kan pivot L yang segmentnya ga ada pair-mod nya.

contoh:
6 10
5 2 8 1 9 5

• karena “((SL + Si) mod M) ? 0, for all i where L ? i ? R.”

apakah mksdnya nilai di index L, jika dipasangkan dgn semua nilai dari L sampai R, modnya tdk akan 0 ?

utk input spt itu outputnya impossible bkn ?

• oh, bayangan sy sblmnya, segment L-R, jumlah bilangan yg berbeda harus sama dgn jml bilangan berbeda array 1 – N

• kelihatannya di situ kesalahannya, gara2 asumsi jml bil beda hrs sama dgn array input…

pertama baca merasa ada kemiripan dgn soal spoj DQUERY yg blm sy mengerti jg π

• Ho iya, “value” di soal J ini sama dengan nilai si d-query (number of distinct elements in a segment).

• “for all i where L <= i <= R" -- artinya cuma dipair dengan semua [L, R], bukan [1, N]; [L, R] itu segmentnya.

• permisi, mengganggu lagi :D, saya sdh mencoba membuat NOMOD utk range tertentu

semoga sudah benar :), [[REMOVED]]

hanya saja kompleksitasnya NOMOD tdk O(N) karena menggunakan map, kalau ada unsorted map spt c++ 11, mgkn bs π

membaca tutorial kadang jd pengen kerjain lg, apakah bs diupload soalnya ke OJ ?

• aduh msh ada salah ><, setelah di-fix, smg uda bener [[REMOVED]]

• Oit, maap beberapa hari ini lagi away, baru bisa cek messagenya.

Solusi yang pertama (SbojVj) masih salah, tapi solusi yang kedua (5i1Mvi) AC π

Anyway, soal sedang diupload ke JOJ, sebentar lagi selesai.

• terima kasih banyak π

• Soal INC sudah diupload ke JOJ. Kode soal: INC14A … INC14J

http://jollybee.binus.ac.id/oj/site/problemset/problem/code/INC14A/

• ok pak, terima kasih, di grup fb ada yg minta sekalian saya post ya link-nya π

• oh ya, apa komen saya yg menyertakan kode yg hampir AC dan AC bs diedit link-nya, takutnya dicopas buat JOJ (kalau boleh copas buat JOJ ya tidak diedit tidak apa2)

saya wkt nulis di ideone tdk login waktu itu, jd tdk bs edit kode di ideone

• Sip, udah diremoved semua link ke code nya π

6. How about ACM-ICPC 2014 Jakarta write up?? Will it be published?

• Yes, it will.

I “lost” one week due to other events after ICPC (and I’ve just come back to my home). So, expect a few more days delay π

7. How can I get input data ?

Thank you for sharing.

• Ah… I didn’t notice this comment before >.< I'll not share the input data publicly. You can test your solution in some online-judges, e.g., tokilearning or joj. (I think) I have sent the test data to the admin on those sites.