Hi all,

I would like to congratulate all participants, but specially to Rick for winning the second problem and for achieve a fantastic performance. From my side, I am happy to have obtained the third position. My trial division algorithm is nothing special, and even when some improvements can double its speed (gross estimation), it is not good enough to beat Rick's solution. Vovanx86 also did a fantastic job, and there are also some very fast solutions who did not get a better result because of correctness problems.

Once again, Congratulation to everybody. Good job:o)


2 posts / 0 new
Last post
For more complete information about compiler optimizations, see our Optimization Notice.

Thank you, Miguel. Congratulations to you and VoVanx86 for placing in the top three in both rounds. You guys consistently submit high quality solutions! My goal for round 2 was merely to place in the top three and earn enough points to remain in the running for the grand prize. These results came as a pleasant surprise.

I believe the key decision was to create a sorted table of perfect powers at initialization time. This reduced the perfect power determination test to a table lookup. Then it was just a matter of finding a search strategy that outperformed binary searching for each sum. I finally hit upon the stride strategy, which used short linear searches and made good use of the data cache and hardware prefetch of the Intel processors. For more on my solution, see my post-mortem and the source code of the stride search function.

krivyakin and wazzupfast also deserve recognition for their fast solutions. As Miguel said, if not for minor correctness problems they would have placed much higher.

The stage is now set for an exciting conclusion in round 3. Good luck, everyone!

- Rick LaMont

Leave a Comment

Please sign in to add a comment. Not a member? Join today