### Petr's blog

By Petr, history, 2 months ago, ,

• +39

 » 2 months ago, # | ← Rev. 2 →   +8 Petr For the TopCoder problem, mentioned, I'm unable to prove this part: However, we still have the freedom of choosing which pair of green and red ends we use for reducing the problem to size n-1. If b>0, then we will choose which green end is one of the red ends of the first green-red string paired with.If we delay merging green-green strings with red-red strings until the end, how do we prove that the answer doesn't change? Playing around with the DP recurrence didn't help.Thanks for your help!