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.