A preview for the editorial is up: http://apps.topcoder.com/wiki/display/tc/SRM+570
This problem was interesting to say the least. Interesting in that it is in theory a simple min-cost max flow problem. Yet nobody was able to solve it. I know that in paper, if I was developing this match, I would expect this problem to be easier than the usual division 1 hard. And it seems the admins and writer for the match thought the same - Gave it a 900 points score tag.
So why did nobody submit it? The reduction to min-cost flow is probably not trivial. I also think that most coders just didn't have time . The division 1 medium turned out to be quite a time sink. Even if you manage to think of a solution, implementing a many-dimensions dynamic programming algorithm with tricky cases is always a time sink...
That division 1 550... It really frustrated my plans. I wanted to get the editorial finished 24 hours ago. But 24 hours ago I was still trying to optimize the complexity after taking ages to actually understand what we need to do. Let me return back to writing that part of the editorial....
0 comments:
Post a Comment