Competitive programming

Algorithm contests were always a bit of “so what?” for me, but the truth is, I hadn’t really tried to participate in one of them or even tried a few problems more than a couple of hours.

At Christmas, I re-assessed how I spend my free time, and I decided that some changes were in order. Among the changes, I decided I would be doing some programming challenges every week.

I started with good old TopCoder and its ugly UI. I did some practice SRMs and followed a few tutorials to refresh my mind. There are some very nice things about TopCoder:

Plugins

The existence of plugins that auto-generate testcases and the function signature allows you to focus solely on the algorithm. I’m currently using moj as it satifies my needs (it works with any text editor, and works with Java and C++), but I’ve gotten to know the more flexible CHelper. CHelper is for IntelliJ only, but works with more challenges sites: for Codeforces, CodeChef and TopCoder it autogenerates code and grabs the test cases. For any other programming challenge, you can enter the test cases into CHelper (input and output), and it will generate the checking code.

All in all, the pain of manually entering test cases for challenges from sites like HackerRank is alleviated by CHelper, but still the convenience of simply opening a problem in TopCoder and all the information you get is automatically translated into code is pretty sweet.

Tutorials

There are some very nice tutorials provided by members of the community. Assuming you know basic datastructures (read CLRS and/or Skiena’s design manual), I recommend going through the following:

  • Dynamic programming. If you’re confused about DP, first read this Quora answer, then the tutorial.

  • Binary search. Don’t expect the typical binary search on sorted arrays. This tutorial generalizes that algorithm over some ordered search space (vs array) and predicate (vs ≥).

  • Graphs 1, 2 and 3. Good to get the hang of common graph algorithms.

  • Tries. Very simple datastructure that is not that widely taught (I couldn’t find it on CLRS). There are other better tutorials for tries, though.

  • String algorithms. String search is an easy problem to describe, yet efficient algorithms aren’t trivial. I’m reading this one tomorrow.

Do not in any case limit yourself to this sample of tutorials! Take a look at the books I mentioned above and also at the list of tutorials in TopCoder.

Warning: don’t think you’ll just use one algorithm for each problem. Algorithms must be part of your toolbox when solving a challenge. I see these tutorials as presenting algorithm families that you might be able to adapt to solve some parts of the challenges.

Solutions

Another nice thing about TopCoder is the existence of match editorials: summaries about each SRM problem, going from fully implemented solutions to some vague guidelines.

The solutions submitted by other members are also available. From the Arena plugin you can see some solutions, but I found this website to be pretty convenient to see the solutions of the contestants in each SRM.

I recommend only looking at the solutions once you have a working implementation yourself or you are really stuck.

Other competition sites

There are many programming challenges websites, each with its own repository of problems. Each site has its pros and cons, but I’ve decided to stick with TopCoder for the moment as I haven’t really seen any features from other websites that I miss.

Conclusion

The best thing is to dive in and practice often, and when there’s an opportunity to participate on a competition (there’s an SRM weekly), go and try it!

I upload my solutions to GitHub in case you want to check them out.

Comments