r/algorithms • u/ZenWoR • 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
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
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:
Dynamic programming This is so important. So many problems are either all dp or have a do aspect to it.
Graph algorithms Know DFS, bfs, shortest path, scc, bi connected components, MST. There is more than this but these are a good start
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.
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.
String algorithms Know string hashing, kmp, zvalues, aho corasic, tries, eer tree, suffix arrays
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.
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.
Misc Backtracking, implementation, red herring.
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.