SRM 600 prelim editorial and recap-rant

So the double contest trouble last weekend ended and it was disastrous to me. But first , let me point you to the first 5/6 of the editorial at : http://apps.topcoder.com/wiki/display/tc/SRM+600

There were t-shirt prizes and I foolishly hoped to maybe get a t-shirt. I forgot how bad SRM 500 was on my luck.

Div1 250

link to statement

I solved this one right-away. You need to pick the bit position that is non-zero in goal and that has the least valid cards. I needed some time to code it and then the strange self-doubt about "maybe something is wrong", also I really wanted to make sure to get that t-shirt. I reviewed the algorithm plenty of times and proved it to myself. So I submitted it. It wasn't a slow submission, but it wasn't particularly fast either, so I rushed to solve div1 600.

It was some time after the system tests that I learned my solution actually got challenged. I was very skeptical, because I was sure the algorithm is right. Well, the algorithm was right, but for some reason I initialized my result variable with 40. I am not sure exactly what happened. It could be I made a typo and typed 40 instead of 50. Or it could be I got the constraints confused and thought to type the maximum number of bits. I don't really remember.

There is a fun story about this challenge that ruined my dreams and rating. I already wrote about it, so here is a link.

Div1 600

Palindrome matrix

I thought that my only hope for t-shirt was solving this problem. And for plenty of time in the match I thought I could do it. My first solution was actually quite close to correct. The only mistake I made was not to figure that you only need sets of palindrome rows/columns with exactly the required number of palindromes. You are not really going to care about the rows/columns so it doesn't really matter. You can actually read the first solution I tried, it is in the site statistics, it was `O(3^m)` because reasons.

When I finished coding it, I had two issues: a) It wasn't giving the right answers to example cases. b) It was taking too long (~4 more seconds than allowed) to solve the large example case. I made the mistake of thinking [Even if I fix this, it would be too slow]. It turns out that besides of bug fixes, the soution was correct. It just needed some pruning and to care only about sets with exactly the required number of palindromes. The new code was a dynamic programming that in reality did exactly the same as the old solution, I just didn't notice... New code was also wrong and somehow still slow. So the coding phase was a missed opportunity.

Anyway, this was a cool little evil implementation problem. I wish I solved it during the match.

T-shirts

It annoyed me that division 2 coders were getting t-shirts. It is a way to punish blue and yellow coders for not having low rating. I think that in matches with awards it would be preferable to have a single division (combined div1 and div2).

SRM 600.5

I wish this match didn't happen. So there was a new chance to get a t-shirt. But this time solving very hard problems. The match was advertised to have a normal SRM 1000 points problem. So I went to the match thinking of spending 4 hours on that problem and hopefully solving it. It was actually very obvious that far less than 40 coders were going to solve more than one problem in this match. When I learned the match actually had a challenge phase, I felt robbed. It was obvious that people were going to submit bogus solutions for some reason, allowing other people to get 50 points and probably joining the top 40.

Really, the TopCoder format is terrible for this kind of match. If the act of opening problems didn't penalize you, it would have been much better to open all problems before deciding which to solve. Instead, I had to rely on the point values assigned to the problems, which were terribly wrong. The 1000 points problem I spent 4 hours trying to solve was solved by no one.

It was a interesting problem. Come up with `n` distinct positive integers such that, for each `1 <= i <= n` , the sum of the `i` largest integers is less than or equal to `s_(i-1)`. Where `s_i <= 1000000000`. I spent a whole afternoon trying to find a secret. Trying to decode the safe that hides the solution to this problem. All with no luck.

So the t-shirts given to people that just got lucky (Many rooms didn't even have any submission at all, whilst some rooms were full of bogus solutions). It was a bit of a waste of t-shirts. I wish they would have included at least a div1 medium or easy problem so that there was a better tie-breaker than the challenge phase. IMHO, maybe not include a challenge phase at all.

Comments?

Problems seemed good. I am just in a very bad performance streak. My decisions during contests are seeming to be very bad lately. Also, I seem to have completely lost the ability to correctly estimate whether a solution will run in time or not.

The way the SRM 600 celebration was made was very disappointing, giving prizes to div2 in SRM 600 or to people being very lucky in SRM 600.5. I would have preferred to have a single division in SRM 600 so that if div2 coders win a t-shirt it is by performing very well , or by being lucky. SRM 600.5 really didn't need a challenge phase...