- Know various strategies for inventing test cases and testing programs
- Understand what programming competitions and algorithmic problems are, what's the difference compared to other forms of programming
- Learn about various platforms dedicated to competitive programming, and what opportunities they offer
- Deduce simple upper bounds on a solution's running time and decide if it's fast enough for a given time limit
- Implement brute force solutions with basic recursive backtracking
- Understand the connection between code structure and the logic behind it
- Structuring Code
- Brute-Force Solutions: Always Conceptually Correct (but extremely slow)
- Intuitive "Proofs" are Wrong
- Defining Solution Set
- Search Space (ie. set A)
- Find an element of a set A which satisfies some property
- Find an element of a set A which minimizes/maximizes an objective function
- Find the number of elements of a set A satisfying some property
- Search Space (ie. set A)
- Recursive Backtracking: Code equivalent to N nested for-loops
- Recipe for developing a brute-force solution:
- Identify the search space for a problem
- Design a method to enumerate all elements of the search space
- Recipe for developing a brute-force solution:
- Time Complexity: Estimating the number of unit operations in an algorithm
- Worst Cases
- Big-O Notation
- Always calculate the Big-O asymptotic bound before implementation
- From Theory to Practice: How to make a solution faster
- Focus optimizations on bottlenecks only
- First optimize asymptotically (major gain), if and only if this fails, then further optimize constants (minor gain)
- Know how integers are represented
- Identify places where integer overflow happens
- Know and compare different ways of representing non-integers, including floating point arithmetic
- Handle precision issues when performing basic operations with doubles
- Distinguish common situations when solution could be simplified by replacing doubles with integers
- Apply code structuring to simplify debugging
- Auto-check program correctness by identifying invariants and inserting corresponding assertions
- Understand motivation and strategy for upsolving
- Invent basic greedy solutions and prove their correctness
- Understand what programming language features are most important on competitions
- Know specialties of popular programming languages
- Apply the segment tree data structure to solve problems which require answer queries of certain form
- Subproblems (and recurrence relation on them) are the most important ingredient of a dynamic programming algorithm
- Two common ways of arriving at the right subproblem:
- Analyze the structure of an optimal solution
- Implement a brute-force solution and optimize it
- Recursive vs Iterative
- Recursive Advantages
- May be faster than iterative if not all subproblems need to be solved
- Easier to implement since the subproblem order is implicitly found by the recursion
- Iterative Advantages
- No recursive stack overhead
- Memory optimization to only store the previous and current rows
- Recursive Advantages