Petr's blog

By Petr, history, 2 months ago, In English,
 
 
 
 
  • Vote: I like it
  • +39
  • Vote: I do not like it

»
2 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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!