Algorithms and Maths you need to know for hard level competitive programming problems
Several programmers solve a lot of problems of easy level and medium level but they fail to solve hard level problems. Reason is, Hard level problems in competitive programming requires a deep understanding of mathematics and algorithms. Here are a topics you need to know to solve Hard level competitive programming problems.
- Data structures: Maps, Segment tree, Fenwick tree, Heaps,
- Dynamic programing: Many of the problems involving DP have a similar structure, learn several of them.
- Graph algorithms: BFS, DFS, Minimum Spanning tree, Single-source and all-pairs shortest paths, Topological ordering, Maximum flow, Maximum bipartite matching, Min-cost max flow, just to mention a few.
- Geometry: Need to know the concepts and the algorithms. We didn’t know the algorithms by heart (they are very error prone) so we had them in our notes.
- Number theory and combinatorics.
- Asymptotic notation: to be able to determine the complexity of your algorithm.
- String algorithms: KMP for string matching, use of prefix trees, Longest common/increasing subsequence, etc.
- Backtracking
I think that Steven Halim’s competitive programming book is a good place to learn all these concepts. Addintional to this, CLRS and Concerete mathematics are the books you should read.
