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 5 of 11 problems and attempted 6. Not bad considering they were down a member, had never worked in a team before, and had some major technical difficulties at the start of the competition.
We weren’t able to connect properly to Waterloo’s contest software from UVic because of firewall issues. We ended up having to connect through VNC and transfer files for submission via scp. It wasn’t until 80 minutes into the contest before the guys could submit the first few problems that they had solved.
It was a pretty good problem set. There were five relatively easy problems requiring simple implementation or some kind of bruteforce. The guys probably started on the second easiest problem rather than the easiest. Most teams started with problem A, which Dan eventually did in just a few minutes, but he didn’t realize how easy it was at the beginning. Without the contest software connection issues, the guys probably would have had three problems solved in the first hour.
Things slowed down a bit after those first three as Dan tried a bruteforce attempt on problem H, which resulted in a time limit exceeded. He then went on to work on problem E and Scott coded problem G and had it accepted with about 10 minutes left.
There were a few other problems that looked reasonable. I wrote a solution to problem J this morning, which can be solved with backtracking and branch bounds when you can’t possibly improve on your best result. A lot of teams solved H, but I have not been able to come up with an algorithm fast enough for the bounds of the problem. There were also two graph problems, which most of the top teams did.
Waterloo solved 10 of 11 problems, which is quite impressive. They are typically one of the best teams in the world, so it’s not surprising. I hope I can get all three members of the team to compete in one of Waterloo’s weekend practices before I leave for Asia in March.
