A week with zero as a divisor

Yandex.Algorithm final round took place online last week (problems in Russian, results, top 5 on the left). Gennady has won the round thanks to a very important quality: he didn't make any bugs in his solutions :) Congratulations!

It was nicely pointed out that I fail to possess this quality for the third year in a row in exactly the same way: by having a bug in problem C.

In 2013, I've submitted C in a hurry without any testing, and it was not a big surprise that it failed. Here's the diff between my submission and the one that passes - as you can see, it's essentially one more corner case not covered by the original submissions:

+    int extraDelta;
...
+            extraDelta = 0;

...

+        if (totalP + 2 + 4 * (n - total) == p && oldTotalP - 2 + 4 * (n - total + 1) == p && total >= 2) {

+            have[id] = false;

+            have[99 * MAX + 100] = true;

+            totalP += 2;

+            extra = n - total;

+            extraDelta = 1;

+            printBoundary();

+            return true;

+        }

...

-            return (r == c && 100-r <= extra);

+            return (r + extraDelta == c && 100-c <= extra);

In 2014, the bug was very stupid, and the best recipe for avoiding its repetition seemed to be simply not making such stupid bugs :) Of course, testing would help tremendously, but the contest format almost rules that out.

-                if (hexamino[r][c] == 1) {

+                if (hexamino[r][c] == sides[1][1][0]) {

This year, the bug is equally stupid, and the fix is equally short:
+            for (int i = 0; i < n; ++i) if (pr[i] == 0) pr[i] = i;

Here's the code snippet where that line makes a difference - its goal is to find any prime divisor for all numbers up to n:
             int n = (int) 1e6;
             int[] pr = new int[n + 1];
             Arrays.fill(pr, 0);
             for (int i = 2; i * i <= n; ++i)
                 if (pr[i] == 0) {
                     pr[i] = i;
                     for (int j = i * i; j <= n; j += i) pr[j] = i;
                 }

A very typical question about programming contests goes like this: do the skills you've learned help you in your job as a software engineer? However, my very ugly snippet above begs for the opposite question: do the skills learned on your job as a software engineer help achieve better results in algorithmic programming competitions?

Here are some ways I could've avoided this bug (and thus would've walked away with some more cash), and I think all of them can be learned in a software engineering job:

• Hardcoding n=1e6 is a bad idea. Had I not done that, I would've noticed the bug on the sample input where n=11 and prime number 11 is actually used in the output. I did have the array up to the value of n from the input at one point, but then changed to the fixed 1e6 boundary to make sure a possible timeout shows immediately on the first testcase.
• Using two different types of special values (pr[i] == 0 and pr[i] == i) to denote the same thing is a bad idea. I should've just filled with pr[i] == i initially.
• The previous issue has appeared because I've initially had the code written with boolean array "pr", then converted it to integer array since I needed any divisor in the solution below. Had I thought the solution through before starting coding, this wouldn't have happened.

But why did all those bugs still happen, despite the 8 year software engineering experience? It seems to be a case of over-confidence to me. I was so confident that I could write the solution for this easy problem quickly, that I didn't think it through, and I've made quick patches without thinking about the consequences. Hopefully this is a lesson learned, both for the next year and for the actual software engineering work!

IOI 2015 took place in Almaty one week earlier (problems, results, top 5 on the left). Congratulations to Jeehak Yoon on the full score and the victory, and to Mikhail Ipatov on the close pursuit! This year's problemset consisted of 4 relatively normal format problems, and two somewhat unusual ones.

The first unusual problem, scales, asked to come up with a strategy to sort 6 coins using a very weird comparison that takes 3 or even 4 coins as inputs and has three possible results of each comparison (see the problem statement for more details). Since the number of coins was extremely small - just 6 - solving this problem boiled down to manually experimenting on your own machine with various comparisons and sets of outcomes that appear, as I understand.

The second unusual problem, towns, challenged one with learning some properties about a hidden tree using a small amount of requests of distances between tree's leaves. This problem also requires one to come up with an algorithm, and the unusual side is the fact that you get to pick which part of input you want to see.

I love that the IOI continues to pick such unusual problems, and hope that they'll continue to do so!

Thanks for reading, and check back soon for this week's summary.

Tweet