Thursday, October 17, 2013

SRM 594 editorial (Part 1)

The first part of SRM 594 editorial, containing explanations for all problems but division 1 hard is up at:

I really hate that there was a delay. This time I really have no excuse, except for the fact that this problem set, specifically division 1 medium and division 2 hard seem to have been designed with the specific objective of making editorials long to write . They have these hard to think of solutions. Hard to prove solutions. And explanations that need to be image-intensive.

While in that topic, I think my explanations for both of those problems are terrible. In Div2 1000 I had no choice but to keep saying "connected component". Div1 medium is bad because it really does a bad job explaining how to come up with that approach. Probably because nobody knows how to do that, it seems to be something that happens espontaneously in good coders's brains without explanation.

I now have less than 48 to solve and write the explanation for div1 hard. I hope I can do it. The fact that nobody solved it during the match (Including Petr and tourist ) does not make me optimistic.


Vijay said...

D1-550 is not yet clear to me even after reading that long explanation. It confused me first why subtracting 'max'flow maximizes what we want. But it should be thought really as 'min'cut or even better #('.'s and 'o's) - 'min'vertex-cover, which somewhat makes sense. I know its really hard to write editorial for such problems. But, I wonder if the writer who thought of this problem in the first place could have contributed to editorial to make understanding better. Thanks for all your write ups, really appreciate and enjoy them !

JOmegaCV said...

I view the general version of this problem as:
1) You have two disjoint sets of elements (here they are blank spaces + blank spaces created by removing white tokens)
2) You want to maximize the total number of elements you have in both sets in your solution
3) There exist constraints between the two sets which state that if one element is present, some other node cannot be present (represented as edges).

Starting with all vertices present (the ideal solution), what is the minimum number of vertices you need to remove to have all constraints met? Then it is clear to me that the solution is total elements - minimum vertex cover.

I would have to guess the writer used BPM just because it is == min vertex cover. I can't think of a way to conceptualize it with BPM that "makes sense."