Monday, December 09, 2013

SRM 599 Recap and editorial : Cursed

I just barely finished SRM 599's editorial. After failing this match both as contestant and editorial writer. My conclusion is that this match has been cursed.

Div1 250

(Read editorial for actual explanation)

I was so happy with this problem when I first read it and... horribly misinterpreted it. For some stupid reason, I thought that when doing the second kind of step, you would always raise the number to square. I am not sure why this assumption happened, or how I managed to misread the problem. But it happened. The reason I liked this, is that with this assumption, the problem reduces to a div1 250 we already solved very recently. So I thought that sort of thing was cool.

I coded my solution, it passed example tests (should so confused solutions pass example tests? Maybe examples were weak?), moved on to div1 500.

Challenge phase and destruction

For a second I thought of not participating in the challenge phase. I was sort of busy that day. But last minute I decided [[It is likely people are making all sorts of bugs in 250 and bad assumptions in 500]]. I was right. Unfortunately, the first solution I opened was correct, but I didn't know it was correct (remember I misunderstood the problem entirely). So I challenge it. The challenge failed and the [Correct answer] provided by the system didn't make any sense to me. That's when I figured that a) My 250 was utterly wrong. b) I had a bad challenge, so this means -25 overall points. Worst position possible, worst rating loss possible. My only hope was to find codes that were wrong and challenge them and recover frm the -25. And to do it fast, because if someone challenged by 250, I would not be able to make any challenges any more. I tried a solution, my challenge was also wrong. Gave up...

Div1 500

What a hellish problem from hell!

During the match, I was able to do just about most of the theory. You can only use integer sides. It is impossible for odd cases. Even cases can be solved with 4 sides. You need bruteforce to find out if a triangle is possible. Unfortunately the time I had allocated during the match was not nearly enough for me to code a solution using this idea and optimize it. OMG, optimizing this brute force was so difficult.

I think this problem would have been a good div1 medium, if it only had the theory part. Such complex implementation on top of the theory makes it too extreme for this slot, imho. The constraints were certainly too tight. I think L <= 1000 or 2000 would have been just fine.

I had so many issues solving and explaining this problem. I had to spend ages coming up not only for optimizations, but for optimizations that I can prove are correct. Eventually it was clear I was not going to finish in less than 48 hours if I wanted to solve this problem. So I moved to the hard... Bad idea.

Div1 950

I didn't open this problem during the match. At first the description sounded very easy. rng_58 called it "an implementation problem". Well yes, but not that much. I didn't really understand how the recurrence worked, and I had to do plenty of reverse engineering of rng_58's code. ... If only Petr made his blog linking to author explaining it in codeforces before, maybe it would have been better. ... (BTW, why?, why can't we have TC problem set writers explaining that way in TC's forums? I mean, how did TopCoder manage to kill its community so much? The forums used to be so active and interesting before)

Finishing the editorial

When I noticed, I was already late for both deadlines. And I was finally understanding how to do the hard. Then I had to fix again what I had for div1 medium. Then do the other problems, which were not non-trivial to explain at all. There was a time period in which I thought I would never finish this editorial.

If you think editorial delays are bad for you, editorial reader, think about how awful they are for the editorial writer. Instead of spending a couple of days in a SRM, I ended up spending almost a week on it. There's plentyof things I couldn't do because of it.

Comments and please vote

Any comments. Also please post feedback to the editorial page, specially, vote. I really dislike that there are so few votes (negative or positive) in editorials when SRMs have hundreds of participants. (Did I already mention something about TopCoder's community being dead?)

The problem set was cool, although 500 was probably too interesting for div1 medium. Maybe swapping div1 500 and div1 hard and making div1 hard have smaller constraints would have been better? I really dislike to have failed this match, I really could have done more.

No comments :