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!