Volatility

Just finished off a TopCoder match(SRM 241, to be precise) and decided to give the experience some blog time. This is only my second SRM, so all you seasoned TopCoders out there - please excuse my excitement over things that you've probably gone through a dozen times already.

Before everyone nods off to sleep - here's a potted version of what happened:

1. Match starts at 6:30 AM, Indian Standard Time. (Yawn!)
2. I do the easy problem.
3. I do the medium problem.
4. I code up the hard problem and start testing.
5. Things don't seem to be giving me the right answers - something is screwy...
6. Coding phase ends - there goes the hard problem - time for the challenge phase.
7. Someone views my easy problem code for a suspiciously long time. It's no surprise when he successfully challenges it - depriving me of almost 200 points.
8. I have the satisfaction of watching my challenger get successfully challenged.
9. I find someone who has a blatant mistake in his code. About to figure out how to challenge, but someone beats me to the punch. Drat.
   
10. Challenges fly thick and fast. At the end of the challenge phase, only 6 of the easy problems are still standing - out of about 20 in the room.
    
11. Time for system testing. Sit and wait.
12. Things end - my medium still stands - and I end up squarely in the middle of the room.

For those of you who haven't been able to make any sense of this - a few words of advice - buzz off to TopCoder and look it up(there's a link on the left) - or just buzz off. This post isn't exactly for general consumption.

Now - let's get into the gory details...

First off - sleep! If only I wasn't yawning through the first problem, I might have seen the line in the problem statement that led to my downfall...Adding one extra line would have taken care of it(N.B: Haven't had a chance to test this out yet, but looks likely.) I'm still yawning a bit as I write this.

Second: On the hard prob - I could have simply used a variant of Floyd-Warshall. Sadly never saw it, jumping into a recursive depth first search instead. If I had submitted it - it might never have handled test cases with large inputs without blowing the stack. Sad...Really have to stop jumping at the first solution that pops into my head. Kinda reminds me of (Digression Alert!) Paul and Leto Atreides II in Dune - by viewing the future, they froze it into unchanging form, and then spent the rest of their lives breaking out of the traps that their prescient vision led them into(and indirectly, the rest of the human race as well). As with most things in Dune, you can pull a lesson out of this - premature design can be a deadly thing. Paul Graham has something to say on this as well, but I can't remember which of his essays addresses this issue.

Third: I really have to look up commonly used algorithms. Unless you can see complex problems as variants of stuff you've done before, chances are you won't be solving it within the time limit. The standard algos(Dijkstra's shortest path, 0-1 knapsack, etc.) are the building blocks of solutions to the hard stuff. You have to weave them together using the standard algorithmic programming techniques(divide and conquer, dynamic programming, memoization...) and tie the whole lot together with some old fashioned ingenuity. And naturally, these three are all connected on a deeper level, so you shouldn't be surprised if getting better at one makes you better at the others...

That's about it for the abstract stuff. On to more mundane matters...

Ran into a friend of a friend in the competition arena. For those of you who know him, the friend happens to be Mihir(the one who lives 2 floors down from me) and his friend happens to be a chap called Nishant(hope I have this right - I can't remember his surname), otherwise known as niphoton on TopCoder. If the name rings a bell, he was the coder of the month for April...

Apparently someone screwed up the system tests. For about fifteen minutes(might have been longer) into the system testing phase, it looked like everyone had failed the Div 1 500 pointer. Someone pointed this out, and I went through all 10 rooms in div 1, searching for someone who hadn't messed up. Naturally I came to the conclusion that something was screwy...then the admins mentioned that something was wrong with the systests. Thankfully for the Div 1 guys, everything worked out. I think the mess up also affected Div 2, since my rank rose from 9 to 4, before falling back to 9 once things were fixed. Interesting how both these ranks were consecutive squares...

That's about all for now - off to check if my rating and rank has been updated - and if I've turned up in division 1(still not sure if that's good or bad - see previous post). And of course, to see if Tomek has managed to give Eryx and Snapdragon a beating and reclaim his throne...