This will probably only be interesting for TopCoder players, and they've probably already seen this on the forum, but anyway. Feel free to scroll over.
This was quite an educating experience from two points of view:
1) The coding times for the problems were 3 min, 52 min and 13 min. In other words, I've spent very much time on the medium, and had to write the hard in a hurry that eventually led to it failing systests. This was not the first time for this to happen, and I've always thought "maybe I need to abandon the medium and go for hard now?" many times, and I've always decided to postpone that decision. I would imagine that such a choice appears more frequently for those who don't usually solve all 3 problems - how do you deal with it?
2) The hard failed because of two bugs. The first one was a loop having a "<" instead of "<=" in the boundary condition, which I think is one-off and hard to prevent systematically. But the second one is very common: an int overflow. And I've always knew that C# can check against that, but somehow haven't been using this feature ("/checked+" compiler option, or the corresponding checkbox in Visual Studio). I will now.
Not much to say here. A quite standard hard that led me to a relatively easy win, a very beautiful medium that I was maybe lucky to solve quickly.
A submit with 10 seconds to go that passes systest, which uses a theorem that I've only had a 'heard-about' knowledge of before the SRM, and after rewriting the solution from scratch at least twice — doesn't look like a dull experience, does it? In retrospect, I shouldn't have even tried writing that DP over all splits of 16 numbered items into groups without finding out that there are billions of those; the Internet connection shouldn't have failed for about 5 minutes when I was struggling with the hard. But maybe because of all that I was finally able to invent a correct solution with about 15 minutes to go, and implement and debug it in that quite exciting last 15 minutes.
It was a nice popup window when the internet went down, revealing some details :)
ReplyDeletecoooooooooooollll!
ReplyDeleteIt's a great performance, "a diagram worths many words" :)
ReplyDeleteI'd like to know, where I can get your plug-in that automatically extracts the examples test cases.
Andrey, you can get them at http://www.topcoder.com/tc?module=Static&d1=applet&d2=plugins
ReplyDeleteDon't be shy and read their documentation.. I think Petr uses some kind of TZTester modified by himself.