The ACM ICPC World Programming Finals took place a few days ago on April 21st. St. Petersburg State University of IT, Mechanics and Optics was first, Tsinghua University second, and St. Petersburg State University was third. You can check out the full standings here. As usual, Waterloo was Canada’s top competitor, finishing in the medals for the 6th year in a row with six problems solved. I...
I am finally back from my almost month long vacation to Japan and China. The trip was fantastic. It was nice to take a break from programming and work for such a long period, but now I am back and trying to scramble to get caught up. I am teaching a third year course on HCI this summer, so I need to prepare for that. I am also starting as a postdoc in May and doing that until the end of the year...
This is not a very programming related post, but I had my PhD defense today. It went very well. My thesis is being nominated for the University of Victoria Gold Medal, which is the prize for the top PhD thesis at the university. It is probably a long shot as I’m sure there are plenty of good theses out there. Also, I don’t know how any committee could compare a PhD from math with a...
I competed in the Top Coder Open 2009 Round 1 last Saturday after qualifying the previous week. My friends Nick and Oleg also competed. You had to finish in the top 720 to qualify for the next round, but only Oleg managed to do that out of the three of us. I was very close, but unfortunately an off by one error caused me to fail system tests. The first problem was pretty easy. You were given a...
I participated in a TopCoder practice session yesterday with Oleg and a new student in our research group, Nick. It turned out to be my best SRM in quite some time. I think I submitted all three problems before Oleg and Nick had submitted their second solution. I was a little worried that I had messed something up since I finished so quickly. I started looking at my 500 and 1000 point solutions...
I’ve been working on this program with my friends Dmitri and Oleg. The program computes permutations of reversible circuits (i.e. NOT gates, CNOT gates, etc.) for different numbers of inputs. The gates are simulated by performing bit operations on 64-bit unsigned integers. The details aren’t that important, but what’s interesting is that the number of permutations gets massively...
Last post I mentioned that I had not been able to come up with a decent algorithm to problem H from the Waterloo practice. Well, yesterday, while running, I figured it out. There’s an N^2 algorithm that’s pretty straight-forward. The problem involves a bunch of planets and each planet has a certain political situation, 0 or 1. A planet is considered unstable if given some value R...
I had Dan and Scott join the University of Waterloo’s online 5 hour practice session yesterday. John couldn’t make it, so I helped out more than I normally would. I didn’t write solutions to any of the problems, but I helped with debugging, reading the problems and some problem solving. The contest problems were taken from the Northeastern European Regional 2003. The guys solved...
I moved this week’s programming club meeting to Wednesday so that I could compete on TopCoder on Thursday. This week at the meeting I introduced people to Robocode, which is an environment and API for developing little tank robots. You can control the robot tank’s radar, gun, and movement. The goal is to program the best strategy such that you beat all the other robots. I had played...
I tried doing a team practice session last night during our weekly PClub meeting. It didn’t go as well as I had hoped. Several people had to miss practice for various reasons and some people showed up late, so I wasn’t able to put together the teams I had planned. I had one team work on problems from last year’s Northwestern Europe Regional while the other two teams worked on...
