September 18th, 2006

color cycle (slow)


There was a TopCoder match tonight (for those of you not aware, my handle there is Windrider), and the NSA was sponsoring a $5,000 prize pool. 70% of the pool goes to Division 1, with 30% going to Division 2. To give everybody at least some chance (not just the people who consistently score highly for the whole round), the prize is further divided by room, so your position in your room- not your overall rank- determines your payout. (Rooms are filled randomly, 20 people each.) The room winner scores 50% of the pot (in Division 1- D2 uses a different distribution), second place gets 30%, and third gets 20%. There are no extra prizes for overall rank, but overall is what decides your rating.

I came in 2nd in Room 13, with a score of 1107.33 points. I came in 27th overall. This is my highest score for a Division 1 problem set, my highest ranking for a Division 1 problem set, and the only time I've won money in an SRM. (I've won cash in previous tournaments- we'll see if I can do it again when the TCCC Round 1 begins this Saturday.) This is also the first time I've swept the problems in Division 1, solving all three of them correctly.

I'm happy about the (approximately) $45, but getting every problem (including the Hard) in Division 1 is what really has me in a good mood. That's the first time I've done that in a real match. (Early tournament rounds are more like D2 in difficulty and don't count.) This match did play to my strengths- discrete mathematics- but still, I'll take what I can get.

My rating is now at 1891, the highest it's ever been. It'll probably drop across the next few matches, but it's fun to have a rating like that, at least for a while. But getting the Hard problem right with the first algorithm I thought of... that's the really cool part.

The punchline is that I coded up my 1000 and submited it as a joke. I just thought up what I thought was a crazy, impossible algorithm, which I wrote mostly so I could use the variable name "antimanhattan". I just had this guess as to what might work, what might exhibit some properties of the right answer- which points I could ignore and still get the right answer. (The problem: Out of 250,000 points generated by an algorithm with fairly messy output, find the pair with the longest Manhattan distance in two seconds or less.) My "only use the manhattanest, the antimanhattanest, the unmanhattanest, and the unantimanhattanest; return longest corner-to-corner" was just this crazy idea I thought of, but then it passed all the example cases. So I submitted it... and it accidentally worked.

A lot of good ideas are like that.

Did I get it by accident? Not really. I coded it right. And I know discrete mathematics well enough that apparently, even when I don't know why, my intution can be correct- and good intuition requires at least some level of knowing what I'm doing.

But anyway. 27th place of 470. SQUEE.
  • Current Music
    The Chemical Brothers- The Private Psychadelic Reel