Petr's blog

A week without branching and the best problem of 2019
By Petr, history, 5 years ago, In English

https://petr-mitrichev.blogspot.com/2020/02/a-week-without-branching-and-best.html

  • Vote: I like it
  • +39
  • Vote: I do not like it

»
5 years 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!

→ Reply