{"id":182,"date":"2005-06-21T22:22:36","date_gmt":"2005-06-22T03:22:36","guid":{"rendered":"http:\/\/UnhinderedByTalent.com\/Phi\/archives\/2005\/06\/21\/my-id-gotten-rusty\/"},"modified":"2005-06-21T23:02:38","modified_gmt":"2005-06-22T04:02:38","slug":"my-id-gotten-rusty","status":"publish","type":"post","link":"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/2005\/06\/21\/my-id-gotten-rusty\/","title":{"rendered":"My, I’d gotten rusty"},"content":{"rendered":"

\"RustingI competed in a TopCoder programming competition<\/a> for the first time in way<\/em> too long, and it showed. I didn’t completely<\/em> tank (I’ve certainly done worse), but it took too darn long to find some of those neurons and get them to fire. I hadn’t actually competed since last October, which was so far back that they’d taken me out of the ranking tables (I think you have to compete every six months to remain active), but this should restore that. Unfortunately being so rusty didn’t really help my rating much, and I dropped from a 1519 to 1487. This drops out of the yellow region of the ratings table and into the top of the blue region, which is the first time I’ve ever not been yellow since my first competition nearly 2 years ago. I’m quite bummed. With a little luck I should be able to compete several more times this summer, brush some of that dust off, and get back into mid-yellow where I think I belong.<\/p>\n

<\/p>\n

I completely blocked on the 250 point problem and eventually decided to skip it and open the 500 point problem. That one I managed to plod through, but it took longer than it should have and I only got 233 points for it. (I think if I’d been in “better shape” I should have been over 300 there.) I then looked at the 1,000 point problem, decided it was way past what I could do in the 20 minutes remaining (esp. given how things had been going). It looks like a pretty standard alpha-beta search problem, but I tend to get lost in the details of those kinds of things and take forever on them. So I went back to the first problem and after a few minutes of reflection figured out how to use the symmetry of the problem to reduce it to a simple closed form that took all of about 2 seconds to code up. I only got 95 points because I’d spent so long on it (they count all the time from when you first open the problem, which included all my time on the 500 point problem in this case). If I’d seen how to do that right away I probably could have gotten over 200 points on that. Sigh.<\/p>\n

The nice thing about going back to that first problem is I nearly fell into a simple trap (a case where the input string only had one character), which suggested that during the challenge phase I should look for others that made that mistake (and didn’t catch it). I got one successful challenge that way, and nearly had another, but got nipped by someone else a few seconds before I submitted mine. With the additional 50 points from that successful challenge, I went into the system test phase with about 380 points, which put me about the middle of my room.<\/p>\n

The real kick in the pants, though, was when my second problem didn’t survive the system tests, which plummeted me to 145 points, putting me at 218th out of 320 that competed in Division I tonight. Sigh again. It turns out that I passed a ton of system tests, and then timed out on a particularly long one. Hmph. I’m not sure why that happened. Perhaps I just needed to tighten up some code (it wasn’t particularly speedy), or perhaps I needed to use something like memoization<\/a> or dynamic programmin<\/a>g to avoid recomputing values.<\/p>\n

In my long stretch of not competing they apparently added a new unused code rule (or put more teeth in an old rule that I don’t remember). This is nice, because you used to get programs that were absolutely full<\/em> of unused stuff, which made figuring them out a lot harder during the challenge phase.<\/p>\n

I also had trouble connecting and had to use HTTP tunnelling, which I’ve never needed to use before. I’m not sure if that’s a change on their end or UMM’s end, so I’ll have to do a little poking around.<\/p>\nNo tag for this post.\n\t

Related posts<\/h4>\n\t