competitive-programming

Competitive Programmer's Core Skills by Saint Petersburg State University

Project maintained by claytonjwong Hosted on GitHub Pages — Theme by mattgraham

Week 1: Programming Competitions

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
- 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
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:
1. Analyze the structure of an optimal solution
2. Implement a brute-force solution and optimize it