![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjKSGeEnQCALdHN1CxakudmOafl4MykLS6dHxzCwjAf3_mjGd9ie0Qe4CkHWH-w0Vcp2cSkmtaKanP1S_Jby3r3I0CtvAO_5TsXeBzgMiXeEtdGFp_d-a4_aUsSyUXmVk1TTXi5TQ/s320/d110004.png)
It is up: http://apps.topcoder.com/wiki/display/tc/SRM+577#BoardPainting
I thought I understood the solution to this problem. During the match, I was pretty sure it was min cut but I had no idea how. Then rng_58 sent me an explanation on how to make the min cut algorithm. So during the week I focused on distractions such as trying to find a proof for the easy solution in div2 hard (Hardest solution to prove in a while, I am not even sure if it is possible to prove it :/). And then with trying to think of a good way to explain div1 medium.
Then yesterday as I was getting ready to explain this problem, I suddenly noticed that, although I understood the solution, I had no idea of why it works or how to think of it. So I spent some hours figuring things out. I think the explanation is still not very good though.
It is very impressive to find that this problem has a polynomial time algorithm. Back in 2007, the SRM 383 version of this problem taught me dynamic programming using bitmasks (Hence why I remember so much about this problem). Who would think it was possible to also learn max flow from it?
No comments :
Post a Comment