Page 3: Essential Algorithms and Data Structures

3. Essential Algorithms and Data Structures

Your ability to solve USACO problems hinges on a solid understanding of various algorithms and data structures. Here\'s what you need to know as a foundation.

3.1. Basic Algorithms

• Brute Force: Trying all possible combinations to find a solution. Useful when N is small (e.g., permutations for N <= 20, simple loops for N <= 1000).

// Sum from 1 to N (Brute Force example)
long long sum = 0;
for (int i = 1; i <= N; ++i) {
    sum += i;
}

• Greedy: Making the locally optimal choice at each step. Doesn\'t always guarantee a global optimum but is effective for certain problems (e.g., coin change, activity selection).
• Binary Search: An efficient algorithm for finding a specific value in sorted data, with a time complexity of O(log N). (e.g., using std::lower_bound, std::upper_bound functions)

// Find value in a sorted vector (Binary Search example)
std::vector<int> arr = {1, 3, 5, 7, 9};
int target = 5;
bool found = std::binary_search(arr.begin(), arr.end(), target); // true

3.2. Fundamental Data Structures

• Arrays / Vectors: The most basic linear data structures. std::vector is more flexible due to its dynamic sizing.
• Maps / Sets:
  • std::map<Key, Value>: Provides fast access to values by key (e.g., counting frequencies of elements).
  • std::set<Value>: Stores a collection of unique elements, not allowing duplicates (e.g., recording visited nodes).
• Queues / Stacks:
  • std::queue: A FIFO (First-In, First-Out) structure, used in Breadth-First Search (BFS).
  • std::stack: A LIFO (Last-In, First-Out) structure, can be used as an auxiliary for Depth-First Search (DFS) implementations.