I regularly compete in the US Computing Olympiad online challenges. There are three levels of competition, bronze, silver, and gold, each with more difficult problems than the last. In order to move up a level, a competitor must achieve a set score in the current level. This week, I advanced from silver to gold by getting a score of 867 out of 1000. I also placed 16th out of 193 high school competitors.
The problems in this competition were really interesting because I was able to apply some of the knowledge I've gained from my Coursera classes. I solved the first problem with a recursive flood fill approach. The recursive, divide-and-conquer paradigm is something the Stanford Design and Analysis of Algorithms class covers extensively. The second problem involved finding the minimum variable that would result in a set of points being connected beyond a certain threshold. I used an optimized union-find data structure to connect the points and check how many were connected in total. This is a technique I learned in my Princeton Algorithms class.
The last problem was really interesting. It required finding the minimum time a set of tasks could be accomplished in, given a set of dependencies. The hard part is that the dependencies had dependencies, and one task might be a dependency for several other tasks. Since the solution has to run in a very short time in order to be judged correct, I couldn't simply calculate the time a task would take each time it was listed as a dependency. Instead, I used a dynamic programming approach, and cached the times of tasks, taking its dependencies into account, when it was first calculated. That way, my program never did the same work twice. I got full points for my solution.
