Introduction to Competitive Programming (original) (raw)
Selection of USACO problems are limited to those before 2017.
Key Ideas
Example Problems
Additional problems
Topic 0: Introduction
- Know how to perform input/output efficiently in your language.
- Understand overflow
- Topic 0 Problem Set
Slides and Video
Topic 1:
Sums, Prefix Sums, and Difference Arrays
- Sum and prefix sums: For many problems where data is stored in an 1D-array, computing the sum or prefix (or postfix) sums can reduce the complexity from O(n^2) to O(n).
- For some problems, it is necessary to store these sums in another array, requiring O(n) extra memory. For other problems, maintaining a running sum suffices. Some problems requires storing information other than sum of prefix.
- Difference array:�With range updates (changing array A's elements in an range by a constant value), maintaining the array where each element represents difference of two adjacent elements in A makes each update constant time. Some discrete event simulation can be viewed as range updates along the time dimension. Difference array to prefix-sum array is differentiation to integration in calculus.
- Topic 1 Problem Set
Slides and Videos
Playlist on youtube Example Problems
Topic 2:
Histograms, Sets, and Maps
- Histogram:� �A histogram counts the number of times a value appears.� When the values we want to count are integers in a small range, the histogram can be stored using an array.� When the values are in a bigger range, we can use Map to store them.
- Set:� A set an important data structure, it supports efficient addition / removal, while maintaining uniqueness of elements.� An ordered set also enable finding the first / last element.
- Map:� A map stores mappings from keys to values.� It can be viewed as more powerful arrays.� While arrays map integer indices to values, maps can map anything to values.� �
- Topic 2 Problem Set
Slides and Videos
Video playlist Example Problems
LeetCode: Maximum Frequency Stack (Optional)
USACO 2016 December Silver 2 Cities and States
CodeForces: Constructing the Array�(The homework problem Exam Seating under Social Distancing is inspired by and similar to this problem.)
Topic 3:
Introduction to Dynamic Programming
- Dynamic Programming:� � Solving problems using recursion (using solutions to subproblems) and storing solutions of subproblems to avoid recomputation. Key is to figure out the recursion relationship. Sometimes need to define subproblems with more inputs.
- Topic 3 Problem Set
Slides and Videos
Video playlist Example Problems
Topic 4:
Two Pointers and Sliding Window
- Two pointers: One maintains two pointers (indices) into either one array or two arrays, and move the pointers based on values at the pointers.
- Sliding window: A window slides through an array (both ends of the window move along one direction). One maintains a summary of what are in the window, and decides how to slide based on that summary.
- Topic 4 Problem Set
Slides and Videos
Spring 2020 Slides for Topic 4 Example Problems for Summer 2020
LeetCode: Sliding Window Maximum Additional Example Problems from Spring 2020
Topic 5:
Binary Search and Bisection
- Binary Search can be used to efficiently search sorted lists.
- Keep a low and high value for the range that the target value could possibly be in.
- There are multiple ways to write code for binary search that work.
- Bisection is a variant of binary search that solves a monotonic function.
- Topic 5 Problem Set
Slides
Slides from Spring 2020 Example Problems for Summer 2020
Kattis: Slalom 2 Example Problems for Spring 2020
LeetCode: Find First and Last Position of Element in Sorted Array
Cipele: COCI 2018 October Task 3
Topic 6:
Stacks
- A stack is a simple data structure that allows push(), pop() and top()
- Elements are always accessed from the top of the stack, so FILO (first in, last out)
- Used implicitly for implementing function calls, and can be explicitly used for many tasks.
- Useful to remember and undo operations
- Useful to process balanced bracket sequences
- Useful to evaluate expressions, especially Reverse Polish Notation.
- Topic 6 Problem Set
Slides and Videos
Video Playlist on Youtube Example Problems
LeetCode: Valid Parentheses (Req, Stack)
LeetCode: Baseball Game (Req, Stack)
LeetCode: Asteroid Collision (Req, Stack)
Kattis: Even Up Solitaire (2013 ICPC North American Qualifier)
Topic 7: Queues, Deques, and Priority Queues
- Queues are a data structure that allows insertion from one end and removal from the other.
- Most of the time, problems that can be solved with queues can also be solved with a sliding window.
- (We will talk about another method that uses queues, breadth-first search, in Topic 9.)
- Deques are data structures that allow insertion and deletion from both sides.
- Priority queues are data structures that allow for efficient removal of a "highest-priority" element.
- In Java and Python (with heapq), priority queues remove the smallest priority first, while in C++, they remove the largest priority first.
- An easy way to sort a priority queue in the opposite direction is to multiply all priorities by -1.
- Topic 7 problem set
Slides and Videos
Videso on Youtube for Topic 7 Example Problems
Topic 8: DFS
- Depth First Search (DFS) is a general technique to solve lots of problems.
- Use recursion, but mark cells as visited to prevent an infinite loop.
- Topic 8 problem set
Slides and Videos
Summer 2020 Video Playlist on Youtube Example Problems
Topic 9: BFS
- Breadth-first search is a pathfinding method that searches in all possible directions at the same rate.
- It can be seen as opposite to depth-first search, which explores down a single direction as far as possible before backtracking.
- BFS can also be seen as a general-problem solving technique.
- Topic 9 problem set
Slides and Videos
Spring 2020 Video Playlist on Youtube Example Problems
Codeforces: Biridian Forest
Codeforces: Kilani and the Game
Topic 10: Graphs
- A graph is a collection of vertices and edges (connections between vertices).
- Different graph representations (adjacency list and adjacency matrix) have a trade-off: adjacency list is more compact, but adjacency matrix can check if an edge exists in constant time.
- Graph traversals (DFS and BFS) can be applied to all graphs, just as we applied it to specific cases in the previous topics.
- Graph traversals can solve a wide range of problems.
- Topic 10 problem set
Slides and Videos