### G. Puzzling Words

Author: Suhendry Effendy
Prepared By: Suhendry Effendy, Felix Halim, Hutomo Widjaja

This is the second most popular problem (in term of the number of submission) in the contest with 569 submissions. Again, I didn’t expect this.

This problem can be solved either by dynamic programming or greedy approach. On both methods, first we have to construct the rooted tree to represent the relation between input strings. A node X is a parent to another node Y iff string X is prefix of string Y and their length differ by 1 (i.e. X can be paired with Y, and X is shorted). Notice that each node will have at most one parent, thus the relationship between all strings will be a (rooted) tree. Create a super root to all nodes which have no parent to make your algorithm easier to be implemented. Now the problem becomes finding a maximum matching in tree.

A straight forward solution for the maximum matching in tree would be using dynamic programming approach. The dynamic programming state would be dp[node][used] where node is the current node, and used is a boolean value whether the current node has been paired (with its parent). If used is true, then you have no other choice except not pairing the current node with any of its children, i.e. the subproblem would be dp[child][false]. Otherwise, you have the option to pair the current node with ONE of its children, while the remaining children are free. To do this, first you have to compute the sum of all dp[child][false]. To pair the current node with one of its children, you only need to “replace” the sum, i.e. sum – dp[target][false] + dp[target][true]. Remember, you still have the option to not pair the current node to any of its children.

Greedy approach can also be used to solve this problem. At each step, pick one leaf node, pair it with its parent (if its parent hasn’t been used), and remove this leaf node from the tree (this might cause other non-leaf node become leaf). That’s it. It might sound simple, but you have to be careful with the implementation, especially when updating the tree. Hutomo Widjaja used this approach, but his first few codes got Wrong Answer because of small mistakes in the code.

There were a lot of wrong submissions to this problem. I randomly checked those submissions and found that many submissions used a wrong greedy approach. One popular approach was by first sorting all the strings and pair each succesive string whenever possible. This solution is clearly wrong, one simple counter example would be: A, AB, ABC, AC. If you pair A with AB, then you will only get one pair, while you can have two: A-AC and AB-ABC.

There are 569 submissions have been made for this problem, in which 53 teams managed to get accepted. The first team who solve this problem is Javelin (minute 35) from Bina Nusantara University.

### 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.