tag:blogger.com,1999:blog-1953325079793449971.post5398692848083640095..comments2024-02-15T20:32:59.333+01:00Comments on Algorithms Weekly by Petr Mitrichev: A week without branching and the best problem of 2019Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-1953325079793449971.post-17784163637158927922020-02-11T02:21:58.229+01:002020-02-11T02:21:58.229+01:00Hi Petr, Thanks for your amazing blogs!
For the To...Hi Petr, Thanks for your amazing blogs!<br />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.<br /><br />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.<br /><br />Thanks for your help!<br />Anonymousnoreply@blogger.com