Well yesterday I took 2 hours off work in the middle of the day to compete. The end result was a “why did I bother”.
The first problem was a really simple prime number search problem. You had to search a range of numbers, and for those numbers that were primes, modulo the prime with a given number. Return the lowest remainder with the highest frequency. Well I wrote the fancy Sieve of Eratosthenes and stuffed it up. Another coder in my room noticed my mistake and found an example case that it failed. At lest it took him three attempts to find it, so he got no gain of points from it.
After some investigation there appears to be a couple of ways of doing the inner loop in the sieve. (Using the same variable naming as in the linked example)
The most obvious is
for( int k = i*2; k <= n; k+= i )
and how the above example code does it, which is faster
for( int k = i*i; k <= n; k+=i )
Which computes from the square up, but when tested they give the same results (tested up to 100,000,000). But my mistake was the loop termination ended at k < n and I initlised the inner loop as int k = i; thus it looked like this.
for( int k = i; k < n; k+=i )
So now at Greig‘s recommendation I’ve written it up the correct way, and I’ll keep it handy for future competitions. Of note is that I wrote my incorrect code faster than
Mark‘s correct code, in a time of 11:21 vs. 14:44. But that’s not much of a victory.
The second problem was about binary trees and was worth 550 points. I really did not know how to solve it, and after reading the post match write-up I still do not understand it, so I’ll have to try the example code, and see how it works. So in the competition I tried implementing a permutations based solution (as this looked like what was happening) but I couldn’t get it to work in time. I even went and found a C++ example, but couldn’t get it to work ether.
To add insult to injury, I challenged another person’s 550 point solution in the challenge phase, and failed.
Final competition result, a score of -25. This put me in 298th equal out of 308 instead of 215th equal if I’d not challenged. So now I’m back in Division II with a ranking score of 1009.