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...
The First Annual UVic Programming Contest took place last Saturday, January 31st, 2009. The contest went extremely smooth. We didn’t have any problems with the PC^2 software and only a few minor issues with the problem set, but everything was caught right away. There were 12 competitors in all. You can check out the problem set, scoreboard, solutions, and judge’s inputs/outputs here...
Last night was the last practice session before the UVic undergraduate programming competition on Saturday. We had a decent turn out of 11 people and I heard from a few people that are coming to the competition but couldn’t make it last night. I’m guessing we’ll have about 15 people on the weekend. I had the students do some old contest problems that Nathan Scott and I wrote...
Since I’ve started competing on TopCoder the lesson of knowing your libraries has been really hammered home for me. I was, of course, never against this, but often I would write my own functions to check alphanumeric values, parse integers and doubles, format output, and so forth. These don’t take that much time to write, but it’s still time away from writing the actual solution...
I did a practice SRM on TopCoder this morning with my friend Oleg. It was SRM 308 Div 2. It went reasonably well, we both got 2 out of 3 accepted. Oleg submitted the 1000 point problem but made a simple mistake by calling the min function rather than max function in one place. I didn’t end up submitting the 1000. Oleg beat me by about 20 points as he finished the second problem faster than...
I posted this week’s problem of the week challenge on the UVic programming club website. You can check it out here if you’re curious. It’s based in part on a problem I did years ago at one of my first contests. It’s not a really challenging problem, although some people may struggle with the parsing and this is in part why I chose this problem. The students main hurdle at...
