Saturday, May 31, 2008

My very first algorithm problem experience

Back in 1997, my Informatics teacher, Yulia Lvovna Vorontsova, has suggested that I participate in Moscow regional (Moscow consists of 10 regions: Central, Northern, Northwestern, Western, ..., Northeastern, and (guess?) Zelenograd) olympiad in informatics.

The olympiad had three problems to offer, but the only one I remember now is: given an integer N not exceeding 10000, output 2 to the power of N.

I've never solved algorithm problems before that olympiad, so everything was new and difficult to me. Luckily, I knew how to read or write files in Pascal. I've solved problems in Pascal then, but I'll use Java for explanations here.

I've thought about keeping an array of digits. This array was fixed-size, and the first element contained the most significant digit (which was always zero, of course, as the size was chosen with a bit of margin). I can reconstruct my code as (this is definitely a very inaccurate reconstruction, but I don't remember much from 11 years ago):
 1: String power(int n) {
2: int[] digits = new int[5000];
3: digits[4999] = 1;
4: for (int i = 0; i < n; ++i) {
5: int p = 0;
6: for (int j = 4999; j >= 0; --j) {
7: int r = p + 2 * digits[j];
8: p = 0;
9: while (r > 10) {
10: p += 1;
11: r -= 10;
12: }
13: digits[j] = r;
14: }
15: }
16: String s = "";
17: for (int i = 0; i < 5000; ++i)
18: if (s.length() > 0 || digits[i] > 0)
19: s += digits[i];
20: return s;
21: }
This code suffers from several common problems (like repeating 5000 and 4999 all over the place), but I'm still amazed how could I get it working in 6th grade.

The rules for that contest were standard IOI-style, that means we've had to write solutions for several problems during the contest, and after the end of contest they were checked on several testcases each, and getting correct answer on each testcase was scored by some amount of points. Of course, the checking was done manually: one of the judges sat next to you and ran your program in command line (it was DOS everywhere at that time) of Norton Commander.

And you know what? The above program passed all testcases but one. The testcases were (not exactly, but the idea should be understandable): 1, 2, 5, 10, 10000. And apparently the answer for 10000 was incorrect. Can you spot the bug in the above code?

Strange, but I remember comparing the correct and wrong answers for that testcase now. The correct answer started with 1995, and my program output something that started with 1994. How could there be such tiny error? Because r > 10 should be r >= 10. Digits of '10' are not good :)

That was my very first problem, and my very first bug. Everything did work out well in the end, as I advanced to Moscow-wide olympiad anyway, and then to Russian olympiad, and then...