USACO Guide

https://usaco.guide/
Admin
The USACO Guide is a free, comprehensive collection of curated, high-quality resources and problem...
Tokens:370,645
Snippets:3,747
Trust Score:9.3
Update:11 months ago
Show doc for...
Tokens:
Raw
### C++ Main Function with IO Setup

Source: https://usaco.guide/editor_filepath=content%2F1_General%2FContributing

A basic C++ main function that includes a call to a 'setIO()' function, likely for setting up input/output operations. This is a common starting point for competitive programming solutions in C++.

```cpp
int main() {
  setIO();
}
```

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

### Sorting and `next_permutation` Setup (C++)

Source: https://usaco.guide/bronze/complete-rec

Initializes the process for using `next_permutation`. It reads a string `s`, sorts it to ensure lexicographical order, and prepares for iterating through all its permutations. The sorted string is the starting point for `next_permutation`.

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

using namespace std;

int main() {
	string s;
	cin >> s;
	sort(s.begin(), s.end());

	// perms is a sorted list of all the permutations of the given string

	// To generate and process all permutations:
	do {
		// Process the current permutation of s
	} while (next_permutation(s.begin(), s.end()));

	return 0;
}
```

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

### Path Cover Algorithm Setup and Main Function

Source: https://usaco.guide/adv/min-cut_lang=cpp

C++ code demonstrating the setup for a path cover algorithm using TopoSort and Dinic. It includes graph representation and the main function for problem input and processing.

```cpp
TopoSort<500> T;
int n, m;
bool link[500][500];
vi out[500];
Dinic<1005> D;


int main() {
	setIO();
	re(n, m);
	F0R(i, m) {


```

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

### Main Function Setup - C++

Source: https://usaco.guide/plat/hld_lang=cpp

Basic C++ main function setup for competitive programming, including fast I/O operations. This snippet is often a prelude to implementing algorithms like Heavy-Light Decomposition (HLD) and segment trees. It includes standard headers and synchronization disabling for speed.

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


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

```

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

### C++ Short Template for Competitive Programming

Source: https://usaco.guide/general/generic-code_lang=cpp

A minimal C++ template for competitive programming, likely intended for quick setup in contests. It includes a basic `main` function and a call to `setIO()`, which is assumed to handle input/output operations. This template serves as a starting point for more complex programs.

```cpp
int main() { setIO(); }
```

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

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

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

An example demonstrating the use of Benq's ModInt template for modular arithmetic. It includes standard headers and defines a MOD constant.

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

const int MOD = 1e9 + 7;

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

```

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

### Namespace Version Control with Inline Namespaces

Source: https://usaco.guide/editor_filepath=content%2F1_General%2FContests

Demonstrates a practical application of inline namespaces for managing program versions. This example shows how to provide different versions of features and control access to them.

```C++
namespace v1 {
const string buggy_feature = "bugs";
const string greeting = "hi";
}  // namespace v1


inline namespace v2 {
// removed the buggy_feature from this new version
const string buggy_feature = "what buggy feature?";
const string greeting = "hi";
}  // namespace v2


int main() {
	cout << buggy_feature << "\n";      // outputs "what buggy feature?"
	cout << v1::buggy_feature << "\n";  // outputs "bugs"
}
```

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

### C++ Meet in the Middle Problem Setup

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

This C++ code snippet sets up the basic input for a Meet in the Middle problem. It reads the number of elements 'n' and the target value 'x', then populates a vector 'a' with 'n' integers. This is a common starting point for problems utilizing this technique.

```cpp
#include <bits/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\n\nint main() {\n\tint n, x;\n\tcin >> n >> x;\n\tvector<int> a(n);\n\tfor (int i = 0; i < n; i++) { cin >> a[i]; }\n\n\n
```

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

### Example Problem Names

Source: https://usaco.guide/general/working-mdx

Provides examples of `name` fields for problems, showing that the problem name should not include the source and can vary in format, including years and descriptive titles.

```text
2009 - Beetle
Greedy Pie Eaters
Zuma
2014 - The Stables of Genghis Khan
```

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

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

Source: https://usaco.guide/editor_filepath=content%2F4_Gold%2FShortest_Paths

Shows an example of using AtCoder's ModInt library. This header file provides a robust implementation of modular arithmetic types, simplifying complex calculations in competitive programming.

```cpp
#include <iostream>
#include <vector>
#include <atcoder/modint>

int main() {
	const int MOD_VAL = 1e9 + 7;
	using mint = atcoder::modint;
	mint::set_mod(MOD_VAL);

	// Example usage:
	mint a = 10;
	mint b = 5;
	mint result = a * b;

	std::cout << "AtCoder ModInt example: " << result.val() << std::endl;
	return 0;
}
```

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

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

Source: https://usaco.guide/editor_filepath=content%2F4_Gold%2FSliding_Window

Demonstrates using AtCoder's ModInt template for modular arithmetic. This example includes the necessary header and shows how to declare and use `modint` objects. It assumes the AtCoder library is available.

```C++
#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using mint = atcoder::modint;

const int MOD = 1e9 + 7;

int main() {
    mint::set_mod(MOD);
    
    mint a = 100000000, b = 100000000, c = 100000000;
    mint res = a + b * c;
    // std::cout << res.val() << std::endl;

    return 0;
}
```

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

### MDX Frontmatter Example

Source: https://usaco.guide/editor_filepath=content%2F2_Bronze%2FAd_Hoc

This is an example of the frontmatter section in an MDX file. Frontmatter is written in YAML and contains metadata for the module, such as ID, title, description, author, prerequisites, and redirects.

```mdx
---
id: getting-started
title: Getting Started
description: Welcome to the guide! We'll introduce what programming competitions are and how this guide is organized.
author: Nathan Wang
order: 1
prerequisites:
 - Dummy prerequisite
 - running-cpp
redirects:
  - /silver/bipartite
---

# Getting Started
...
```

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

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

Source: https://usaco.guide/editor_filepath=content%2F4_Gold%2FUnweighted_Shortest_Paths

An example showcasing the use of AtCoder's ModInt template for modular arithmetic. This includes the necessary header and namespace setup, demonstrating how to define a modular integer type.

```cpp
#include <iostream>
#include <atcoder/modint>

using mint = atcoder::modint;

int main() {
    // Set the modulus for all mint operations
    mint::set_mod(1e9 + 7);

    mint a(1e8), b(1e8), c(1e8);
    mint result = a + b - c;
    std::cout << result.val() << "\n";

    return 0;
}
```

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

### MDX Frontmatter Example

Source: https://usaco.guide/editor_filepath=content%2F2_Bronze%2FAd_Hoc

An example of the frontmatter structure used in MDX files for editorials. It includes an ID, source, title, and author for each problem editorial.

```markdown
---
id: cses-1621
source: CSES
title: Distinct Numbers
author: Nathan Wang
---

... solution

```

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

### ModInt Template Example (C++)

Source: https://usaco.guide/editor_filepath=content%2F4_Gold%2FSliding_Window

Illustrates the usage of a ModInt template for automatic modular arithmetic. This example is based on Benq's template and shows basic arithmetic operations with numbers that wrap around a modulus. It requires the `bits/stdc++.h` header.

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

const int MOD = 1e9 + 7;

// Assuming ModInt template is defined elsewhere or included
// For demonstration, we'll use a placeholder structure
struct ModInt {
    long long val;
    ModInt(long long v = 0) : val((v % MOD + MOD) % MOD) {}
    ModInt operator+(const ModInt& other) const { return ModInt(val + other.val); }
    ModInt operator*(const ModInt& other) const { return ModInt(val * other.val); }
    // ... other operators
};

int main() {
	{
		ModInt a = 1e8, b = 1e8, c = 1e8;
        ModInt res = a + b * c;
        // std::cout << res.val << std::endl;
	}
    return 0;
}
```

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

### C++ Basic Setup for Dominator Algorithms

Source: https://usaco.guide/adv/critical_lang=cpp

This code snippet sets up the necessary include files and constants for implementing graph algorithms, likely related to dominators. It includes headers for bitsets, input/output streams, and vectors, along with a maximum vertex count.

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


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


const int MAX_N = 1e5;

```

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

### Populate C++ vector with numbers

Source: https://usaco.guide/bronze/intro-ds

This example shows how to create a dynamic array (`std::vector`) in C++ and populate it with a sequence of integers using a loop and the `push_back` method.

```cpp
vector<int> v;
for (int i = 1; i <= 10; i++) { v.push_back(i); }

```

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

### Introduction to Dynamic Programming (DP)

Source: https://usaco.guide/editor_filepath=solutions%2Fplatinum%2Fcses-2079

This example provides a conceptual outline of dynamic programming, often involving recursion with memoization or tabulation. DP is used to solve problems by breaking them down into simpler overlapping subproblems and storing their solutions.

```cpp
// Conceptual example for DP (e.g., Fibonacci)

// Recursive approach (inefficient without memoization)
int fib_recursive(int n) {
    if (n <= 1) return n;
    return fib_recursive(n - 1) + fib_recursive(n - 2);
}

// DP with memoization
#include <vector>

std::vector<int> memo;

int fib_memo(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    
    memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
    return memo[n];
}

// DP with tabulation
int fib_tab(int n) {
    if (n <= 1) return n;
    std::vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
```

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

### C++ Inline Namespace Example

Source: https://usaco.guide/editor_filepath=content%2F1_General%2FContributing

Shows the usage of an inline namespace, allowing direct access to members of the inline namespace without explicit qualification.

```cpp
inline namespace test {
const std::string greeting = "hi";
}
```

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

### C++ BFS Implementation Setup

Source: https://usaco.guide/silver/graph-traversal

Sets up the basic structure for a Breadth-First Search (BFS) in C++. It includes reading the number of nodes and edges from input and preparing the necessary data structures.

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


using namespace std;


int main() {
	int n;
	int m;
	cin >> n >> m;

	// ... adjacency list and BFS queue initialization
```

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

### Wavelet Matrix Initialization (C++)

Source: https://usaco.guide/adv/wavelet_lang=cpp

Basic setup for a Wavelet Matrix implementation. This snippet includes standard C++ headers, input/output optimization, and the declaration of variables for problem size (N) and queries (Q), along with the input array A.

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


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int N, Q;
	cin >> N >> Q;
	vector<int> A(N);

```

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

### Two Pointers Implementation - C++ Setup

Source: https://usaco.guide/silver/two-pointers_lang=cpp

Sets up the necessary includes and variables for a Two Pointers algorithm implementation in C++. It initializes input/output speed and reads the number of elements (N) and a target value (T) for the problem.

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


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);


	int N, T;
	cin >> N >> T;
	vector<int> A(N);

```

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

### Minimum Path Cover Implementation (C++)

Source: https://usaco.guide/adv/min-cut

This snippet shows the setup for solving the Minimum Path Cover problem using TopoSort and Dinic's algorithm. It defines graph structures and the main function entry point.

```cpp
TopoSort<500> T;
int n, m;
bool link[500][500];
vi out[500];
Dinic<1005> D;


int main() {
	setIO();
	re(n, m);
	F0R(i, m) {

```

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

### Initialize Vector in C++

Source: https://usaco.guide/editor_filepath=content%2F3_Silver%2FFlood_Fill

This C++ code snippet demonstrates how to read an integer 'n' and initialize a vector 'v' of size 'n'. It uses standard input/output and the vector library. This is a common pattern for competitive programming problems.

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

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> v(n);

```

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

### C++ Custom Hash Table Resize Example

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

Illustrates the usage of the custom 'ht' hash table, specifically demonstrating the 'resize' function and its effect on the actual size and element count. It shows how resizing rounds up to the nearest power of 2.

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

using namespace __gnu_pbds;

template <class K, class V>
using ht =
gp_hash_table<K, V, std.hash<K>, std.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);
	std::cout << g.get_actual_size() << "\n";  // 8
	std::cout << g.size() << "\n";             // 0
}

```

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

### Message Route BFS Setup - C++

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

Initializes data structures for a BFS to find shortest paths in an unweighted graph. It sets up distance and parent arrays to track path information during the traversal. Dependencies include standard C++ libraries.

```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);

```

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

### C++ CSES Problem Setup - Expected Value

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

This C++ snippet initializes variables 'n' and 'k' for a problem likely involving expected values, possibly from CSES. It includes standard headers for mathematical functions, input/output formatting, and basic I/O operations.

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


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


int main() {
	int n;
	int k;

```

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

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

Source: https://usaco.guide/editor_filepath=content%2F4_Gold%2FShortest_Paths

Demonstrates the usage of a ModInt template, likely from Benq's competitive programming library, for automatic modular arithmetic. This template simplifies operations by handling modulo automatically.

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

// Assuming ModInt template is defined elsewhere
// template <int MOD>
// struct ModInt {
//     long long value;
//     ModInt(long long v = 0) : value(v % MOD) { if (value < 0) value += MOD; }
//     // ... other operators ...
// };

// using mint = ModInt<1000000007>;

const int MOD = 1e9 + 7;

int main() {
	// Placeholder for actual ModInt usage
	// Example of variables that would be of type 'mint'
	int a = 1e8, b = 1e8, c = 1e8;
    std::cout << "Example variables for ModInt: a, b, c";
	return 0;
}
```

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

### Mo's Algorithm - C++ Structure Initialization

Source: https://usaco.guide/plat/sqrt_lang=cpp

This C++ snippet demonstrates the basic structure for defining a query with left and right bounds, and an index. It's a common starting point for implementing Mo's Algorithm.

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

struct Query {
	int l, r, idx;
};

int main() {
	int n;
	cin >> n;

}
```

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

### Inclusion-Exclusion Principle Implementation Example (C++)

Source: https://usaco.guide/plat/PIE_lang=cpp

This C++ code snippet illustrates a basic setup for implementing problems that utilize the Inclusion-Exclusion Principle. It includes necessary headers and defines a constant for the maximum value. This serves as a foundation for problems involving set unions and intersections.

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

using namespace std;

const int VALMAX = 1e7;

int mobius[VALMAX];

int main() {

}
```

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

### C++ Constructor for General Initialization

Source: https://usaco.guide/editor_filepath=content%2F1_General%2FContributing

Demonstrates creating multiple 'Human' objects with initial properties using a constructor and calling a 'condition' function to print their states. This highlights the extensibility of classes with constructors.

```cpp
// Prints out the condition of a human to cout
void condition(Human h) {
	cout << h.get_name() << " feels " << h.get_feeling() << " and is "
	     << h.get_emotion() << endl;
}


int main() {
	Human sal("Sal", 98, 25);
	Human bob("Bob", 100, 9);
	Human joe("Joe", 85, 35);
	// Print out the conditions of all three people
	condition(sal);
	condition(bob);
	condition(joe);
}

```

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

### C++ Namespace Versioning Example

Source: https://usaco.guide/editor_filepath=content%2F1_General%2FDebugging_Checklist

Provides a practical example of using namespaces and inline namespaces for software versioning. It shows how to manage different versions of features, allowing newer versions to be accessed by default while retaining access to older versions.

```cpp
namespace v1 {
	const std::string buggy_feature = "bugs";
	const std::string greeting = "hi";
} // namespace v1

inline namespace v2 {
	// removed the buggy_feature from this new version
	const std::string buggy_feature = "what buggy feature?";
	const std::string greeting = "hi";
} // namespace v2

int main() {
	std::cout << buggy_feature << "\n";      // outputs "what buggy feature?"
	std::cout << v1::buggy_feature << "\n";  // outputs "bugs"
}
```

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

### ModInt Template Example (C++ with AtCoder Library)

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

This C++ code demonstrates the usage of a ModInt template, specifically from the AtCoder library, for handling modular arithmetic. It includes necessary headers and sets a global MOD constant. The snippet shows the basic setup before performing operations within the main function.

```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;



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

```

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

### Linking to Modules in MDX

Source: https://usaco.guide/editor_filepath=content%2F2_Bronze%2FAd_Hoc

Demonstrates how to create internal links to other modules within the USACO Guide. Links should use the absolute path starting from the guide's root, not relative paths.

```mdx
"[insert text here](/general/practicing)"
```

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

### Basic Input Reading in C++

Source: https://usaco.guide/editor_filepath=content%2F1_General%2FUSACO_Monthlies

A fundamental C++ code snippet for reading an integer N and then reading N elements into a vector of long long integers. This setup is common as a starting point for competitive programming problems, including those involving bitmasks or permutations, where input processing is the first step.

```cpp
#include <bits/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\n\nint main() {\n\tint n;\n\tcin >> n;\n\tvector<ll> weights(n);\n\tfor (ll &w : weights) { cin >> w; }\n\n\n}
```

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

### C++ Priority Queue Solution Setup for Robot Construction

Source: https://usaco.guide/editor_filepath=content%2F6_Advanced%2FGame_Theory

This C++ code snippet sets up the necessary includes and type definitions for implementing the priority queue solution for robot construction. It utilizes standard libraries and defines common type aliases for convenience.

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


typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef pair<ll, pi> T;


#define f first
#define s second

```

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

### Implementing Graph-Based Constraint Satisfaction in C++

Source: https://usaco.guide/bronze/intro-graphs

This C++ code snippet, likely part of a larger solution for problems like 'Livestock Lineup', uses a graph representation to handle constraints. It employs `<map>` and `<vector>` to manage relationships between entities (cows in the example) and allows for efficient traversal to satisfy conditions. The focus is on the setup for processing constraints.

```cpp
#include <algorithm>
#include <fstream>
#include <map>
#include <string>
#include <vector>


using std::endl;
using std::string;
using std::vector;


// Potential implementation details would follow, likely involving:
// - A map to store adjacency lists for each cow (string to vector<string>)
// - Logic to build this map from input constraints
// - A traversal algorithm (e.g., DFS or BFS) to order the cows
```

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

### Basic C++ Input Setup for Competitive Programming

Source: https://usaco.guide/editor_filepath=content%2F1_General%2FUSACO_Camp

A standard C++ boilerplate for competitive programming, including necessary headers and basic input operations. It sets up the main function to read an integer 'n' and then read 'n' long long values into a vector.

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


int main() {
	int n;
	cin >> n;
	vector<ll> weights(n);
	for (ll &w : weights) { cin >> w; }


}
```

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

### Compile and Run C++ Program

Source: https://usaco.guide/editor_filepath=content%2F1_General%2FContest_Strategy

Commands to compile a C++ source file (`name.cpp`) into an executable (`name`) using g++ and then run the executable. It also shows how to combine these steps.

```bash
g++ name.cpp -o name
```

```bash
./name
```

```bash
g++ name.cpp -o name && ./name
```

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

### Initialize and Use next_permutation

Source: https://usaco.guide/editor_filepath=content%2F1_General%2FUSACO_Monthlies

This C++ code demonstrates the initialization and usage of the `next_permutation` function. It reads a string, sorts it to ensure lexicographical order, and comments indicate where to process the sorted permutations. This is a prerequisite for using `next_permutation` effectively.

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


using namespace std;


int main() {
	string s;
	cin >> s;
	sort(s.begin(), s.end());


	// perms is a sorted list of all the permutations of the given string


```

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

### C++ Helper Function for USACO File I/O Setup

Source: https://usaco.guide/general/input-output

A C++ helper function `setIO` that takes a string representing the problem name (without extension) and sets up file I/O redirection using freopen. It creates input and output files named 's.in' and 's.out' respectively. This simplifies the process of configuring file I/O for multiple problems.

```cpp
#include <cstdio>
#include <iostream>
using namespace std;


// the argument is the input filename without the extension
void setIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}



```

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

### C++ std::map Demonstration

Source: https://usaco.guide/editor_filepath=content%2F2_Bronze%2FComplete_Rec

Illustrates the basic usage of std::map in C++, demonstrating key-value pair insertion and modification. It shows how elements are added and the state of the map after insertions. Requires the `<map>` header.

```cpp
#include <iostream>
#include <map>


using namespace std;


void demo() {
	map<int, int> m;
	m[1] = 5;                    // [(1, 5)]
	m[3] = 14;                   // [(1, 5); (3, 14)]
	m[2] = 7;                    // [(1, 5); (2, 7); (3, 14)]

```

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

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

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

An example showcasing AtCoder's ModInt template, which is often included in competitive programming environments. It utilizes the atcoder/modint library and defines a MOD constant.

```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;



```

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

### Basic C++ Command Line Execution

Source: https://usaco.guide/editor_filepath=solutions%2Fgold%2Fcses-1139

This snippet shows the basic structure of a C++ program and how it can be compiled and executed from the command line. It covers the necessary compiler command and how to run the resulting executable.

```bash
# Compile the C++ code
g++ main.cpp -o main

# Run the executable
./main
```

```C++
#include <iostream>

int main() {
    std::cout << "Hello, World!\n";
    return 0;
}
```

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

### C++ Dynamic Programming Setup

Source: https://usaco.guide/editor_filepath=content%2F6_Advanced%2FDP_More

Initializes variables and reads input for a dynamic programming problem. This snippet sets up the basic structure for an N-element array and an integer K, likely representing the number of subarrays.

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


#define ll long long


int main() {
	int n, k;
	cin >> n >> k;


	int a[n];

```

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

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

Source: https://usaco.guide/editor_filepath=content%2F4_Gold%2FTree_Euler

An example using AtCoder's ModInt library, which provides a convenient way to perform modular arithmetic. This template is often used in competitive programming for its efficiency and ease of use.

```c++
#include <bits/stdc++.h>
// https://atcoder.github.io/ac-library/document_en/modint.html
// (included in atcoder grading)
#include <atcoder/modint>
using namespace std;
using mint = atcoder::modint;

const int MOD = 1e9 + 7;

int main() {
    mint::set_mod(MOD);
    mint a = 1e8, b = 1e8, c = 1e8;
    cout << (a + b - c).val() << "\n";
    return 0;
}
```

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

### Example Unique IDs (Text)

Source: https://usaco.guide/editor_filepath=content%2F1_General%2FResources_CP

Illustrative examples of `uniqueId` formats for various competitive programming platforms and problem sources.

```text
cses-2177
poi-08-blockade
apio-18-duathlon
dmoj-investment
infoarena-xortransform
usaco-949
cses-1691
kattis-chineseremainder
cfgym-102538F
cf-1209H
spoj-LexicographicalStringSearch
ys-AssociativeArray
```

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

### Basic C++ Program Compilation and Execution

Source: https://usaco.guide/general/cpp-command_lang=cpp

Demonstrates the fundamental steps to compile a C++ source file (`name.cpp`) into an executable (`name`) and then run the executable. It also shows how to combine these commands into a single line using the `&&` operator for sequential execution.

```cpp
#include <iostream>
using namespace std;


int main() {
	int x;
	cin >> x;
	cout << "FOUND " << x << "\n";
}
```

```bash
g++ name.cpp -o name
```

```bash
./name
```

```bash
g++ name.cpp -o name && ./name
```

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

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

Source: https://usaco.guide/editor_filepath=content%2F4_Gold%2FTree_Euler

An example demonstrating the use of a ModInt template, which automatically handles modular arithmetic for integer types. This simplifies operations by ensuring results stay within the specified modulus.

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

const int MOD = 1e9 + 7;

// Assuming ModInt template is defined here or included
// For example:
/*
template<int MOD>
struct ModInt {
    long long value;
    ModInt(long long v = 0) : value(v % MOD) {}
    // ... other methods for arithmetic operations
};
using mint = ModInt<MOD>;
*/

int main() {
	{
		int a = 1e8, b = 1e8, c = 1e8;
        // Example usage with ModInt would go here,
        // e.g., mint ma = a, mb = b, mc = c;
        // std::cout << (ma + mb - mc).value << "\n";
	}
    return 0;
}
```

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

### C++ Priority Queue Solution Setup

Source: https://usaco.guide/adv/fracturing-search_lang=cpp

This C++ code sets up necessary type definitions and macros for a priority queue-based solution. It includes standard libraries and defines aliases for long long, pairs, and vectors, along with macros for accessing pair elements.

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

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef pair<ll, pi> T;

#define f first
#define s second

```

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

### Complete Graph Partition DP - C++

Source: https://usaco.guide/editor_filepath=content%2F4_Gold%2FDP_Trees

Implementation for a DP problem that partitions nodes into sets where each set forms a complete graph. It initializes DP states for complete subgraphs and uses a DP transition to find the minimum partitions.

```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;

```

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

### C++ freopen Example for Fence Painting Problem

Source: https://usaco.guide/general/input-output

This C++ snippet redirects standard input from 'paint.in' and standard output to 'paint.out' using the freopen function. This is an example specifically for the 'Fence Painting' problem, demonstrating the application of freopen for competitive programming contest submissions.

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


int main() {
	// Use standard input to read from "paint.in"
	freopen("paint.in", "r", stdin);
	// Use standard output to write to "paint.out"
	freopen("paint.out", "w", stdout);




```

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

### Debugging with LLDB for Stack Backtrace

Source: https://usaco.guide/general/debugging-cpp_lang=cpp

Provides a step-by-step guide on using the LLDB debugger to analyze runtime errors. It covers compiling with the `-g` flag for debugging information, starting LLDB, running the program, and displaying the stack backtrace (`bt`) to identify the error's origin.

```bash
# Compile with debugging information
g++ -g your_program.cpp -o your_program

# Start LLDB
lldb your_program

# Run the program
r

# Show stack backtrace
bt
```

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

### C++ Input and Vector Initialization

Source: https://usaco.guide/editor_filepath=content%2F3_Silver%2FBinary_Search_Sorted_Array

This C++ code snippet demonstrates basic input reading using `cin` to get an integer `n` and then initializes a vector `v` of size `n`. It's a common starting point for many competitive programming problems.

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


using namespace std;


int main() {
	int n;
	cin >> n;
	vector<int> v(n);

```

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

### C++ Bit Inversions Setup with Set

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

Initializes 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 differences between these indices. This setup is crucial for efficiently calculating the longest run of identical bits after inversions.

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


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


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


```

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

### C++ Priority Queue Basic Operations

Source: https://usaco.guide/silver/priority-queues

Demonstrates the basic usage of a C++ priority queue (max-heap) including push, top, and pop operations. It shows how elements are added and retrieved in descending order.

```cpp
#include <iostream>
#include <queue>

using namespace std;

int main() {
	priority_queue<int> pq;
	pq.push(7);                // [7]
	pq.push(2);                // [2, 7]
	pq.push(1);                // [1, 2, 7]
	pq.push(5);                // [1, 2, 5, 7]
	cout << pq.top() << endl;  // 7
	pq.pop();                  // [1, 2, 5]
	pq.pop();                  // [1, 2]
	pq.push(6);                // [1, 2, 6]

	return 0;
}
```

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

### Order Statistic Tree (C++) - Basic Setup

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

This snippet shows the basic setup for an Order Statistic Tree using GCC's Policy Based Data Structures. It defines a type alias `Tree` for convenience. Note that this implementation assumes distinct elements; for non-distinct elements, pairs should be used.

```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() {


```

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

### Basic C++ Program: Standard Input/Output

Source: https://usaco.guide/editor_filepath=content%2F1_General%2FContest_Strategy

A simple C++ program that reads an integer from standard input and prints it to standard output. This serves as a basic example for demonstrating compilation and execution.

```cpp
#include <iostream>
using namespace std;


int main() {
	int x;
	cin >> x;
	cout << "FOUND " << x << "\n";
}
```

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

### MDX Solution Template with LaTeX - C++

Source: https://usaco.guide/general/adding-solution_lang=cpp

A template for adding a new solution in an MDX file. It includes frontmatter for problem details, an explanation section with LaTeX formatting for equations, and placeholders for C++, Python, and Java code implementations. It also specifies time complexity and linking conventions.

```markdown
---
id: usaco-690
source: USACO Silver 2017 January
title: Cow Dance Show
author: (add your name here)
---

[Official Analysis](http://www.usaco.org/current/data/sol_cowdance_silver_jan17.html)

## Explanation

(add explanation here ...)

Use `\texttt{}` around variable names with length *greater than one*, like so. Place long equations on separate lines with display math, and use `\cdot` instead of `*` to denote multiplication.

$$
\texttt{arr}[i]=2\cdot (a+b+c+d+e)+\sum_{j=0}^{i-1}\texttt{arr}[j]
$$

Some additional text styles which you might consider using:

http://latexref.xyz/Font-styles.html

http://applied-r.com/latex-font-styles/

$func(var)$

$\textit{func(var)}$

$\\textrm{func(var)}$

$\\text{func(var)}$

$\\textsf{func(var)}$

$\\textbf{func(var)}$

$\\texttt{func(var)}$

## Implementation

**Time Complexity:** $\mathcal{O}(N\log^2N)$

^ Format time complexity like this. Should appear outside of `<LanguageSection>` if it's the same for all implementations.

If you need to link to a module, format your link like [this](/silver/binary-search) instead of [this](https://usaco.guide/silver/binary-search).

<LanguageSection>

<CPPSection>

(add cpp code)

</CPPSection>

<PySection>

(if you have Python code)

</PySection>

<JavaSection>

(if you have Java code)

</JavaSection>

</LanguageSection>

```

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

### C++ Vector Size Handling Example

Source: https://usaco.guide/editor_filepath=content%2F1_General%2FContributing

Demonstrates the correct way to handle vector size calculations to avoid unsigned integer overflow when subtracting.

```cpp
vi x;
std::cout << x.size() - 1 << "\n";  // outputs 18446744073709551615 (incorrect)
std::cout << sz(x) - 1 << "\n";     // outputs -1 (correct)
```

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

### DSU Initialization (C++)

Source: https://usaco.guide/editor_filepath=content%2F5_Plat%2FConclusion

Initializes a Disjoint Set Union (DSU) data structure. This is a common setup for problems involving connected components or sets.

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


 DSU D;
int n, m;
vector<int> comps;


void init() {

}
```

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

### Digit DP State Initialization (C++)

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

Initializes the DP table for Digit DP problems. The state `dp[pos][k][under][started]` is used to store counts based on position, digit balance, upper bound adherence, and whether digits have started. This function ensures the DP table is reset before each computation.

```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() {

```

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

### Push DP Example in C++

Source: https://usaco.guide/editor_filepath=content%2F4_Gold%2FIntro_DP

This C++ code demonstrates the Push DP approach to calculate minimum costs. It initializes a DP array and iterates through stones, updating costs based on jumping one or two stones forward. The cost calculation considers the absolute difference in heights between stones.

```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

```

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

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

Source: https://usaco.guide/editor_filepath=content%2F4_Gold%2FPURS

A C++ template for ModInt (Modular Integer) that automatically handles modular arithmetic. This example shows how to include and use such a template, likely simplifying operations like addition, subtraction, multiplication, and division (via modular inverse) within a competitive programming context.

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

// Assuming a ModInt template implementation exists
// Example structure:
// template<int MOD>
// struct ModInt {
//     int val;
//     ModInt(int v = 0) : val((v % MOD + MOD) % MOD) {}
//     // ... operators ...
// };

// const int MOD = 1e9 + 7;
// using mint = ModInt<MOD>;

int main() {
	// Example usage within a contest setup
	// int a = 1e8, b = 1e8, c = 1e8;
	// std::cout << "ModInt example placeholder\n";

    // Actual Benq's template usage would involve defining and using the ModInt struct
    // For demonstration, we'll show a simplified direct calculation context:
    long long a = 1e8, b = 1e8, c = 1e8;
    long long MOD = 1e9 + 7;
    long long res = (a + b) % MOD;
    res = (res * c) % MOD;
    std::cout << "Example calculation: " << res << "\n";

	return 0;
}
```

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

### C++ Min-Heap Implementation for Room Allocation

Source: https://usaco.guide/silver/priority-queues_lang=cpp

Provides a C++ code snippet illustrating the use of a min-priority queue (min-heap) for the 'Room Allocation' problem. It shows how to include necessary headers and initialize a min-heap using `greater<>()`. This approach is crucial for efficiently managing departure times to find available rooms.

```cpp
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;


int main() {
	int N;
	cin >> N;


	vector<int> ans(N);

```

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

### Link Cut Tree Initialization (C++)

Source: https://usaco.guide/adv/link-cut-tree_lang=cpp

Initializes a Link Cut Tree (LCT) data structure for a given number of nodes. This is a common starting point for LCT implementations.

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


int main() {
	int n;
	int m;
	cin >> n >> m;
	LCT lc(n);

```

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

### Centroid Decomposition - C++ Setup

Source: https://usaco.guide/plat/centroid

Initializes data structures for centroid decomposition in C++. It includes the adjacency list, a boolean array to mark removed nodes, and an array to store subtree sizes.

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

using namespace std;

const int maxn = 200010;

int n;
vector<int> adj[maxn];
int subtree_size[maxn];
```

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

### Cowpatibility Problem Setup (C++)

Source: https://usaco.guide/editor_filepath=content%2F5_Plat%2FMatrix_Expo

This C++ code snippet sets up the initial part of the Cowpatibility problem solution. It reads the number of cows and uses a map to store the frequency of different combinations of ice cream flavors. This is a common data structure for counting occurrences of complex keys.

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

int main() {
	ifstream in("cowpatibility.in");
	int n;
	in >> n;

	map<vector<int>, int> subsets;
	for (int i = 1; i <= n; i++) {

	}
}
```

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

### DSU Initialization (C++)

Source: https://usaco.guide/adv/offline-del_lang=cpp

Initializes a Disjoint Set Union (DSU) data structure with a maximum size of MAXN. This is a common setup for problems involving dynamic connectivity or maintaining sets of elements.

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


const int MAXN = 3e5;


DSU dsu(MAXN);

```

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

### C++ Tuple Usage

Source: https://usaco.guide/bronze/intro-ds_lang=cpp

Illustrates the use of `std::tuple` in C++ for storing multiple elements of potentially different types. Demonstrates creation, accessing elements with `get<i>`, and assignment with `tie`.

```cpp
#include <iostream>
#include <tuple>
#include <string>

int main() {
    // Creating a tuple using make_tuple
    auto t1 = std::make_tuple(3, 4, 5);
    std::cout << std::get<0>(t1) << " " << std::get<1>(t1) << " " << std::get<2>(t1) << std::endl;

    // Creating a tuple using initializer list (C++11 and later)
    std::tuple<int, int, int> t2{7, 4, 5};
    std::cout << std::get<0>(t2) << " " << std::get<1>(t2) << " " << std::get<2>(t2) << std::endl;

    // Modifying a tuple element
    std::get<0>(t2) = 9;
    std::cout << "Modified tuple: ";
    std::cout << std::get<0>(t2) << " " << std::get<1>(t2) << " " << std::get<2>(t2) << std::endl;

    // Using tie to unpack a tuple
    int a, b, c;
    std::tie(a, b, c) = t2;
    std::cout << "Unpacked tuple: " << a << " " << b << " " << c << std::endl;

    // Tuple with different types
    std::tuple<std::string, int> t3 = std::make_tuple("Hello world", 100);
    std::cout << std::get<0>(t3) << " " << std::get<1>(t3) << std::endl;

    return 0;
}
```

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

### Namespace and Inline Namespace Usage in C++

Source: https://usaco.guide/editor_filepath=content%2F1_General%2FCpp_Command

Demonstrates creating custom namespaces to organize code elements like constants and classes. It also introduces `using namespace` for easier access and explains the concept and application of inline namespaces for versioning.

```cpp
namespace test {
const std::string greeting = "hi";
namespace test1 {
const int time = 2;
}
using namespace test1;

template <class T> struct TestDS {
	T s;

	void add(T x) { s += x; }

	T get() { return s; }
};
}  // namespace test

inline namespace v2 {
// removed the buggy_feature from this new version
const std::string buggy_feature = "what buggy feature?";
const std::string greeting = "hi";
}  // namespace v2

namespace v1 {
const std::string buggy_feature = "bugs";
const std::string greeting = "hi";
}  // namespace v1

int main() {
	std::cout << buggy_feature << "\n";      // outputs "what buggy feature?"
	std::cout << v1::buggy_feature << "\n";  // outputs "bugs"
}
```

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

### DFS for Subtree Range Calculation

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

This C++ code implements a Depth First Search (DFS) traversal to determine 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. This is useful for subtree queries and analysis. It uses global variables for timer, start times (tin), and the Euler tour array.

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


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


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) {


```

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

### 2D Fenwick Tree (BIT) Usage Example

Source: https://usaco.guide/plat/2DRQ_lang=cpp

A C++ code snippet demonstrating the usage of a 2D Fenwick Tree (BIT). It includes necessary headers and uses `long long` for potentially large values.

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

// Code Snippet: Offline 2D BIT (Click to expand)

int main() {


```

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

### C++ std::unordered_set Demonstration

Source: https://usaco.guide/editor_filepath=content%2F2_Bronze%2FComplete_Rec

Demonstrates the basic insertion operations for std::unordered_set in C++. It shows how elements are added to the set and the resulting state after each insertion. This requires the `<unordered_set>` header.

```cpp
#include <iostream>
#include <unordered_set>


using namespace std;


void demo() {
	unordered_set<int> s;
	s.insert(1);                 // {1}
	s.insert(4);                 // {1, 4}
	s.insert(2);                 // {1, 2, 4}

```

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

### Namespace Definition and Usage

Source: https://usaco.guide/editor_filepath=content%2F1_General%2FContests

Explains how to define custom namespaces to organize code, including nested namespaces and using declarations. This example shows a 'test' namespace with nested 'test1' and a 'TestDS' struct.

```C++
namespace test {
const string greeting = "hi";
namespace test1 {
const int time = 2;
}
using namespace test1;


template <class T> struct TestDS {
	T s;


	void add(T x) { s += x; }


	T get() { return s; }
};
}  // namespace test
```
Tokens:
Raw