r/algorithms • • May 07 '19

Useful algorithms for competitive programming (and websites if you have any)

I am competing in programming and I wasn't really into algorithms until last competition. It feels great understanding basic algorithms (like Kadane's or something like that), but which algorithms do you think are really valuable for competitive programming?

Also, do you have any sites where I can learn about algorithms ? :D

134 Upvotes

10 comments sorted by

94

u/sturdyplum May 07 '19

Hey there I competed for 3 years at a collegiate level. Best website for competitions and for blogs is codeforces.com the best book for beginners is competitive programming 3. Depending in what your goals are, different types of competitions have different types of problems. In terms of language there are two main choices. C++ and java. C++ is blazing fast, but it is easier to make mistakes and you will spend longer debugging. Java is slower, and is more verbose but you will make less mistakes. As for algorithms I recommend:

  1. Dynamic programming This is so important. So many problems are either all dp or have a do aspect to it.

  2. Graph algorithms Know DFS, bfs, shortest path, scc, bi connected components, MST. There is more than this but these are a good start

  3. Linear programming These come up quite often and are often the harder problems. Know flow (dinics is the only algorithm you'll need it has a really good runtime compared to other ones and is easy to implement). Know simplex, kind of rare but still important.

  4. Math There is a ton of things here that are important I will name the ones I can remember. Gcd, lcm, fft, crt, factorization, prime seive, fast modular expo, solving linear recurances with fast modular expo, gaussian elimination. Many more.

  5. String algorithms Know string hashing, kmp, zvalues, aho corasic, tries, eer tree, suffix arrays

  6. Data structure Dsu (disjoint set), BIT (Fenwick tree), segment tree, ordered and unordered sets, Cartesian trees (treap). Kinda rare but I've seen dominator trees come up a few times. Stacks, queue, Priority queue, min queue. I'm probably forgetting a ton.

  7. Geometry It's the worst and I hate it. Know dot products, cross products, know trigonometry, know about floating point errors, know convex Hull. Closest points, checking 3 points are colinear, circle circle intersction. There is too many techniques to mention here. These problems tend to be really hard and the code for them tends to be quite long.

  8. Misc Backtracking, implementation, red herring.

  9. Know your complexity Understand how to analyze the run time of your program. Look at the input and try to guess what the run time should be. What I usually go for is under 200 million operations per second. So if the input size is 100,000 I know an n2 is too slow.

I can update this later to be more inclusive since I made this all of the top of my head. Feel free to pm me with any questions. Don't sit down and try to learn all of these at once it won't work. The best way to learn is to pick one thing at a time and spend some time understanding what it does and then solve some problems. You don't need to understand how something works to use it. I have no idea how the fft code I use works I just know what it does.

2

u/ZenWoR May 07 '19

Well if someone answered my question, you did :D Thank you man, I am competing on country-level competition, so this will be useful :D

11

u/TheoryNut May 07 '19

This is a solid comment but regarding your last point: it’s often pretty useful to understand the underlying ideas behind a lot of algos. For example, counting inversions in n log n can be done easily if you understand merge sort pretty deeply (also if you know fenwick tree but IMO the merge sort solution is cleaner). FFT in particular doesn’t generalize to much else so it’s fine to just have code for, but other stuff like DFS trees that are used in graph algos and binary lifting in LCA are really general concepts that get used elsewhere and are helpful to know.

6

u/sturdyplum May 07 '19

Yes I guess I explained that poorly. What I mean is there will be some things that are not worth putting the time into learning why it works. And trying to do so can leave you demotivated and over whelmed. Another example is the Burnside lemma, I know how to use it but the underlying math is not worth knowing (for competitive programming). The more you spend learning the better you will get at knowing what is and what isn't worth learning.

17

u/TheoryNut May 07 '19 edited May 07 '19

cp-algorithms.com is a favorite in the community.

If you're just starting out, here are the categories I'd recommend:

-Algebra Fundamentals/Prime Numbers

-Combinatorics Fundamentals/Techniques (skip Burnside's Lemma; it's cool but pretty advanced)

-Geometry Elementary Operations

-Graph Traversal/Finding Connected Components/Dijkstra's/Dijkstra's On Sparse Graphs/Cycles/Topological Sorting

Feel free to PM me if you have other questions about competitive programming; there's not a very large presence of competitive programmers on Reddit.

4

u/jp_anglais May 08 '19

Antti Laaksonen’s Competitive Programer’s Handbook is a great resource https://cses.fi/book/book.pdf

1

u/[deleted] May 07 '19

Ford-Fulkerson is a good algorithm for network flow.