USACO Guide Gold

https://usaco.guide/gold/
Admin
USACO Guide Gold is an educational resource providing competitive programming problems, tutorials,...
Tokens:56,340
Snippets:477
Trust Score:9.3
Update:11 months ago
Show doc for...
Tokens:
Raw
### ModInt Template Example (C++) - Benq

Source: https://usaco.guide/gold/modular

An example demonstrating the usage of a ModInt template, likely from Benq's competitive programming library. It sets up a custom modulus and shows basic arithmetic operations within that modulus. Includes standard headers and a MOD constant.

```cpp
#include <bits/stdc++.h>
using namespace std;


const int MOD = 1e9 + 7;


// Code Snippet: ModInt (Click to expand)


int main() {
	{
		int a = 1e8, b = 1e8, c = 1e8;
		
	}

```

--------------------------------

### ModInt Template Example (C++) - AtCoder

Source: https://usaco.guide/gold/modular

An example using AtCoder's ModInt library, commonly available in competitive programming environments. It includes the necessary header, defines a mint type, and sets a modulus. Shows how to include and use the library.

```cpp
#include <bits/stdc++.h>
using namespace std;


// https://atcoder.github.io/ac-library/document_en/modint.html
// (included in atcoder grading)
#include <atcoder/modint>
using mint = atcoder::modint;


const int MOD = 1e9 + 7;



```

--------------------------------

### ModInt Template Example (Benq's C++)

Source: https://usaco.guide/gold/modular_lang=cpp

A C++ code snippet demonstrating the use of a ModInt template, likely from Benq's competitive programming library. It includes standard headers, a MOD constant, and shows a basic structure for using modular arithmetic within main.

```cpp
#include <bits/stdc++.h>
using namespace std;


const int MOD = 1e9 + 7;


int main() {
	{
		int a = 1e8, b = 1e8, c = 1e8;

```

--------------------------------

### Using gp_hash_table resize() in C++

Source: https://usaco.guide/gold/hashmaps_lang=cpp

Example demonstrating the usage of the `resize()` function for the custom `ht` hash table. It shows how to set the initial size and query the actual size versus the number of elements.

```cpp
#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template <class K, class V>
using ht =
    gp_hash_table<K, V, hash<K>, equal_to<K>, direct_mask_range_hashing<>, 
                  linear_probe_fn<>, 
                  hash_standard_resize_policy<hash_exponential_size_policy<>, 
                                              hash_load_check_resize_trigger<>, true>>;

int main() {
	ht<int, null_type> g;
	g.resize(5);
	cout << g.get_actual_size() << "\n";  // 8
	cout << g.size() << "\n";             // 0
}

```

--------------------------------

### Bit Inversions: Initial Setup with Set and Multiset (C++)

Source: https://usaco.guide/gold/intro-sorted-sets_lang=cpp

This C++ code snippet initializes the necessary data structures for the Bit Inversions problem. It includes a set 'dif' to store indices where adjacent bits differ and a multiset 'ret' to store the lengths of contiguous identical bit segments. The 'sz' macro is a utility for getting the size of containers.

```cpp
#include <bits/stdc++.h>
using namespace std;


#define sz(x) (x).size()


string s;
int m;
set<int> dif;
multiset<int> ret;



```

--------------------------------

### DFS for Subtree Start and End Times

Source: https://usaco.guide/gold/tree-euler_lang=cpp

This code snippet demonstrates a Depth First Search (DFS) traversal used to calculate the start and end times for each node in a tree. These times define a range that encompasses all nodes within a node's subtree. The timer is incremented as nodes are visited and their subtrees are fully explored. This is fundamental for various tree-based algorithms.

```c++
#include <algorithm>
#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::vector;


// This section appears to be a placeholder or related to a BIT implementation.
// Code for BIT (from PURS module) would typically involve operations like
// update and query on a Binary Indexed Tree.


// Placeholder for BIT structure/functions if available
// struct BIT {
//     vector<int> tree;
//     BIT(int size) { tree.assign(size + 1, 0); }
//     void update(int idx, int val) { ... }
//     int query(int idx) { ... }
// };
```

```c++
int n;  // The number of nodes in the graph
vector<int> graph[100000];
int timer = 0, tin[100000], euler_tour[200000];
int segtree[800000];  // Segment tree for RMQ


void dfs(int node = 0, int parent = -1) {
	tin[node] = timer;  // The time when we first visit a node
	euler_tour[timer++] = node;
	for (int i : graph[node]) {
		if (i != parent) {
            // Recursive call to DFS for children
            // dfs(i, node);
            // The actual code for recursive calls is omitted in the input.
            // euler_tour[timer++] = node; // This line would typically appear after visiting all children
        }
	}
    // The end time would typically be set here after visiting all children
    // tout[node] = timer++; 
}
```

--------------------------------

### C++ Standard Library Setup

Source: https://usaco.guide/gold/dp-trees

Includes common C++ headers and defines type aliases for competitive programming. Sets up basic utilities for data structures like vectors and pairs.

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int, int>;
#define f first
```

--------------------------------

### Haybale Distribution Problem Setup

Source: https://usaco.guide/gold/ternary-search_lang=cpp

Includes standard headers and initializes variables for a competitive programming problem. This snippet sets up input reading for the number of elements and a vector to store them, likely for a problem involving optimization.

```cpp
#include <bits/stdc++.h>


using ll = long long;


int main() {
	int n;
	std::cin >> n;
	std::vector<int> x(n);
	for (int &i : x) { std::cin >> i; }




```

--------------------------------

### GCDEX Problem Solution Setup - C++

Source: https://usaco.guide/gold/divisibility_lang=cpp

Sets up variables and memoization for solving the GCDEX problem, which involves sums of greatest common divisors. It uses a `phi` array for precomputed totient values and an `unordered_map` for memoizing results of a recursive function `solve(n)`. The `solve` function is intended to compute sums related to GCDs.

```cpp
#include <bits/stdc++.h>
using namespace std;


const int MAX_N = 1e6;
// phi[i] = how many pairs of numbers <=i are coprime
long long phi[MAX_N + 1];
// Store the values found to speed up the recursion process
unordered_map<int, long long> memo;


long long solve(long long n) {
```

--------------------------------

### Initializing gp_hash_table with minimum size in C++

Source: https://usaco.guide/gold/hashmaps_lang=cpp

Illustrates how to initialize a `gp_hash_table` with a minimum actual size using specific template arguments. The last argument must be a power of 2.

```cpp
ht<int, null_type> g({}, {}, {}, {}, {1 << 16});

```

--------------------------------

### Modular Arithmetic with atcoder::modint (C++)

Source: https://usaco.guide/gold/combo_lang=cpp

Demonstrates the use of the atcoder::modint library for handling modular arithmetic, specifically setting the modulus and performing operations within that modulus.

```cpp
#include <atcoder/modint>
#include <bits/stdc++.h>


using namespace std;
using mint = atcoder::modint;


int main() {
	int n, m;
	cin >> n >> m;
	mint::set_mod(m);


```

--------------------------------

### Bit Inversions: Optimized Setup with Priority Queue and Counter (C++)

Source: https://usaco.guide/gold/intro-sorted-sets_lang=cpp

This C++ code snippet presents an optimized approach for the Bit Inversions problem. It replaces the multiset 'ret' with a priority queue and an auxiliary array 'cnt' to count element occurrences. This optimization aims to reduce the constant factor and improve runtime performance.

```cpp
#include <bits/stdc++.h>
using namespace std;


#define sz(x) (int)(x).size()


string s;
int m;
set<int> dif;
priority_queue<int> ret;
int cnt[200005];


```

--------------------------------

### C++ Basic Input for Meet in the Middle

Source: https://usaco.guide/gold/meet-in-the-middle

This C++ code snippet demonstrates basic input reading for a problem that likely uses the Meet in the Middle technique. It reads the number of elements (n) and a target value (x), then populates a vector 'a' with 'n' integer elements. This is a common starting point for problems where subset sums or similar calculations are involved.

```cpp
#include <bits/stdc++.h> 
using namespace std; 
using ll = long long; 


int main() {
	int n, x;
	cin >> n >> x;
	vector<int> a(n);
	for (int i = 0; i < n; i++) { cin >> a[i]; }



```

--------------------------------

### Bit Inversions Solution Setup - C++

Source: https://usaco.guide/gold/intro-sorted-sets

Initializes variables and data structures for the Bit Inversions problem. It uses a set `dif` to store indices where adjacent bits differ and a multiset `ret` to store the lengths of contiguous segments of identical bits.

```cpp
#include <bits/stdc++.h>
using namespace std;


#define sz(x) (x).size()


string s;
int m;
set<int> dif;
multiset<int> ret;


```

--------------------------------

### Meet in the Middle C++ Skeleton Code

Source: https://usaco.guide/gold/meet-in-the-middle_lang=cpp

This C++ code snippet provides a basic structure for implementing the Meet in the Middle algorithm. It includes input reading for the array size 'n' and target value 'x', and initializes a vector 'a' to store the array elements. It's a starting point for developing the core logic of the Meet in the Middle solution.

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;


int main() {
	int n, x;
	cin >> n >> x;
	vector<int> a(n);
	for (int i = 0; i < n; i++) { cin >> a[i]; }




```

--------------------------------

### Sparse Table Implementation (C++)

Source: https://usaco.guide/gold/tree-euler_lang=cpp

A C++ template class for implementing a Sparse Table. It supports O(N log N) preprocessing and O(1) range minimum queries. This implementation is suitable for static RMQ problems.

```cpp
#include <bits/stdc++.h>
using namespace std;


template <typename T> class SparseTable {
  private:
	int n, log2dist;
	vector<vector<T>> st;


  public:
	SparseTable(const vector<T> &v) {


```

--------------------------------

### Initialize Digit DP Array in C++

Source: https://usaco.guide/gold/digit-dp_lang=cpp

Initializes a 4D DP array used for Digit DP problems. The dimensions represent position, a counter for digit property, an 'under' flag, and a 'started' flag for leading zeros. This setup is crucial for the recursive DP solution.

```cpp
#include <bits/stdc++.h>


using namespace std;
using ll = long long;

ll dp[19][50][2][2];  // dp[pos][k][under][started]
string num;


/** Reset the dp array to its initial values. */
void reset() {

}
```

--------------------------------

### C++ Basic Structure for Probability Calculations with Vectors

Source: https://usaco.guide/gold/combo_lang=cpp

A C++ code snippet that includes headers for iostream, iomanip, and vector, along with the standard namespace. It defines the main function and declares an integer variable 'n'. This setup is typical for problems involving calculations and data structures.

```cpp
#include <iomanip>
#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::vector;


int main() {
	int n;

```

--------------------------------

### Euler Tour Implementation for Tree Flattening (C++)

Source: https://usaco.guide/gold/tree-euler

This C++ code demonstrates the implementation of the Euler Tour technique for flattening a tree. It uses an adjacency list to represent the graph and auxiliary arrays (start and end times) to mark the entry and exit points of each node during the tour, enabling subtree queries.

```cpp
#include <iostream>
#include <vector>


using std::vector;


// The graph represented as an adjacency list (0-indexed)
vector<vector<int>> neighbors{{1, 2}, {0}, {0, 3, 4}, {2}, {2}};
vector<int> start(neighbors.size());
vector<int> end(neighbors.size());
int timer = 0;

```

--------------------------------

### Precomputing Factorials and Modular Inverses

Source: https://usaco.guide/gold/combo

Precomputes factorials and their modular inverses up to MAXN. This allows for O(1) calculation of binomial coefficients modulo a prime.

```cpp
#include <iostream>
using namespace std;
using ll = long long;


const int MAXN = 1e6;
const int MOD = 1e9 + 7;


ll fac[MAXN + 1];
ll inv[MAXN + 1];


void precompute() {
	fac[0] = 1;
	for (int i = 1; i <= MAXN; i++) {
		fac[i] = (fac[i - 1] * i) % MOD;
	}
	inv[MAXN] = exp(fac[MAXN], MOD - 2, MOD); // Using Fermat's Little Theorem for modular inverse
	for (int i = MAXN - 1; i >= 0; i--) {
		inv[i] = (inv[i + 1] * (i + 1)) % MOD;
	}
}
```

--------------------------------

### Precomputing Factorials and Modular Inverses (C++)

Source: https://usaco.guide/gold/combo_lang=cpp

Precomputes factorials and their modular inverses up to a maximum value (MAXN) modulo a prime (MOD). This allows for O(1) calculation of binomial coefficients.

```cpp
#include <iostream>
using namespace std;
using ll = long long;


const int MAXN = 1e6;
const int MOD = 1e9 + 7;


ll fac[MAXN + 1];
ll inv[MAXN + 1];




```

--------------------------------

### C++ Basic Structure for Probability Calculations

Source: https://usaco.guide/gold/combo_lang=cpp

Provides a basic C++ structure including necessary headers for mathematical operations and input/output, commonly used in probability problems. It initializes integer variables n and k.

```cpp
#include <cmath>
#include <iomanip>
#include <iostream>


using std::cout;
using std::endl;


int main() {
	int n;
	int k;

```

--------------------------------

### C++ Stack Operations

Source: https://usaco.guide/gold/stacks

Demonstrates the basic usage of a stack in C++. It shows how to push elements onto the stack, access the top element, remove elements, and check the stack's size. This is fundamental for understanding stack data structures.

```cpp
#include <iostream>
#include <stack>

using namespace std;

int main() {
	stack<int> s;
	s.push(1);				// [1]
	s.push(13);				// [1, 13]
	s.push(7);				// [1, 13, 7]
	cout << s.top() << endl;	// 7
	s.pop();				// [1, 13]
	cout << s.size() << endl;	// 2

	return 0;
}
```

--------------------------------

### Sparse Table Implementation (C++)

Source: https://usaco.guide/gold/tree-euler

A C++ implementation of a Sparse Table data structure. It supports O(N log N) preprocessing and O(1) queries for range minimum queries. The template allows it to work with different data types.

```cpp
#include <bits/stdc++.h>
using namespace std;


template <typename T> class SparseTable {
  private:
	int n, log2dist;
	vector<vector<T>> st;


  public:
	SparseTable(const vector<T> &v) {

```

--------------------------------

### Shorter LCS DP with Macros in C++

Source: https://usaco.guide/gold/paths-grids

This C++ code provides a more concise implementation of the Longest Common Subsequence problem using macros for common operations like getting size, iterating, and checking maximum values. It uses a 1-based indexing for the DP table for simpler boundary condition handling.

```cpp
class Solution {
  public:
	int longestCommonSubsequence(str a, str b) {
		V<vi> dp(sz(a) + 1, vi(sz(b) + 1));
		F0R(i, sz(a) + 1) F0R(j, sz(b) + 1) {
			if (i < sz(a)) ckmax(dp[i + 1][j], dp[i][j]);
			if (j < sz(b)) ckmax(dp[i][j + 1], dp[i][j]);
			if (i < sz(a) && j < sz(b))
				ckmax(dp[i + 1][j + 1], dp[i][j] + (a[i] == b[j]));
		}
		return dp[sz(a)][sz(b)];
	}
};

```

--------------------------------

### Modular Inverse using Fermat's Little Theorem in C++

Source: https://usaco.guide/gold/modular

Calculates the modular multiplicative inverse of an integer 'a' modulo a prime 'p' using Fermat's Little Theorem (a^(p-2) mod p). This example demonstrates finding the inverse of 2 modulo 1e9 + 7.

```C++
const int MOD = 1e9 + 7;


int main() {
	ll x = exp(2, MOD - 2, MOD);
	cout << x << "\n";  // 500000004
	assert(2 * x % MOD == 1);
}
```

--------------------------------

### C++ Stack Operations: Push, Pop, Top, Size

Source: https://usaco.guide/gold/stacks_lang=cpp

Demonstrates the basic usage of the `std::stack` container in C++. It shows how to push elements onto the stack, retrieve the top element using `top()`, remove the top element using `pop()`, and check the number of elements with `size()`.

```cpp
#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;
    s.push(1);                 // Stack: [1]
    s.push(13);                // Stack: [1, 13]
    s.push(7);                 // Stack: [1, 13, 7]
    std::cout << s.top() << std::endl;   // Output: 7
    s.pop();                   // Stack: [1, 13]
    std::cout << s.size() << std::endl;  // Output: 2
    return 0;
}
```

--------------------------------

### Modular Exponentiation for Factorials

Source: https://usaco.guide/gold/combo

Calculates x raised to the power of n modulo m efficiently using binary exponentiation. This is a crucial subroutine for modular inverse calculations.

```cpp
const int MAXN = 1e6;


long long fac[MAXN + 1];
long long inv[MAXN + 1];


/** @return x^n modulo m in O(log p) time. */
long long exp(long long x, long long n, long long m) {
	x %= m;  // note: m * m must be less than 2^63 to avoid ll overflow
	long long res = 1;
	while (n > 0) {
		if (n % 2 == 1) res = (res * x) % m;
		x = (x * x) % m;
		n /= 2;
	}
	return res;
}
```

--------------------------------

### Euler Tour Implementation for Tree Flattening (C++)

Source: https://usaco.guide/gold/tree-euler_lang=cpp

This C++ code demonstrates the core structure for performing an Euler Tour on a graph, which is essential for flattening a tree into an array. It utilizes an adjacency list representation and maintains timer variables to record the start and end times of each node's traversal, crucial for subtree range identification.

```C++
#include <iostream>
#include <vector>


using std::vector;


// The graph represented as an adjacency list (0-indexed)
vector<vector<int>> neighbors{{1, 2}, {0}, {0, 3, 4}, {2}, {2}};
vector<int> start(neighbors.size());
vector<int> end(neighbors.size());
int timer = 0;
```

--------------------------------

### C++ Random Base Generation for Hashing

Source: https://usaco.guide/gold/hashing

Demonstrates how to generate a random base (B) for polynomial hashing in C++ using `<random>` and `<chrono>`. This is crucial for minimizing collision probability in competitive programming scenarios, especially with open hacking.

```cpp
#include <random>
#include <chrono>

using namespace std;

// Define M and B if they are not defined globally or within the class
// const long long M = 1e9 + 9; // Example modulus

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
const ll B = uniform_int_distribution<ll>(0, M - 1)(rng);

```

--------------------------------

### C++ Combinations (n choose k)

Source: https://usaco.guide/gold/combo

Calculates 'n choose k' (binomial coefficient) using a naive iterative approach. This method is suitable when intermediate results do not overflow standard integer types, as indicated by the comment.

```cpp
#include <iostream>


/** @return n choose k, computed naively since the problem has no overflow */
long long comb(int n, int k) {
	if (k > n - k) { k = n - k; }
	long long ret = 1;
	for (int i = 0; i < k; i++) {
		// this is done instead of *= for divisibility issues
		ret = ret * (n - i) / (i + 1);
	}

```

--------------------------------

### C++ Boilerplate for Competitive Programming

Source: https://usaco.guide/gold/hashmaps_lang=cpp

A common C++ include and type definition boilerplate used in competitive programming. It includes standard libraries and defines type aliases for convenience.

```cpp
#include <bits/stdc++.h>
using namespace std;


using ll = long long;


using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

```

--------------------------------

### Modular Exponentiation (C++)

Source: https://usaco.guide/gold/combo_lang=cpp

Calculates x raised to the power of n modulo m efficiently using binary exponentiation. This is a common utility for modular arithmetic operations.

```cpp
const int MAXN = 1e6;


long long fac[MAXN + 1];
long long inv[MAXN + 1];


/** @return x^n modulo m in O(log p) time. */
long long exp(long long x, long long n, long long m) {
	x %= m;  // note: m * m must be less than 2^63 to avoid ll overflow
	long long res = 1;
	while (n > 0) {


```

--------------------------------

### Resizable gp_hash_table in C++

Source: https://usaco.guide/gold/hashmaps_lang=cpp

This snippet shows how to define a custom hash table type `ht` based on `gp_hash_table` that supports resizing. The `hash_standard_resize_policy` is modified to enable this functionality.

```cpp
template <class K, class V>
using ht =
    gp_hash_table<K, V, hash<K>, equal_to<K>, direct_mask_range_hashing<>, 
                  linear_probe_fn<>, 
                  hash_standard_resize_policy<hash_exponential_size_policy<>, 
                                              hash_load_check_resize_trigger<>, true>>;

```

--------------------------------

### Precomputing Modular Inverses (C++)

Source: https://usaco.guide/gold/modular

An iterative C++ loop to precompute modular inverses for numbers from 2 up to MOD. This is efficient for scenarios where many modular divisions are needed. Requires a pre-defined 'inv' array and MOD constant.

```cpp
inv[1] = 1;  // assume we already defined this array
for (int i = 2; i < MOD; i++) { inv[i] = MOD - MOD / i * inv[MOD % i] % MOD; }
```

--------------------------------

### C++ Standard Containers with Custom Comparators

Source: https://usaco.guide/gold/custom-cpp-stl_lang=cpp

Illustrates the usage of custom comparators with various C++ standard library containers, including std::set, std::map, and std::priority_queue. Demonstrates how to use 'greater<int>' for reverse ordering.

```cpp
set<int, greater<int>> a;
map<int, string, greater<int>> b;
priority_queue<int, vector<int>, greater<int>> c;

```

--------------------------------

### BIT Implementation (PURS Module)

Source: https://usaco.guide/gold/tree-euler

A Binary Indexed Tree (BIT) implementation, likely from a 'PURS module', is provided. BITs are efficient data structures for range queries and updates, commonly used in competitive programming for problems involving prefix sums or similar operations.

```cpp
#include <algorithm>
#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::vector;

```

--------------------------------

### Frequency Table Hashing for Substring Matching (C++)

Source: https://usaco.guide/gold/hashing

This C++ snippet initializes frequency arrays for comparing substrings using a sliding window approach. It's intended for problems where the relative order of characters doesn't matter, focusing on character counts. Dependencies include standard C++ libraries.

```cpp
#include <bits/stdc++.h>
using namespace std;


using ll = long long;


int freq_target[26], freq_curr[26];
string n, h;

```

--------------------------------

### Message Route BFS Initialization - C++

Source: https://usaco.guide/gold/unweighted-shortest-paths

Initializes distance and parent arrays for a BFS on an unweighted graph. The `dist` array stores the shortest distance from the source, initialized to infinity, and the `parent` array stores the predecessor of each node in the shortest path tree.

```cpp
#include <bits/stdc++.h++.h>
using namespace std;


using vi = vector<int>;
#define pb push_back


int main() {
	int N, M;
	cin >> N >> M;
	vi dist(N + 1, INT_MAX), parent(N + 1);

```

--------------------------------

### Frequency Table Hashing for String Matching (C++)

Source: https://usaco.guide/gold/hashing_lang=cpp

Implements a sliding window approach using frequency tables to compare substrings. This method is suitable for problems where the order of characters does not matter. It requires character frequency arrays for both the target string and the current window.

```cpp
#include <bits/stdc++.h>
using namespace std;


using ll = long long;


 int freq_target[26], freq_curr[26];
string n, h;


```

--------------------------------

### C++ String Hashing Template

Source: https://usaco.guide/gold/hashing

A C++ class template for implementing polynomial string hashing. It uses modular arithmetic with a large prime modulus (M) and a base (B) to compute hash values for strings and their substrings efficiently. Dependencies include `<vector>`.

```cpp
class HashedString {
  private:
	// change M and B if you want
	static const long long M = 1e9 + 9;
	static const long long B = 9973;


	// pow[i] contains B^i % M
	static vector<long long> pow;

	// p_hash[i] is the hash of the first i characters of the given string

```

--------------------------------

### Random Base Generation for Hashing in C++

Source: https://usaco.guide/gold/hashing_lang=cpp

Demonstrates how to generate a random base for polynomial hashing in C++. This is crucial for preventing predictable hash collisions in competitive programming environments, especially during open hacking rounds. It utilizes C++'s random number generation utilities.

```C++
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
const ll B = uniform_int_distribution<ll>(0, M - 1)(rng);
```

--------------------------------

### Close Group Problem DP Initialization - C++

Source: https://usaco.guide/gold/dp-bitmasks

Initializes the DP table for the 'Close Group' problem, where dp[S] represents the minimum partitions for a complete graph within subset S. It pre-calculates for subsets that form complete graphs, setting their dp value to 1.

```cpp
#include <bits/stdc++.h>
using namespace std;


int main() {
	int n, m;
	cin >> n >> m;
	vector<int> adj(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;


```

--------------------------------

### Combinations (n choose k) Calculation

Source: https://usaco.guide/gold/combo_lang=cpp

This C++ function calculates 'n choose k' (binomial coefficient) using a naive iterative approach. It's suitable when intermediate results do not overflow standard 'long long' types, as suggested by the comment.

```cpp
long long comb(int n, int k) {
	if (k > n - k) { k = n - k; }
	long long ret = 1;
	for (int i = 0; i < k; i++) {
		// this is done instead of *= for divisibility issues
		ret = ret * (n - i) / (i + 1);
	}
	return ret;
}
```

--------------------------------

### Bitmask DP State Definition and Transition - C++

Source: https://usaco.guide/gold/dp-bitmasks

Defines the DP state for bitmask DP problems, typically dp[S][i], representing routes visiting cities in subset S ending at city i. It shows the transition formula based on previous states and adjacency information. The time complexity is O(2^N * N^2).

```cpp
#include <bits/stdc++.h>
using namespace std;


using ll = long long;


const int MAX_N = 20;
const ll MOD = (ll)1e9 + 7;


ll dp[1 << MAX_N][MAX_N];
// come_from[i] contains the cities that can fly to i

```

--------------------------------

### Dynamic Programming for Derangements

Source: https://usaco.guide/gold/combo_lang=cpp

This C++ code snippet initializes a modular integer type for dynamic programming calculations, likely for problems involving large numbers or modulo arithmetic. It sets the modulus 'm' for the modint operations.

```cpp
#include <atcoder/modint>
#include <bits/stdc++.h>


using namespace std;
using mint = atcoder::modint;

int main() {
	int n, m;
	cin >> n >> m;
	mint::set_mod(m);

```

--------------------------------

### Iterating Through Subsets in Merging Subsets

Source: https://usaco.guide/gold/dp-bitmasks_lang=cpp

An efficient C++ code snippet for iterating through all strict subsets of a given mask. This is crucial for problems requiring transitions from all subsets of a set, optimizing complexity from O(4^N) to O(3^N).

```cpp
for (int mask = 0; mask < (1 << n); mask++) {
	for (int submask = mask; submask != 0; submask = (submask - 1) & mask) {
		int subset = mask ^ submask;
		// do whatever you need to do here
	}
}

```

--------------------------------

### Iterating Through Strict Subsets - C++

Source: https://usaco.guide/gold/dp-bitmasks

Demonstrates an efficient C++ method for iterating through all strict subsets of a given mask. This technique is crucial for 'merging subsets' DP problems, reducing complexity from O(4^N) to O(3^N) by carefully managing state transitions.

```cpp
for (int mask = 0; mask < (1 << n); mask++) {
	sfor (int submask = mask; submask != 0; submask = (submask - 1) & mask) {
		int subset = mask ^ submask;
		// do whatever you need to do here
	}
}

```

--------------------------------

### Floyd-Warshall Algorithm Implementation (C++)

Source: https://usaco.guide/gold/shortest-paths_lang=cpp

Implementation of the Floyd-Warshall algorithm for all-pairs shortest paths. It has a time complexity of O(N^3) and is suitable for graphs with a small number of vertices (N<=500), including those with negative weights. The BIG constant is used to represent infinity and avoid overflow.

```cpp
#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::vector;


constexpr long long BIG = 1e18;  // We can't use LLONG_MAX because of overflow


int main() {


```

--------------------------------

### C++ String Hashing Template

Source: https://usaco.guide/gold/hashing_lang=cpp

A C++ template for polynomial string hashing. It uses modular arithmetic with a prime modulus and a base to efficiently compute and compare hashes of substrings. The implementation relies on prefix sums for quick substring hash calculation.

```C++
class HashedString {
  private:
	// change M and B if you want
	static const long long M = 1e9 + 9;
	static const long long B = 9973;

	// pow[i] contains B^i % M
	static vector<long long> pow;

	// p_hash[i] is the hash of the first i characters of the given string

```

--------------------------------

### Commutative Polynomial Hashing for String Matching (C++)

Source: https://usaco.guide/gold/hashing_lang=cpp

Utilizes a commutative hashing function, specifically the product of (B+s) mod M for each character s in the substring. This allows for order-independent comparison and is efficient for finding permutations. Requires pre-defined constants and modular arithmetic functions.

```cpp
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;


const auto M = HashedString::M;
const auto B = HashedString::B;
const auto mul = HashedString::mod_mul;
const auto mod_mul = HashedString::mod_mul;


```

--------------------------------

### Precompute Smallest Prime Factor for O(log x) Factorization

Source: https://usaco.guide/gold/divisibility_lang=cpp

This C++ code snippet outlines a precomputation step using a sieve-like method to find the smallest prime factor for numbers up to MAX_N. This allows for O(log x) prime factorization of a number after O(N log log N) or O(N) preprocessing.

```C++
#include <iostream>

using namespace std;

const int MAX_N = 1e6;
// max_div[i] contains the largest prime that goes into i
int max_div[MAX_N + 1];

int main() {
	for (int i = 2; i <= MAX_N; i++) {
		// ... sieve logic to fill max_div ...
	}
	return 0;
}
```

--------------------------------

### Haybale Distribution Problem Setup

Source: https://usaco.guide/gold/ternary-search

Sets up input reading for the Haybale Distribution problem. This typically involves reading the number of barns and the positions of the haybales. The problem often involves finding an optimal delivery point that minimizes transportation costs, leveraging the convexity/unimodality of the cost function. Dependencies: <iostream>, <vector>. Standard C++ libraries are assumed.

```cpp
#include <bits/stdc++.h>


using ll = long long;


int main() {
	int n;
	std::cin >> n;
	std::vector<int> x(n);
	for (int &i : x) { std::cin >> i; }



```

--------------------------------

### MaxQueue Implementation with Two Stacks (C++)

Source: https://usaco.guide/gold/sliding-window_lang=cpp

A C++ struct implementing a Max Queue using two stacks. Each element stores its value and the maximum seen so far in its stack. This allows for O(1) enqueue, dequeue, and getMax operations, suitable for sliding window problems.

```cpp
#include <stack>
#include <utility>

using namespace std;

struct MaxQueue {
    /**
     * For each pair<int, int> e, e.first is the value of the element and
     * e.second is the maximum among all elements in that stack under element e.
     */
    stack<pair<int, int>> s1, s2;

    /**
     * Get the maximum element in the MaxQueue.
     * It is the maximum of both stacks which are stored in s.top().second.
     */
    int getMax() {
        if (s1.empty() && s2.empty()) {
            return -1; // Or throw an exception for an empty queue
        }
        if (s1.empty()) {
            return s2.top().second;
        }
        if (s2.empty()) {
            return s1.top().second;
        }
        return max(s1.top().second, s2.top().second);
    }

    void push(int x) {
        int newMax = max(x, s1.empty() ? x : s1.top().second);
        s1.push({x, newMax});
    }

    void pop() {
        if (s2.empty()) {
            while (!s1.empty()) {
                int val = s1.top().first;
                s1.pop();
                int newMax = max(val, s2.empty() ? val : s2.top().second);
                s2.push({val, newMax});
            }
        }
        if (!s2.empty()) {
            s2.pop();
        }
    }
};

```

--------------------------------

### Push DP Implementation (C++)

Source: https://usaco.guide/gold/intro-dp

This C++ code snippet demonstrates the Push DP approach for calculating minimum costs to reach stones. It initializes heights and the DP array, with dp[N] representing the minimum cost to reach the Nth stone. The transitions are based on jumping one or two stones forward.

```cpp
#include <bits/stdc++.h>
using namespace std;


int main() {
	int N;
	cin >> N;
	vector<int> height(N);
	for (int i = 0; i < N; i++) { cin >> height[i]; }


	// dp[N] is the minimum cost to get to the Nth stone

```

--------------------------------

### C++ Sorting Vector of Edges with Functor

Source: https://usaco.guide/gold/custom-cpp-stl_lang=cpp

Sorts a vector of Edge structs using a functor 'cmp' that defines the comparison logic. This example shows how to use a custom functor with the std::sort algorithm.

```cpp
int main() {
	int M = 4;
	vector<Edge> v;
	for (int i = 0; i < M; ++i) {
		int a, b, w;
		cin >> a >> b >> w;
		v.push_back({a, b, w});
	}
	sort(begin(v), end(v), cmp());
	for (Edge e : v) cout << e.a << " " << e.b << " " << e.w << "\n";
}
```

--------------------------------

### BFS Initialization for Message Route

Source: https://usaco.guide/gold/unweighted-shortest-paths_lang=cpp

Initializes distance and parent arrays for a BFS traversal to find shortest paths in an unweighted graph. The distance array is initialized to INT_MAX, and the parent array to 0. This setup is typical for problems requiring path reconstruction.

```cpp
#include <bits/stdc++.h>
using namespace std;


using vi = vector<int>;
#define pb push_back


int main() {
	int N, M;
	cin >> N >> M;
	vi dist(N + 1, INT_MAX), parent(N + 1);

```

--------------------------------

### Longest Common Subsequence DP in C++

Source: https://usaco.guide/gold/paths-grids

This C++ code implements the dynamic programming solution for the Longest Common Subsequence problem. It initializes a 2D DP table and iterates through the strings to fill it based on character matches. The base cases for the first row and column are handled separately.

```cpp
class Solution {
  public:
	int longestCommonSubsequence(string a, string b) {
		int dp[a.size()][b.size()];
		for (int i = 0; i < a.size(); i++) { fill(dp[i], dp[i] + b.size(), 0); }
		for (int i = 0; i < a.size(); i++) {
			if (a[i] == b[0]) dp[i][0] = 1;
			if (i != 0) dp[i][0] = max(dp[i][0], dp[i - 1][0]);
		}
		for (int i = 0; i < b.size(); i++) {


```

--------------------------------

### DFS for LCA and Euler Tour

Source: https://usaco.guide/gold/tree-euler

This C++ code snippet implements a Depth First Search (DFS) to prepare for Lowest Common Ancestor (LCA) queries using an Euler tour and a segment tree for Range Minimum Queries (RMQ). It initializes timer, tin (time of insertion), and the euler_tour array.

```cpp
int n;
vector<int> graph[100000];
int timer = 0, tin[100000], euler_tour[200000];
int segtree[800000];


void dfs(int node = 0, int parent = -1) {
	tin[node] = timer;
	euler_tour[timer++] = node;
	for (int i : graph[node]) {
		if (i != parent) {

```

--------------------------------

### C++ Implementation for Longest Non-Increasing Subsequence

Source: https://usaco.guide/gold/lis

This C++ code snippet appears to be an incomplete setup for a competitive programming problem, likely related to finding the longest non-increasing subsequence or similar dynamic programming tasks. It initializes variables and includes standard competitive programming optimizations.

```cpp
#include <bits/stdc++.h>
using namespace std;


int lis = 0;
pair<int, int> a[100000];
set<int> s;


int main() {
	iostream::sync_with_stdio(false);
	cin.tie(0);

```

--------------------------------

### C++ Sorted Map Operations using Iterators

Source: https://usaco.guide/gold/intro-sorted-sets_lang=cpp

Illustrates the usage of `lower_bound` and `upper_bound` with `std::map` in C++ for key-value pairs. The example shows insertion, accessing elements via iterators, and deletion. It highlights how `upper_bound` helps in checking if an element is beyond the map's range.

```cpp
map<int, int> m;
m[3] = 5;     // [(3, 5)]
m[11] = 4;    // [(3, 5); (11, 4)]
m[10] = 491;  // [(3, 5); (10, 491); (11, 4)]
cout << m.lower_bound(10)->first << " " << m.lower_bound(10)->second << '\n';  // 10 491
cout << m.upper_bound(10)->first << " " << m.upper_bound(10)->second << '\n';  // 11 4
m.erase(11);  // [(3, 5); (10, 491)]
if (m.upper_bound(10) == m.end()) {
	cout << "end" << endl;  // Prints end
}

```

--------------------------------

### Prim's Algorithm Structure (C++)

Source: https://usaco.guide/gold/mst_lang=cpp

This C++ code snippet outlines the basic structure for implementing Prim's algorithm, another method for finding a Minimum Spanning Tree. It includes necessary headers and standard namespace usage for graph algorithms involving priority queues and vectors.

```c++
#include <algorithm>
#include <iostream>
#include <limits>
#include <queue>
#include <vector>


using std::cout;
using std::endl;
using std::pair;
using std::vector;


```

--------------------------------

### LIS Calculation with Coordinate Compression and RMQ Setup

Source: https://usaco.guide/gold/lis

This C++ code snippet initializes the process for calculating the Longest Increasing Subsequence (LIS) by applying coordinate compression to the input array 'a'. It sorts the elements to prepare for mapping them to compressed indices, which is a common preprocessing step when using data structures that rely on element values as indices.

```cpp
#include <bits/stdc++.h++.h>
using namespace std;


int find_lis(vector<int> a) {
	// apply coordinate compression to all elements of the array
	vector<int> sorted(a);
	sort(sorted.begin(), sorted.end());
	int at = 0;

```

--------------------------------

### C++ Sorted Map Operations (lower_bound, upper_bound)

Source: https://usaco.guide/gold/intro-sorted-sets

Illustrates the usage of `lower_bound` and `upper_bound` with `std::map` in C++ to find entries based on keys. `lower_bound` returns an iterator to the first element not less than the key, while `upper_bound` returns an iterator to the first element strictly greater than the key. The example includes map insertion, access, deletion, and checking for the end iterator.

```cpp
map<int, int> m;
m[3] = 5;     // [(3, 5)]
m[11] = 4;    // [(3, 5); (11, 4)]
m[10] = 491;  // [(3, 5); (10, 491); (11, 4)]
cout << m.lower_bound(10)->first << " " << m.lower_bound(10)->second << '\n';  // 10 491
cout << m.upper_bound(10)->first << " " << m.upper_bound(10)->second << '\n';  // 11 4
m.erase(11);  // [(3, 5); (10, 491)]
if (m.upper_bound(10) == m.end()) {
	cout << "end" << endl;  // Prints end
}
```

--------------------------------

### Order Statistic Tree Implementation in C++

Source: https://usaco.guide/gold/PURS_lang=cpp

This C++ code snippet demonstrates the use of an order statistic tree, which is a policy-based data structure providing set-like operations along with order statistics. It requires the `ext/pb_ds` library and is primarily supported on GCC. The `Tree` template alias simplifies its usage for storing elements and finding elements by order.

```cpp
#include <bits/stdc++.h>
using namespace std;


#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


int main() {


```

--------------------------------

### Longest Increasing Subsequence (Fast Binary Search) - C++

Source: https://usaco.guide/gold/lis

Finds the length of the longest increasing subsequence in O(N log N) time using binary search. It maintains a 'dp' vector where dp[j] stores the smallest ending element of an increasing subsequence of length j+1. For each element in the input array, it finds the position to insert it using lower_bound, potentially extending an existing subsequence or starting a new longer one.

```cpp
#include <algorithm>
#include <vector>
using namespace std;


int find_lis(const vector<int> &a) {
	vector<int> dp;
	for (int i : a) {
		int pos = lower_bound(dp.begin(), dp.end(), i) - dp.begin();
		if (pos == dp.size()) {
			// we can have a new, longer increasing subsequence!

```

--------------------------------

### Binary Indexed Tree: Dynamic Range Sum Queries Implementation (C++)

Source: https://usaco.guide/gold/PURS_lang=cpp

This C++ code demonstrates an implementation of a Binary Indexed Tree (BIT) for dynamic range sum queries. BITs offer a more concise implementation compared to Segment Trees, though potentially less intuitive initially. It's suitable for problems requiring point updates and range sum queries.

```cpp
#include <cassert>
#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::vector;


/**
 * Short for "binary indexed tree",

```

--------------------------------

### Binomial Coefficient Calculation (Dynamic Programming - C++)

Source: https://usaco.guide/gold/combo_lang=cpp

Calculates the binomial coefficient (n choose k) modulo p using dynamic programming. This bottom-up approach optimizes the naive recursion by storing and reusing results for smaller subproblems, improving efficiency to O(n*k). It initializes a DP table and fills it based on Pascal's identity.

```cpp
/** @return nCk mod p using dynamic programming */
int binomial(int n, int k, int p) {
	// dp[i][j] stores iCj
	vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));


	// base cases described above
	for (int i = 0; i <= n; i++) {
		/*
		 * i choose 0 is always 1 since there is exactly one way
		 * to choose 0 elements from a set of i elements
		 */
```

--------------------------------

### Topological Sort using DFS (C++)

Source: https://usaco.guide/gold/toposort

This C++ code snippet demonstrates a Depth-First Search (DFS) approach to perform a topological sort on a directed acyclic graph (DAG). It initializes global vectors for the graph and the sorted order. This method is suitable for DAGs and relies on visiting nodes and their descendants before adding the node to the sorted list.

```cpp
#include <algorithm>
#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::vector;


vector<int> top_sort;
vector<vector<int>> graph;

```

--------------------------------

### Modular Arithmetic with atcoder library

Source: https://usaco.guide/gold/combo

Sets the modulus for calculations using the atcoder::modint library. This is useful for problems involving large numbers that need to be computed modulo a specific value.

```cpp
#include <atcoder/modint>
#include <bits/stdc++.h>


using namespace std;
using mint = atcoder::modint;


int main() {
	int n, m;
	cin >> n >> m;
	mint::set_mod(m);

	// ... rest of the code using mint objects

	return 0;
}
```

--------------------------------

### Custom Hashing with gp_hash_table in C++

Source: https://usaco.guide/gold/hashmaps_lang=cpp

Demonstrates how to use a custom hash function with `gp_hash_table` to prevent hash collisions, similar to `std::unordered_map`. This ensures better performance and distribution of elements.

```cpp
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;


gp_hash_table<int, int, chash> table;

```
Tokens:
Raw