CMU High School Programming Competition – Win!
Tue, 11 May 2010
Me and two of my friends decided to team up and take part in the High School Programming Competition at Carnegie Mellon University Qatar this year. So we did, as ‘Team Analog’, and guess what? We won! :D It was great fun! You can see the local newspaper article here (in the picture I’m the guy on the left). If that link is down, you can see a cached version of the article here.
We did seven out of the eight problems. We were hoping to do it all, but we got lazy toward the end and slacked off. :P The question we left was kinda fun though. Basically, it asked ‘how many combinations of 1, 3, 10 and 20 add up to a given number n?’ (the real question involved a ‘story’ about pirates and stuff – Arr!). For example, for n = 10, there are 5 combinations:-
10 * 1, 0 * 3, 0 * 10, 0 * 20
0 * 1, 0 * 3, 1 * 10, 0 * 20
7 * 1, 1 * 3, 0 * 10, 0 * 20
4 * 1, 2 * 3, 0 * 10, 0 * 20
1 * 1, 3 * 3, 0 * 10, 0 * 20
So, after I came home I came up with a really stupid and inefficient way to do it involving storing all the combinations. Yes, silly me. Of course, Kojack on the Ogre forums came up with a better way that takes about 12/th of the time and about (yikes!) 1/17144217.6 times the memory space that mine does for n = 200. Argh. Why didn’t I think of this one? >_>
