Nov 112014

G. Puzzling Words

Author: Suhendry Effendy
Prepared By: Suhendry Effendy, Felix Halim, Hutomo Widjaja
(link to problem G)

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

  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

    • 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? πŸ˜€

  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 πŸ˜€

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

  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.

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>