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