June 29, 2018 GitHub Repositories With Competitive Programming Libraries
Everyone who has participated in algorithm competitions for at least a year knows that some algorithms and data structures frequently appear in problems\solutions. Segment tree, treap, LCA calculation, Knuth-Morris-Pratt algo – you get used to implementing them.
Some problems require more advanced algorithms: max flows, suffix trees, hardcore geometry. Those are harder to code.
It is most likely that you wouldn’t find these algorithms in the standard library of your favorite language. Luckily, experienced competitive programmers create their own libraries and share them open-source on GitHub!
Why do they write these libraries? Here are my guesses:
- You can think about performance and reusability of the code beforehand. Drink a cup of coffee, get that 2x speedup without the rush of a contest;
- Reimplementing every algorithm from scratch requires debugging. Personally, if I code segment tree correct the first time, I am very surprised. Debugging takes time, which is crucial in a contest like a Topcoder SRM;
- Some algorithms are just too hard to understand and you don’t need them that often. E.g. simplex method. Write it once and use it as many times as you want!
There are quite a few GitHub repositories with prewritten algorithm\data structure code that you can use. I explored some of them with the intention of sharing my knowledge with others.
Please be aware that according to this topic, any code that you use in a Topcoder SRM must be written entirely by you!
Cheer up though because you can create your own library!
Repositories sorted by latest commit time:
Interestingly, some libraries were prepared by ACM ICPC world finalists. And others were written by mere enthusiasts like you and me!
Don’t be scared by the number of characters. Some repos also contain solutions to various programming contests. Some repos contain tests along with the code. Also, Java is naturally more verbose than other languages.
Speaking about languages, C++ is the most popular.
Distribution of repos by programming language:
– C++ 17
– Java 5
– C# 2
– CoffeeScript 1
– Swift 1
– Python 1
– Objective-C 1
– Scala 1
– Go 1
Personally, I like short and concise code that can be easily copy-pasted, i.e. one function or one class, without any comments. However, if you browse the repos above, you will certainly find the representation that suits you and your needs.