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....
No comments :
Post a Comment