Sunday, May 05, 2013

Editorial for SRM 577 div1 hard: BoardPainting

It is up:

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 :