🏆 C++ for Competitive Programming: A USACO Guide

From Zero to USACO Gold

The complete beginner's roadmap to competitive programming in C++, designed around USACO competition preparation.

No prior experience required. Written for clarity, depth, and contest readiness.

🎯 What Is This Book?

This book is a structured, self-contained course for students who want to learn competitive programming in C++ — specifically USACO (USA Computing Olympiad)

Unlike scattered online resources, this book gives you a single linear path: from writing your very first C++ program, through data structures and graph algorithms, all the way to solving USACO Gold problems with confidence. Every chapter builds on the previous one, with detailed worked examples, annotated C++ code, and SVG diagrams that make abstract algorithms visual and concrete.

If you've ever felt overwhelmed looking at USACO editorials, or if you know some programming but don't know what to learn next — this book was written for you.

✅ What You'll Learn

📊 Book Statistics

🗺️ Learning Path

🚀 Quick Start (5 Minutes)

Step 1: Install C++ Compiler

Windows: Install MSYS2, then: pacman -S mingw-w64-x86_64-gcc

macOS: xcode-select --install in Terminal

Linux: sudo apt install g++ build-essential

Verify: g++ --version (should show version ≥ 9)

Step 2: Get an Editor

VS Code + C/C++ extension + Code Runner extension

Step 3: Competition Template

Copy this to template.cpp — use it as your starting point for every problem:

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("problem.in", "r", stdin);   // uncomment for file I/O
    // freopen("problem.out", "w", stdout);

    // Your solution here

    return 0;
}

Step 4: Compile & Run

g++ -o sol solution.cpp -std=c++17 -O2 -Wall
./sol < input.txt

Step 5: Start Reading

Go to Chapter 2.1 and write your first C++ program. Then solve all practice problems before moving on. Don't skip the problems — that's where 80% of learning happens.

📚 How to Use This Book

The Reading Strategy That Works

1. Read actively: Code every example yourself. Don't just read — type it out.
2. Do the problems: Each chapter has 5–7 problems. Attempt every one before reading hints.
3. Read hints when stuck (after 20–30 minutes of genuine effort)
4. Review the Chapter Summary before moving on — it's a quick checklist.
5. Return to earlier chapters when a later chapter references them.

Practice Problems Guide

Each practice problem is labeled:

• 🟢 Easy — Directly applies the chapter's main technique
• 🟡 Medium — Requires combining ideas or a minor insight
• 🔴 Hard — Challenging; partial credit counts!
• 🏆 Challenge — Beyond chapter scope; try when ready

All hints are hidden by default (click to expand). Struggle first!

Reading Schedule

📖 Chapter Overview

Part 2: C++ Foundations (1–2 weeks)

Part 3: Core Data Structures (2–3 weeks)

Part 4: Greedy Algorithms (1 week)

Part 5: Graph Algorithms (2–3 weeks)

Part 6: Dynamic Programming (3–4 weeks)

Part 7: USACO Contest Guide (Read anytime)

Part 8: USACO Gold Topics (4 weeks)

Appendix & Reference

🔧 Setup Instructions

Compiler Setup

Verify with: g++ --version

Recommended Compile Flags

# Development (shows warnings, helpful for debugging)
g++ -o sol solution.cpp -std=c++17 -O2 -Wall -Wextra

# Contest (fast, silent)
g++ -o sol solution.cpp -std=c++17 -O2

Running with I/O Redirection

# Run with input file
./sol < input.txt

# Run and save output
./sol < input.txt > output.txt

# Compare output to expected
diff output.txt expected.txt

📖 Local Development / Build This Book

This project uses mdBook (a Rust-based book builder) as its build system. GitBook is no longer used.

Prerequisites: Install mdBook

Via Homebrew (macOS):

brew install mdbook

Via Cargo (cross-platform, requires Rust):

cargo install mdbook

Via pre-built binary: Download from mdBook GitHub Releases

Verify installation: mdbook --version

Local Preview (with hot-reload)

mdbook serve

This starts a local server at http://localhost:3000 with live-reload. Edit any .md file and the browser will automatically refresh.

Local Build

mdbook build

Build output is in the book/ directory. Open book/index.html in a browser to view the static site.

CI/CD

The project uses GitHub Actions to automatically build and deploy via mdBook. See .github/workflows/deploy.yml for details.

🌐 External Resources

🏅 Who Is This Book For?

✅ Middle school / high school students preparing for USACO Bronze through Gold

✅ Complete beginners with no prior programming experience (Part 2 starts from zero)

✅ Intermediate programmers who know Python or Java and want to learn C++ for competitive programming

✅ Self-learners who want a structured, complete curriculum instead of scattered tutorials

✅ Coaches and teachers looking for a comprehensive curriculum for their students

This book is NOT for:

• USACO Gold/Platinum (advanced data structures, network flow, geometry)
• General software engineering (no databases, web development, etc.)

🐄 Ready? Let's Begin!

Turn to Chapter 2.1 and write your first C++ program.

The path from complete beginner to USACO Gold is roughly 300–500 hours of focused practice over 3–8 months. It won't always be easy — but every USACO Gold competitor you admire started exactly where you are now.

The only way to get better is to write code, struggle with problems, and keep going. 🐄

Last updated: 2026 · Targets: USACO Bronze → Gold · C++ Standard: C++17 55+ SVG diagrams · 150+ code examples · 130+ practice problems

Part 2: C++ Foundations

Before you can solve algorithmic problems, you need to speak the language. Part 2 is your crash course in C++ — from the very first program to functions, arrays, and vectors. You'll build the foundational skills needed for all later chapters.

What You'll Learn

Why C++?

Competitive programmers overwhelmingly choose C++ for two reasons:

1. Speed — C++ programs run faster than Python or Java, which matters when you have tight time limits (typically 1–2 seconds for up to 10^8 operations)
2. The STL — C++'s Standard Template Library gives you ready-made implementations of nearly every data structure and algorithm you'll ever need

Note: USACO accepts C++, Java, and Python. But C++ is by far the most common choice among top competitors, and this book focuses on it exclusively.

Tips for Part 2

• Type the code yourself. Don't copy-paste. Your fingers need to learn the syntax.
• Break things. Deliberately introduce errors and see what happens. Reading compiler errors is a skill.
• Run every example. Seeing output appear on screen cements understanding far better than just reading.

Let's dive in!

Chapter 2.1: Your First C++ Program

📝 Before You Continue: This is the very first chapter — no prerequisites! You don't need to have any programming experience. Just work through this chapter from top to bottom and you'll write your first real C++ program by the end.

Welcome! By the end of this chapter, you will have:

• Set up a working C++ environment (takes 5 minutes using an online compiler)
• Written, compiled, and run your first C++ program
• Understood what every single line of code does
• Learned about variables, data types, and input/output
• Solved 13 practice problems with full solutions

2.1.0 Setting Up Your Environment

Before writing any code, you need a place to write and run it. There are two options: online compilers (recommended for beginners — no installation required) and local setup (optional, for when you want to work offline).

Option A: Online Compilers (Recommended — Start Here!)

You only need a web browser. Open any of these sites:

Using Ideone (simplest for beginners):

1. Go to ideone.com
2. Select "C++17 (gcc 8.3)" from the language dropdown
3. Paste your code in the text area
4. Click the green "Run" button
5. See output in the bottom panel

That's it! No installation, no configuration.

Option B: Using CLion (Recommended Local IDE)

If you want to write and run C++ code offline on your own computer, we highly recommend CLion — a professional C/C++ IDE by JetBrains. It features intelligent code completion, one-click build & run, and a built-in debugger, all of which will significantly boost your productivity.

💡 Free for Students! CLion is a paid product, but JetBrains offers a free educational license for students. Simply apply with your .edu email on the JetBrains Student License page.

Installation Steps:

Step 1: Install a C++ Compiler (CLion requires an external compiler)

Step 2: Install CLion

1. Go to the CLion download page and download the installer for your OS
2. Run the installer and follow the prompts (keep the default options)
3. On first launch, choose "Activate" → sign in with your JetBrains student account, or start a free 30-day trial

Step 3: Create Your First Project

1. Open CLion and click "New Project"
2. Select "C++ Executable" and set the Language standard to C++17
3. Click "Create" — CLion will automatically generate a project with a main.cpp file
4. Write your code in main.cpp, then click the green ▶ Run button in the top-right corner to compile and run
5. The output will appear in the "Run" panel at the bottom

🔧 CLion Auto-Detects Compilers: On first launch, CLion automatically scans for installed compilers (GCC / Clang / MSVC). If detection succeeds, you'll see a green checkmark ✅ in Settings → Build → Toolchains. If not detected, verify that the compiler from Step 1 is correctly installed and added to your PATH.

Useful CLion Features for Competitive Programming:

• Built-in Terminal: The Terminal tab at the bottom lets you type test input directly
• Debugger: Set breakpoints, step through code line by line, and inspect variable values — an essential tool for tracking down bugs
• Code Formatting: Ctrl + Alt + L (Mac: Cmd + Option + L) automatically tidies up your code indentation

How to Compile and Run (Local)

Once you have g++ installed, here's how to compile and run:

g++ -o hello hello.cpp -std=c++17

Let's break down that command character by character:

Then to run it:

./hello        # Linux/Mac: ./ means "in current directory"
hello.exe      # Windows (the .exe is added automatically)

🤔 Why ./hello and not just hello? On Linux/Mac, the system won't run programs from the current folder by default (for security). The ./ explicitly says "look in the current directory."

2.1.1 Hello, World!

Every programming journey starts the same way. Here is the simplest complete C++ program:

#include <iostream>    // tells the compiler we want to use input/output

int main() {           // every C++ program starts executing from main()
    std::cout << "Hello, World!" << std::endl;  // print to the screen
    return 0;          // 0 = success, program ended normally
}

Run it, and you should see:

Hello, World!

What every line means:

Line 1: #include <iostream> This is a preprocessor directive — an instruction that runs before the actual compilation. It says "copy-paste the contents of the iostream library into my program." The iostream library provides cin (read input) and cout (print output). Without this line, your program can't print anything.

Think of it like: before you can cook, you need to bring the ingredients into the kitchen.

Line 3: int main() This declares the main function — the starting point of every C++ program. When you run a C++ program, the computer always starts executing from the first line inside main(). The int means this function returns an integer (the exit code). Every C++ program must have exactly one main.

Line 4: std::cout << "Hello, World!" << std::endl; This prints text. Let's break it down:

• std::cout — the "console output" stream (think of it as the screen)
• << — the "put into" operator; sends data into the stream
• "Hello, World!" — the text to print (the quotes are not printed)
• << std::endl — adds a newline (like pressing Enter)
• ; — every statement in C++ ends with a semicolon

Line 5: return 0; Exits main and tells the operating system the program finished successfully. (A non-zero return would signal an error.)

The Compilation Pipeline

Visual: The Compilation Pipeline

The diagram above shows the three-stage journey from source code to executable: your .cpp file is fed to the g++ compiler, which produces a runnable binary. Understanding this pipeline helps debug compilation errors before they happen.

2.1.2 The Competitive Programmer's Template

When solving USACO problems, you'll use a standard template. Here it is, fully explained:

#include <bits/stdc++.h>      // "batteries included" — includes ALL standard libraries
using namespace std;           // lets us write cout instead of std::cout

int main() {
    ios_base::sync_with_stdio(false);  // disables syncing C and C++ I/O (faster)
    cin.tie(NULL);                      // unties cin from cout (faster input)

    // Your solution code goes here

    return 0;
}

Why #include <bits/stdc++.h>?

This is a GCC-specific header that includes every standard library at once. Instead of writing:

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
// ... 20 more lines

You write one line. In competitive programming, this is universally accepted and saves time.

Note: bits/stdc++.h only works with GCC (the compiler USACO judges use). It's fine for competitive programming, but don't use it in production software.

Why using namespace std;?

The standard library puts everything inside a namespace called std. Without this line, you'd write std::cout, std::vector, std::sort everywhere. With using namespace std;, you write cout, vector, sort — much cleaner.

The I/O Speed Lines

ios_base::sync_with_stdio(false);
cin.tie(NULL);

These two lines make cin and cout much faster. Without them, reading large inputs can be 10× slower and cause "Time Limit Exceeded" (TLE) even if your algorithm is correct. Always include them.

🐛 Common Bug: After using these speed lines, don't mix cin/cout with scanf/printf. Pick one style.

2.1.3 Variables and Data Types

A variable is a named location in memory that stores a value. In C++, every variable has a type — the type tells the computer how much memory to reserve and what kind of data will go in it.

🧠 Mental Model: Variables are like labeled boxes

When you write:   int score = 100;

The computer does three things:
  1. Creates a box big enough to hold an integer (4 bytes)
  2. Puts the label "score" on the box
  3. Puts the number 100 inside the box

The Essential Types for Competitive Programming

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

int main() {
    // int: whole numbers, range: -2,147,483,648 to +2,147,483,647 (about ±2 billion)
    int apples = 42;
    int temperature = -5;

    // long long: big whole numbers, range: about ±9.2 × 10^18
    long long population = 7800000000LL;  // the LL suffix means "this is a long long literal"
    long long trillion = 1000000000000LL;

    // double: decimal/fractional numbers
    double pi = 3.14159265358979;
    double percentage = 99.5;

    // bool: true or false only
    bool isRaining = true;
    bool finished = false;

    // char: a single character (stored as a number 0-255)
    char grade = 'A';     // single quotes for characters
    char newline = '\n';  // special: newline character

    // string: a sequence of characters
    string name = "Alice";         // double quotes for strings
    string greeting = "Hello!";

    // Print them all:
    cout << "Apples: " << apples << "\n";
    cout << "Population: " << population << "\n";
    cout << "Pi: " << pi << "\n";
    cout << "Is raining: " << isRaining << "\n";  // prints 1 for true, 0 for false
    cout << "Grade: " << grade << "\n";
    cout << "Name: " << name << "\n";

    return 0;
}

Visual: C++ Data Types Reference

Choosing the Right Type

Variable Naming Rules

Variable names follow strict rules in C++. Getting these right is essential — bad names lead to bugs, and illegal names won't compile at all.

The Formal Rules (Enforced by the Compiler)

✅ Legal names must:

• Start with a letter (a-z, A-Z) or underscore _
• Contain only letters, digits (0-9), and underscores
• Not be a C++ reserved keyword

❌ These will NOT compile:

⚠️ Case sensitive! score, Score, and SCORE are three completely different variables. This is a common source of bugs — be consistent.

Common Naming Styles

There are several widely-used naming conventions in C++. You don't have to pick one for competitive programming, but knowing them helps you read other people's code:

In competitive programming, camelCase and single-letter names are most common. In production code at companies, snake_case or camelCase are standard depending on the style guide.

Best Practices for Naming

1. Be descriptive — make the purpose clear from the name:

// ✅ Good — instantly clear what each variable stores
int numCows = 5;
long long totalMilk = 0;
string cowName = "Bessie";
int maxScore = 100;

// ❌ Bad — legal but confusing
int x = 5;            // What is x? Count? Index? Value?
long long t = 0;      // What is t? Time? Total? Temporary?
string n = "Bessie";  // n usually means "number" — misleading for a name!

2. Use conventional single-letter names only when the meaning is obvious:

// ✅ Acceptable — these are universally understood conventions
for (int i = 0; i < n; i++) { ... }    // i, j, k for loop indices
int n, m;                                // n = count, m = second dimension
cin >> n >> m;                           // in competitive programming, everyone does this

// ❌ Confusing — single letters with no clear convention
int q = 5;   // Is q a count? A query? A coefficient?
char z = 'A'; // Why z?

3. Constants should be ALL_CAPS to stand out:

const int MAX_N = 200005;        // maximum array size
const int MOD = 1000000007;      // modular arithmetic constant
const long long INF = 1e18;      // "infinity" for comparisons
const double PI = 3.14159265359; // mathematical constant

4. Avoid names that look too similar to each other:

// ❌ Easy to mix up
int total1 = 10;
int totall = 20;  // is this "total-L" or "total-1" with a typo?

int O = 0;        // the letter O looks like the digit 0
int l = 1;        // lowercase L looks like the digit 1

// ✅ Better alternatives
int totalA = 10;
int totalB = 20;

5. Don't start names with underscores followed by uppercase letters:

// ❌ Technically compiles, but reserved by the C++ standard
int _Score = 100;   // names like _X are reserved for the compiler/library
int __value = 42;   // double underscore is ALWAYS reserved

// ✅ Safe alternatives
int score = 100;
int myValue = 42;

Naming in Competitive Programming vs. Production Code

💡 For this book: We'll use a mix — descriptive names for clarity in explanations, but shorter names when solving problems under time pressure. The important thing is: you should always be able to look at a variable name and immediately know what it stores.

Deep Dive: char, string, and Character-Integer Conversions

Earlier in this chapter we briefly introduced char and string. Since many USACO problems involve character processing, digit extraction, and string manipulation, let's take a deeper look at these essential types.

char and ASCII — Every Character is a Number

A char in C++ is stored as a 1-byte integer (0–255). Each character is mapped to a number according to the ASCII table (American Standard Code for Information Interchange). You don't need to memorize the whole table, but knowing a few key ranges is extremely useful:

 Key relationships:
 • 'a' - 'A' = 32     (difference between lower and upper case)
 • '0' has ASCII value 48 (not 0!)
 • Digits, uppercase letters, and lowercase letters
   are each in CONSECUTIVE ranges

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

int main() {
    char ch = 'A';

    // A char IS an integer — you can print its numeric value
    cout << ch << "\n";        // prints: A  (as character)
    cout << (int)ch << "\n";   // prints: 65 (its ASCII value)

    // You can do arithmetic on chars!
    char next = ch + 1;       // 'A' + 1 = 66 = 'B'
    cout << next << "\n";     // prints: B

    // Compare chars (compares their ASCII values)
    cout << ('a' < 'z') << "\n";   // 1 (true, because 97 < 122)
    cout << ('A' < 'a') << "\n";   // 1 (true, because 65 < 97)

    return 0;
}

char ↔ int Conversions — The Most Common Technique

In competitive programming, you constantly need to convert between character digits and integer values. Here's the complete guide:

1. Digit character → Integer value (e.g., '7' → 7)

char ch = '7';
int digit = ch - '0';    // '7' - '0' = 55 - 48 = 7
cout << digit << "\n";   // prints: 7

// This works because digit characters '0'~'9' have consecutive ASCII values:
// '0'=48, '1'=49, ..., '9'=57
// So ch - '0' gives the actual numeric value (0~9)

2. Integer value → Digit character (e.g., 7 → '7')

int digit = 7;
char ch = '0' + digit;   // 48 + 7 = 55 = '7'
cout << ch << "\n";      // prints: 7 (as the character '7')

// Works for digits 0~9 only

3. Uppercase ↔ Lowercase conversion

char upper = 'C';
char lower = upper + 32;           // 'C'(67) + 32 = 'c'(99)
cout << lower << "\n";            // prints: c

// More readable approach using the difference:
char lower2 = upper - 'A' + 'a';  // 'C'-'A' = 2, 'a'+2 = 'c'
cout << lower2 << "\n";           // prints: c

// Reverse: lowercase → uppercase
char ch = 'f';
char upper2 = ch - 'a' + 'A';    // 'f'-'a' = 5, 'A'+5 = 'F'
cout << upper2 << "\n";           // prints: F

// Using built-in functions (recommended for clarity):
cout << (char)toupper('g') << "\n";  // prints: G
cout << (char)tolower('G') << "\n";  // prints: g

4. Check character types (very useful in USACO)

char ch = '5';

// Check if digit
if (ch >= '0' && ch <= '9') {
    cout << "It's a digit!\n";
}

// Check if uppercase letter
if (ch >= 'A' && ch <= 'Z') {
    cout << "Uppercase!\n";
}

// Check if lowercase letter
if (ch >= 'a' && ch <= 'z') {
    cout << "Lowercase!\n";
}

// Or use built-in functions:
// isdigit(ch), isupper(ch), islower(ch), isalpha(ch), isalnum(ch)
if (isdigit(ch)) cout << "Digit!\n";
if (isalpha(ch)) cout << "Letter!\n";

5. A Classic Pattern: Extract Digits from a String

string s = "abc123def";
int sum = 0;
for (char ch : s) {
    if (ch >= '0' && ch <= '9') {
        sum += ch - '0';  // convert digit char to int and add
    }
}
cout << "Sum of digits: " << sum << "\n";  // 1+2+3 = 6

string Detailed Guide

string is C++'s built-in text type. Unlike a single char, a string holds a sequence of characters and provides many useful operations.

Basic operations:

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

int main() {
    // Creating strings
    string s1 = "Hello";
    string s2 = "World";
    string empty = "";           // empty string
    string repeated(5, 'x');     // "xxxxx" — 5 copies of 'x'

    // Length
    cout << s1.size() << "\n";   // 5 (same as s1.length())

    // Concatenation (joining strings)
    string s3 = s1 + " " + s2;  // "Hello World"
    s1 += "!";                   // s1 is now "Hello!"

    // Access individual characters (0-indexed, just like arrays)
    cout << s3[0] << "\n";      // 'H'
    cout << s3[6] << "\n";      // 'W'

    // Modify individual characters
    s3[0] = 'h';                // "hello World"

    // Comparison (lexicographic, i.e., dictionary order)
    cout << ("apple" < "banana") << "\n";   // 1 (true)
    cout << ("abc" == "abc") << "\n";       // 1 (true)
    cout << ("abc" < "abd") << "\n";        // 1 (true, compares char by char)

    return 0;
}

Iterating over a string:

string s = "USACO";

// Method 1: index-based loop
for (int i = 0; i < (int)s.size(); i++) {
    cout << s[i] << " ";  // U S A C O
}
cout << "\n";

// Method 2: range-based for loop (cleaner)
for (char ch : s) {
    cout << ch << " ";    // U S A C O
}
cout << "\n";

// Method 3: range-based with reference (for modifying in-place)
for (char& ch : s) {
    ch = tolower(ch);     // convert each char to lowercase
}
cout << s << "\n";        // "usaco"

Useful string functions:

string s = "Hello, World!";

// Substring: s.substr(start, length)
string sub = s.substr(7, 5);     // "World" (starting at index 7, take 5 chars)
string sub2 = s.substr(7);       // "World!" (from index 7 to end)

// Find: s.find("text") — returns index or string::npos if not found
size_t pos = s.find("World");    // 7  (size_t, not int!)
if (s.find("xyz") == string::npos) {
    cout << "Not found!\n";
}

// Append
s.append(" Hi");                 // "Hello, World! Hi"
// or equivalently: s += " Hi";

// Insert
s.insert(5, "!!");               // "Hello!!, World! Hi"

// Erase: s.erase(start, count)
s.erase(5, 2);                   // removes 2 chars starting at index 5 → "Hello, World! Hi"

// Replace: s.replace(start, count, "new text")
string msg = "I love cats";
msg.replace(7, 4, "dogs");       // "I love dogs"

Reading strings from input:

// cin >> reads ONE WORD (stops at whitespace)
string word;
cin >> word;    // input "Hello World" → word = "Hello"

// getline reads the ENTIRE LINE (including spaces)
string line;
getline(cin, line);   // input "Hello World" → line = "Hello World"

// ⚠️ Remember: after cin >>, call cin.ignore() before getline!
int n;
cin >> n;
cin.ignore();          // consume the leftover '\n'
string fullLine;
getline(cin, fullLine); // now this reads correctly

Converting between string and numbers:

// String → Integer
string numStr = "42";
int num = stoi(numStr);         // stoi = "string to int" → 42
long long big = stoll("123456789012345"); // stoll = "string to long long"

// String → Double
double d = stod("3.14");       // stod = "string to double" → 3.14

// Integer → String
int x = 255;
string s = to_string(x);       // "255"
string s2 = to_string(3.14);   // "3.140000"

char Arrays (C-Style Strings) — Know They Exist

In C (and old C++ code), strings were stored as arrays of char ending with a special null character '\0'. You'll rarely need these in competitive programming (use string instead), but you should recognize them:

// C-style string (char array)
char greeting[] = "Hello";  // actually stores: H e l l o \0 (6 chars!)
// The '\0' (null terminator) marks the end of the string

// WARNING: you must ensure the array is big enough to hold the string + '\0'
char name[20];              // can hold up to 19 characters + '\0'

// Reading into a char array (rarely needed)
// cin >> name;             // works, but limited by array size
// scanf("%s", name);       // C-style, also works

// Converting between char array and string
string s = greeting;        // char array → string (automatic)
// string → char array: use s.c_str() to get a const char*

Why string is better than char[] for competitive programming:

⚡ Pro Tip for USACO: Always use string unless a problem specifically requires char arrays. String operations are cleaner, safer, and easier to debug. The only common use of char arrays in competitive programming is when reading very large inputs with scanf/printf for speed — but with sync_with_stdio(false), string + cin/cout is fast enough for 99% of USACO problems.

Quick Reference: Character/String Cheat Sheet

⚠️ Integer Overflow — The #1 Bug in Competitive Programming

What happens when a number gets too big for its type?

// Imagine int as a dial that goes from -2,147,483,648 to 2,147,483,647
// When you go past the maximum, it WRAPS AROUND to the minimum!

int x = 2147483647;  // maximum int value
cout << x << "\n";   // prints: 2147483647
x++;                 // add 1... what happens?
cout << x << "\n";   // prints: -2147483648  (OVERFLOW! Wrapped around!)

This is like an old car odometer that hits 999999 and rolls back to 000000. The number wraps around.

How to avoid overflow:

int a = 1000000000;    // 1 billion — fits in int
int b = 1000000000;    // 1 billion — fits in int
// int wrong = a * b;  // OVERFLOW! a*b = 10^18, doesn't fit in int

long long correct = (long long)a * b;  // Cast one to long long before multiplying
cout << correct << "\n";  // 1000000000000000000 ✓

// Rule of thumb: if N can be up to 10^9 and you multiply two such values, use long long

⚡ Pro Tip: When in doubt, use long long. It's slightly slower than int but prevents overflow bugs that are very hard to spot.

2.1.4 Input and Output with cin and cout

Printing Output with cout

int score = 95;
string name = "Alice";

cout << "Score: " << score << "\n";     // Score: 95
cout << name << " got " << score << "\n"; // Alice got 95

// "\n" vs endl
cout << "Line 1" << "\n";   // fast — just a newline character
cout << "Line 2" << endl;   // slow — flushes buffer AND adds newline

⚡ Pro Tip: Always use "\n" instead of endl. The endl flushes the output buffer which is much slower. In problems with lots of output, using endl can cause Time Limit Exceeded!

Reading Input with cin

int n;
cin >> n;    // reads one integer from input

string s;
cin >> s;    // reads one word (stops at whitespace — spaces, tabs, newlines)

double x;
cin >> x;    // reads a decimal number

cin >> automatically skips whitespace between values. This means spaces, tabs, and newlines are all treated the same way. So these two inputs are read identically:

Input style 1 (all on one line):   42 hello 3.14
Input style 2 (on separate lines):
42
hello
3.14

Both work with:

int a; string b; double c;
cin >> a >> b >> c;  // reads all three regardless of formatting

Reading Multiple Values — The Most Common USACO Pattern

USACO problems almost always start with: "Read N, then read N values." Here's how:

Typical USACO input:
5          ← first line: N (the number of items)
10 20 30 40 50   ← next line(s): the N items

int n;
cin >> n;              // read N

for (int i = 0; i < n; i++) {
    int x;
    cin >> x;          // read each item
    cout << x * 2 << "\n";  // process it
}

Complexity Analysis:

• Time: O(N) — read N numbers and process each one in O(1)
• Space: O(1) — only one variable x, no storage of all data

For the input 5\n10 20 30 40 50, this would print:

20
40
60
80
100

Reading a Full Line (Including Spaces)

Sometimes input has multiple words on a line. cin >> only reads one word at a time, so use getline:

string fullName;
getline(cin, fullName);  // reads the entire line, including spaces
cout << "Name: " << fullName << "\n";

🐛 Common Bug: Mixing cin >> and getline can cause problems. After cin >> n, there's a leftover \n in the buffer. If you then call getline, it will read that empty newline instead of the next line. Fix: call cin.ignore() after cin >> before using getline.

Controlling Decimal Output

double y = 3.14159;

cout << y << "\n";                            // 3.14159 (default)
cout << fixed << setprecision(2) << y << "\n"; // 3.14 (exactly 2 decimal places)
cout << fixed << setprecision(6) << y << "\n"; // 3.141590 (6 decimal places)

2.1.5 Basic Arithmetic

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

int main() {
    int a = 17, b = 5;

    cout << a + b << "\n";   // 22  (addition)
    cout << a - b << "\n";   // 12  (subtraction)
    cout << a * b << "\n";   // 85  (multiplication)
    cout << a / b << "\n";   // 3   (INTEGER division — truncates toward zero!)
    cout << a % b << "\n";   // 2   (modulo — the REMAINDER after division)

    // Integer division example:
    // 17 ÷ 5 = 3 remainder 2
    // So: 17 / 5 = 3  and  17 % 5 = 2

    double x = 17.0, y = 5.0;
    cout << x / y << "\n";   // 3.4 (real division when operands are doubles)

    // Shorthand assignment operators:
    int n = 10;
    n += 5;    // same as: n = n + 5   → n is now 15
    n -= 3;    // same as: n = n - 3   → n is now 12
    n *= 2;    // same as: n = n * 2   → n is now 24
    n /= 4;    // same as: n = n / 4   → n is now 6
    n++;       // same as: n = n + 1   → n is now 7
    n--;       // same as: n = n - 1   → n is now 6

    cout << n << "\n";  // 6

    return 0;
}

🤔 Why does integer division truncate?

When both operands are integers, C++ does integer division — it discards the fractional part. 17 / 5 gives 3, not 3.4. This is intentional and very useful (e.g., to find which "group" something falls into).

// How many full hours in 200 minutes?
int minutes = 200;
int hours = minutes / 60;     // 200 / 60 = 3 (not 3.33...)
int remaining = minutes % 60; // 200 % 60 = 20
cout << hours << " hours and " << remaining << " minutes\n";  // 3 hours and 20 minutes

// To get decimal division, at least ONE operand must be a double:
int a = 7, b = 2;
cout << a / b << "\n";           // 3    (integer division)
cout << (double)a / b << "\n";   // 3.5  (cast a to double first)
cout << a / (double)b << "\n";   // 3.5  (cast b to double)
cout << 7.0 / 2 << "\n";        // 3.5  (literal 7.0 is a double)

2.1.6 Your First USACO-Style Program

Let's put everything together and write a complete program that reads input and produces output — just like a real USACO problem.

Problem: Read two integers N and M. Print their sum, difference, product, integer quotient, and remainder.

Thinking through it:

1. We need two variables to store N and M
2. We use cin to read them
3. We use cout to print each result
4. Since N and M could be large, should we use long long? Let's be safe.

💡 Beginner's Problem-Solving Flow:

When facing a problem, don't rush to write code. First think through the steps in plain language:

1. Understand the problem: What is the input? What is the output? What are the constraints?
2. Work through an example by hand: Use the sample input, manually compute the output, confirm you understand the problem
3. Think about data ranges: How large can N and M be? Could there be overflow?
4. Write pseudocode: Read → Compute → Output
5. Translate to C++: Convert pseudocode to real code line by line

This problem: read two numbers → perform five operations → output five results. Very straightforward!

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

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

    long long n, m;
    cin >> n >> m;  // read both numbers on one line

    cout << n + m << "\n";  // sum
    cout << n - m << "\n";  // difference
    cout << n * m << "\n";  // product
    cout << n / m << "\n";  // integer quotient
    cout << n % m << "\n";  // remainder

    return 0;
}

Complexity Analysis:

• Time: O(1) — only a fixed number of arithmetic operations
• Space: O(1) — only two variables

Sample Input:

17 5

Sample Output:

22
12
85
3
2

⚠️ Common Mistakes in Chapter 2.1

Chapter Summary

📌 Key Takeaways

❓ FAQ

Q1: Does bits/stdc++.h slow down compilation?

A: Yes, compilation time may increase by 1-2 seconds. But in contests, compilation time is not counted toward the time limit, so it doesn't affect results. Don't use it in production projects.

Q2: Which should I default to — int or long long?

A: Rule of thumb — when in doubt, use long long. It's slightly slower than int (nearly imperceptible on modern CPUs), but prevents overflow. Especially note: if two int values are multiplied, the result may need long long.

Q3: Why can't I use scanf/printf in USACO?

A: You actually can! But after adding sync_with_stdio(false), you cannot mix cin/cout with scanf/printf. Beginners are advised to stick with cin/cout — it's safer.

Q4: Can I omit return 0;?

A: In C++11 and later, if main() reaches the end without a return, the compiler automatically returns 0. So technically it can be omitted, but writing it is clearer.

Q5: My code runs correctly locally, but gets Wrong Answer (WA) on the USACO judge. What could be wrong?

A: The three most common reasons: ① Integer overflow (used int when long long was needed); ② Not handling all edge cases; ③ Wrong output format (extra or missing spaces/newlines).

🔗 Connections to Later Chapters

• Chapter 2.2 (Control Flow) builds on this chapter by adding if/else conditionals and for/while loops, enabling you to handle "repeat N times" tasks
• Chapter 2.3 (Functions & Arrays) introduces functions (organizing code into reusable blocks) and arrays (storing a collection of data) — core tools for solving USACO problems
• Chapter 3.1 (STL Essentials) introduces STL tools like vector and sort, greatly simplifying the logic you write manually in this chapter
• The integer overflow prevention techniques learned in this chapter will appear throughout the book, especially in Chapter 3.2 (Prefix Sums) and Chapters 6.1–6.3 (DP)

Practice Problems

Work through all problems in order — they get progressively harder. Each has a complete solution you can reveal after trying it yourself.

🌡️ Warm-Up Problems

These problems only require 1-3 lines of new code each. They're meant to help you practice typing C++ and running programs.

Warm-up 2.1.1 — Personal Greeting Write a program that prints exactly this (with your own name):

Hello, Alice!
My favorite number is 7.
I am learning C++.

(You can hardcode all values — no input needed.)

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

int main() {
    cout << "Hello, Alice!\n";
    cout << "My favorite number is 7.\n";
    cout << "I am learning C++.\n";
    return 0;
}

Warm-up 2.1.2 — Five Lines Print the numbers 1 through 5, each on its own line. Use exactly 5 separate cout statements (no loops yet — we cover loops in Chapter 2.2).

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

int main() {
    cout << 1 << "\n";
    cout << 2 << "\n";
    cout << 3 << "\n";
    cout << 4 << "\n";
    cout << 5 << "\n";
    return 0;
}

Warm-up 2.1.3 — Double It Read one integer from input. Print that integer multiplied by 2.

Sample Input: 7 Sample Output: 14

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

int main() {
    int n;
    cin >> n;
    cout << n * 2 << "\n";
    return 0;
}

Warm-up 2.1.4 — Sum of Two Read two integers on the same line. Print their sum.

Sample Input: 15 27 Sample Output: 42

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

int main() {
    int a, b;
    cin >> a >> b;
    cout << a + b << "\n";
    return 0;
}

Warm-up 2.1.5 — Say Hi Read a single word (a first name, no spaces). Print Hi, [name]!

Sample Input: Bob Sample Output: Hi, Bob!

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

int main() {
    string name;
    cin >> name;
    cout << "Hi, " << name << "!\n";
    return 0;
}

🏋️ Core Practice Problems

These problems require combining input, arithmetic, and output. Think through the math before coding.

Problem 2.1.6 — Age in Days Read a person's age in whole years. Print their approximate age in days (use 365 days per year, ignore leap years).

Sample Input: 15 Sample Output: 5475

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

int main() {
    int years;
    cin >> years;
    cout << years * 365 << "\n";
    return 0;
}

Problem 2.1.7 — Seconds Converter Read a number of seconds S (1 ≤ S ≤ 10^9). Convert it to hours, minutes, and remaining seconds.

Sample Input: 3661 Sample Output:

1 hours
1 minutes
1 seconds

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

int main() {
    long long s;
    cin >> s;

    long long hours = s / 3600;         // 3600 seconds per hour
    long long remaining = s % 3600;     // seconds left after removing full hours
    long long minutes = remaining / 60; // 60 seconds per minute
    long long seconds = remaining % 60; // seconds left after removing full minutes

    cout << hours << " hours\n";
    cout << minutes << " minutes\n";
    cout << seconds << " seconds\n";

    return 0;
}

Problem 2.1.8 — Rectangle Read the length L and width W of a rectangle. Print its area and perimeter.

Sample Input: 6 4 Sample Output:

Area: 24
Perimeter: 20

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

int main() {
    long long L, W;
    cin >> L >> W;

    cout << "Area: " << L * W << "\n";
    cout << "Perimeter: " << 2 * (L + W) << "\n";

    return 0;
}

Problem 2.1.9 — Temperature Converter Read a temperature in Celsius. Print the equivalent in Fahrenheit. Formula: F = C × 9/5 + 32

Sample Input: 100 Sample Output: 212.00

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

int main() {
    double celsius;
    cin >> celsius;

    double fahrenheit = celsius * 9.0 / 5.0 + 32.0;

    cout << fixed << setprecision(2) << fahrenheit << "\n";

    return 0;
}

Problem 2.1.10 — Coin Counter Read four integers: the number of quarters (25¢), dimes (10¢), nickels (5¢), and pennies (1¢). Print the total value in cents.

Sample Input:

3 2 1 4

(3 quarters, 2 dimes, 1 nickel, 4 pennies)

Sample Output: 104

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

int main() {
    int quarters, dimes, nickels, pennies;
    cin >> quarters >> dimes >> nickels >> pennies;

    int total = quarters * 25 + dimes * 10 + nickels * 5 + pennies * 1;

    cout << total << "\n";

    return 0;
}

🏆 Challenge Problems

These require more thought — especially around data types and problem-solving.

Challenge 2.1.11 — Overflow Detector Read two integers A and B (each up to 10^9). Compute their product TWO ways: as an int and as a long long. Print both results. Observe the difference when overflow occurs.

Sample Input: 1000000000 3 Sample Output:

int product: -1294967296
long long product: 3000000000

(The int result is wrong due to overflow; long long is correct.)

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

int main() {
    long long a, b;
    cin >> a >> b;

    // Cast to int FIRST to force integer overflow
    int int_product = (int)a * (int)b;

    // Long long multiplication — no overflow for values up to 10^9
    long long ll_product = a * b;

    cout << "int product: " << int_product << "\n";
    cout << "long long product: " << ll_product << "\n";

    return 0;
}

Challenge 2.1.12 — USACO-Style Large Multiply You're given two integers N and M (1 ≤ N, M ≤ 10^9). Print their product. (This seems simple, but requires long long.)

Sample Input: 1000000000 1000000000 Sample Output: 1000000000000000000

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

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

    long long n, m;
    cin >> n >> m;

    cout << n * m << "\n";

    return 0;
}

Challenge 2.1.13 — Quadrant Problem (USACO 2016 February Bronze) Read two non-zero integers x and y. Determine which quadrant of the coordinate plane the point (x, y) is in:

• Quadrant 1: x > 0 and y > 0
• Quadrant 2: x < 0 and y > 0
• Quadrant 3: x < 0 and y < 0
• Quadrant 4: x > 0 and y < 0

Print just the number: 1, 2, 3, or 4.

Sample Input 1: 3 5 → Output: 1 Sample Input 2: -1 2 → Output: 2 Sample Input 3: -4 -7 → Output: 3 Sample Input 4: 8 -3 → Output: 4

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

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

    int x, y;
    cin >> x >> y;

    if (x > 0 && y > 0) {
        cout << 1 << "\n";
    } else if (x < 0 && y > 0) {
        cout << 2 << "\n";
    } else if (x < 0 && y < 0) {
        cout << 3 << "\n";
    } else {  // x > 0 && y < 0
        cout << 4 << "\n";
    }

    return 0;
}

Chapter 2.2: Control Flow

📝 Prerequisites: Chapter 2.1 (variables, cin/cout, basic arithmetic)

2.2.0 What is "Control Flow"?

So far, every program we wrote ran top to bottom — line 1, line 2, line 3, done. Like reading a book straight through.

But real programs need to make decisions and repeat things. That's what "control flow" means — controlling the flow (order) of execution.

Think of it like a "Choose Your Own Adventure" book:

• Sometimes you're told "if you want to fight the dragon, turn to page 47; otherwise turn to page 52"
• Sometimes you're told "repeat this section until you escape the dungeon"

C++ gives us exactly this with:

• if/else — make decisions based on conditions
• for/while loops — repeat a section of code

Here's a visual overview:

In the loop diagram: the program keeps going back to Step 2 until the condition becomes false, then it exits to Step 3.

2.2.1 The if Statement

The if statement lets your program make a decision: "if this condition is true, do this thing."

Basic if

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

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

    if (score >= 90) {
        cout << "Excellent!\n";
    }

    cout << "Done.\n";  // always runs regardless of score
    return 0;
}

If score is 95: prints Excellent! then Done. If score is 80: prints only Done. (the if-block is skipped)

if / else

int score;
cin >> score;

if (score >= 60) {
    cout << "Pass\n";
} else {
    cout << "Fail\n";
}

The else block runs only when the if condition is false. Exactly one of the two blocks will run.

if / else if / else Chains

When you have multiple conditions to check:

int score;
cin >> score;

if (score >= 90) {
    cout << "A\n";
} else if (score >= 80) {
    cout << "B\n";
} else if (score >= 70) {
    cout << "C\n";
} else if (score >= 60) {
    cout << "D\n";
} else {
    cout << "F\n";
}

C++ checks these conditions in order, from top to bottom, and runs the first one that's true. Once it runs one block, it skips all the remaining else if/else blocks.

So if score = 85:

1. Is 85 >= 90? No → skip
2. Is 85 >= 80? Yes → print "B", then jump past all the else-ifs

🤔 Why does this work? When we reach else if (score >= 80), we already know score < 90 (because if it were ≥ 90, the first condition would have caught it). Each else if implicitly assumes all the previous conditions were false.

Comparison Operators

Logical Operators (Combining Conditions)

int x, y;
cin >> x >> y;

if (x > 0 && y > 0) {
    cout << "Both positive\n";
}

if (x < 0 || y < 0) {
    cout << "At least one is negative\n";
}

bool done = false;
if (!done) {
    cout << "Still working...\n";
}

🐛 Common Bug: = vs ==

This is one of the most common mistakes for beginners (and even experienced programmers!):

int x = 5;

// DANGEROUS BUG:
if (x = 10) {   // This ASSIGNS 10 to x, doesn't compare!
                 // x becomes 10, and since 10 is nonzero, this is always TRUE
    cout << "x is 10\n";  // This ALWAYS runs, even though x started as 5!
}

// CORRECT:
if (x == 10) {  // This COMPARES x with 10
    cout << "x is 10\n";  // Only runs when x actually equals 10
}

The = operator assigns (stores a value). The == operator compares (checks if two values are equal). They look similar but do completely different things.

⚡ Pro Tip: Some programmers write 10 == x instead of x == 10 — if you accidentally type = instead of ==, it becomes 10 = x which is a compile error (you can't assign to a literal). This is called a "Yoda condition."

Nested if Statements

You can put if statements inside other if statements:

int age, income;
cin >> age >> income;

if (age >= 18) {
    cout << "Adult\n";
    if (income > 50000) {
        cout << "High income adult\n";
    } else {
        cout << "Standard income adult\n";
    }
} else {
    cout << "Minor\n";
}

Be careful: each else matches the nearest preceding if that doesn't already have an else.

2.2.2 The while Loop

A while loop repeats a block of code as long as its condition is true. When the condition becomes false, execution continues after the loop.

while (condition) {
    body (runs over and over)
}

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

int main() {
    int i = 1;             // 1. Initialize before the loop
    while (i <= 5) {       // 2. Check condition — if false, skip the loop
        cout << i << "\n"; // 3. Run the body
        i++;               // 4. Update — VERY IMPORTANT! Forget this → infinite loop
    }
    // After loop: i = 6, condition 6 <= 5 is false, loop exits
    return 0;
}

Output:

1
2
3
4
5

🐛 Common Bug: Infinite Loop

If you forget to update the variable (step 4 above), the condition never becomes false and the loop runs forever!

int i = 1;
while (i <= 5) {
    cout << i << "\n";
    // BUG: forgot i++ — this prints "1" forever!
}

If your program seems stuck, press Ctrl+C to stop it.

When to use while vs for

• Use while when you don't know in advance how many iterations you need
• Use for when you do know the count (we'll cover for next)

Classic while use case: read until a condition is met.

// Common USACO pattern: read until end of input
int x;
while (cin >> x) {    // cin >> x returns false when input runs out
    cout << x * 2 << "\n";
}

do-while Loop

A do-while loop always runs its body at least once, then checks the condition:

int n;
do {
    cin >> n;
} while (n <= 0);   // keep re-reading until user gives a positive number

This is useful when you want to execute something before checking whether to repeat. It's rare in competitive programming but worth knowing.

2.2.3 The for Loop

The for loop is the most used loop in competitive programming. It packages initialization, condition-check, and update into one clean line:

for (initialization; condition; update) {
    body
}

This is equivalent to:

initialization;
while (condition) {
    body
    update;
}

Visual: For Loop Flowchart

The flowchart above traces the execution: initialization runs once, then the condition is checked before every iteration. When false, the loop exits.

Common for Patterns

// Count from 0 to 9 (standard competitive programming pattern)
for (int i = 0; i < 10; i++) {
    cout << i << " ";
}
// Prints: 0 1 2 3 4 5 6 7 8 9

// Count from 1 to n (inclusive)
int n = 5;
for (int i = 1; i <= n; i++) {
    cout << i << " ";
}
// Prints: 1 2 3 4 5

// Count backwards
for (int i = 10; i >= 1; i--) {
    cout << i << " ";
}
// Prints: 10 9 8 7 6 5 4 3 2 1

// Count by steps of 2
for (int i = 0; i <= 10; i += 2) {
    cout << i << " ";
}
// Prints: 0 2 4 6 8 10

🧠 Loop Tracing: Understanding Exactly What Happens

When learning loops, trace through them manually. Here's how:

Code: for (int i = 0; i < 4; i++) cout << i * i << " ";

Practice tracing loops on paper before running them — it builds intuition and helps spot bugs.

The Most Common USACO Loop Pattern

Read N numbers and process each one:

int n;
cin >> n;

for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    // process x here
    cout << x * 2 << "\n";
}

⚡ Pro Tip: In competitive programming, for (int i = 0; i < n; i++) with 0-based indexing is standard. It matches how arrays are indexed (Chapter 2.3), so everything lines up neatly.

2.2.4 Nested Loops

You can put a loop inside another loop. The inner loop runs completely for each single iteration of the outer loop.

// Print a 4x4 multiplication table
for (int i = 1; i <= 4; i++) {         // outer: rows
    for (int j = 1; j <= 4; j++) {     // inner: columns
        cout << i * j << "\t";          // \t = tab character
    }
    cout << "\n";  // newline after each row
}

Output:

1   2   3   4
2   4   6   8
3   6   9   12
4   8   12  16

Tracing the first two rows:

i=1: j=1→print 1, j=2→print 2, j=3→print 3, j=4→print 4, then newline
i=2: j=1→print 2, j=2→print 4, j=3→print 6, j=4→print 8, then newline
...

⚠️ Nested Loop Time Complexity

💡 Why should you care about loop counts? In competitions, your program typically needs to finish within 1-2 seconds. A modern computer can execute roughly 10^8 to 10^9 simple operations per second. So if you can estimate how many times your loop body executes in total, you can determine whether it will exceed the time limit (TLE). This is the core idea behind "time complexity analysis" — we'll study it in greater depth in later chapters.

A single loop of N iterations does N operations. Two nested loops of N do N × N = N² operations.

If N = 1000 and you have two nested loops, that's 10^6 operations — fine. But if N = 100,000, that's 10^10 — too slow!

🧠 Quick Rule of Thumb: After seeing the range of N, use the table above to work backwards and determine the maximum number of nested loops you can afford. For example, N ≤ 10^5 → you can only use O(N) or O(N log N) algorithms; N ≤ 5000 → O(N²) is acceptable. This technique is extremely useful in USACO!

2.2.5 Switch Statements

When you have a variable and want to check many specific values, switch is cleaner than a long chain of if/else if:

int day;
cin >> day;

switch (day) {
    case 1:
        cout << "Monday\n";
        break;   // IMPORTANT: break exits the switch
    case 2:
        cout << "Tuesday\n";
        break;
    case 3:
        cout << "Wednesday\n";
        break;
    case 4:
        cout << "Thursday\n";
        break;
    case 5:
        cout << "Friday\n";
        break;
    case 6:
    case 7:
        cout << "Weekend!\n";  // cases 6 and 7 share this code
        break;
    default:
        cout << "Invalid day\n";  // runs if no case matches
}

When to use switch vs if-else

🐛 Common Bug: Forgetting break — Without break, execution "falls through" to the next case!

int x = 2;
switch (x) {
    case 1:
        cout << "one\n";
    case 2:
        cout << "two\n";   // this runs
    case 3:
        cout << "three\n"; // ALSO runs (fall-through!) because no break after case 2
}
// Output: two\nthree\n  (surprising!)

2.2.6 break and continue

break — Exit the Loop Immediately

// Find the first number divisible by 7 between 1 and 100
for (int i = 1; i <= 100; i++) {
    if (i % 7 == 0) {
        cout << "First multiple of 7: " << i << "\n";  // prints 7
        break;  // stop searching — we found it
    }
}

continue — Skip to the Next Iteration

// Print all numbers 1 to 10 except multiples of 3
for (int i = 1; i <= 10; i++) {
    if (i % 3 == 0) {
        continue;  // skip the rest of this iteration, go to i++
    }
    cout << i << " ";
}
// Output: 1 2 4 5 7 8 10

break in Nested Loops

break only exits the innermost loop. To exit multiple levels, use a flag variable:

bool found = false;
int target = 25;

for (int i = 0; i < 10 && !found; i++) {    // outer loop also checks !found
    for (int j = 0; j < 10; j++) {
        if (i * j == target) {
            cout << i << " * " << j << " = " << target << "\n";
            found = true;
            break;   // exits inner loop; outer loop exits too because of !found
        }
    }
}

2.2.7 Classic Loop Patterns in Competitive Programming

These patterns appear in nearly every USACO solution. Learn them cold.

Pattern 1: Read N Numbers, Compute Sum

int n;
cin >> n;

long long sum = 0;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    sum += x;
}
cout << sum << "\n";

Complexity Analysis:

• Time: O(N) — iterate through N numbers, each processed in O(1)
• Space: O(1) — only one accumulator variable sum

Pattern 2: Find Maximum (and Minimum) in a List

int n;
cin >> n;

int maxVal, minVal;
cin >> maxVal;    // read first element
minVal = maxVal;  // initialize both max and min to first element

for (int i = 1; i < n; i++) {   // start from 2nd element (index 1)
    int x;
    cin >> x;
    if (x > maxVal) maxVal = x;
    if (x < minVal) minVal = x;
}

cout << "Max: " << maxVal << "\n";
cout << "Min: " << minVal << "\n";

Complexity Analysis:

• Time: O(N) — iterate through N numbers, each comparison in O(1)
• Space: O(1) — only two variables maxVal and minVal

🤔 Why initialize to the first element? Don't initialize max to 0! What if all numbers are negative? Initializing to the first element guarantees we start with a real value from the input.

Pattern 3: Count How Many Satisfy a Condition

int n;
cin >> n;

int count = 0;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (x % 2 == 0) {   // condition: even number
        count++;
    }
}
cout << "Even count: " << count << "\n";

Pattern 4: Print a Star Triangle Pattern

int n;
cin >> n;

for (int row = 1; row <= n; row++) {     // row goes from 1 to n
    for (int col = 1; col <= row; col++) { // print `row` stars per row
        cout << "*";
    }
    cout << "\n";  // newline after each row
}

For n=4, output:

*
**
***
****

Pattern 5: Compute Sum of Digits

int n;
cin >> n;

int digitSum = 0;
while (n > 0) {
    digitSum += n % 10;  // last digit
    n /= 10;             // remove last digit
}
cout << digitSum << "\n";

Tracing for n = 12345:

n=12345: digitSum += 5, n becomes 1234
n=1234:  digitSum += 4, n becomes 123
n=123:   digitSum += 3, n becomes 12
n=12:    digitSum += 2, n becomes 1
n=1:     digitSum += 1, n becomes 0
n=0: loop exits. digitSum = 15 ✓

2.2.8 Complete Example: USACO-Style Problem

Problem: You have N cows. Each cow has a milk production rating. Find the highest-rated cow's rating and count how many cows produce above-average milk.

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

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

    int n;
    cin >> n;

    // We need to store all values to compare against the average
    // (We'll learn arrays/vectors in Chapter 2.3 — for now use two passes)

    // First pass: find sum and max
    long long sum = 0;
    int maxMilk = 0;
    vector<int> milk(n);   // store all values (preview of Chapter 2.3)

    for (int i = 0; i < n; i++) {
        cin >> milk[i];
        sum += milk[i];
        if (milk[i] > maxMilk) maxMilk = milk[i];
    }

    double avg = (double)sum / n;

    // Second pass: count above-average
    int aboveAvg = 0;
    for (int i = 0; i < n; i++) {
        if (milk[i] > avg) aboveAvg++;
    }

    cout << "Maximum: " << maxMilk << "\n";
    cout << "Above average: " << aboveAvg << "\n";

    return 0;
}

Sample Input:

5
10 20 30 40 50

Sample Output:

Maximum: 50
Above average: 2

(Average is 30; cows with 40 and 50 are above average → 2 cows)

Complexity Analysis:

• Time: O(N) — two passes (read + count), each O(N), total O(2N) = O(N)
• Space: O(N) — uses vector<int> milk(n) to store all data

⚠️ Common Mistakes in Chapter 2.2

Chapter Summary

📌 Key Takeaways

🧩 Five Classic Loop Patterns Quick Reference

❓ FAQ (Frequently Asked Questions)

Q1: Can for and while replace each other? When should I use which?

A: Yes, any for loop can be rewritten as a while loop, and vice versa. Rule of thumb: if you know the number of iterations (e.g., "loop N times"), use for; if you don't know the count (e.g., "read until end of input"), use while. In competitions, for is used about 90% of the time.

Q2: How many levels deep can nested loops go? Is there a limit?

A: Syntactically there's no limit, but in practice you should be cautious beyond 3 levels. Two nested loops give O(N²), three give O(N³). When N ≥ 1000, three nested loops can easily time out. If you find yourself needing more than 3 levels of nesting, it usually means you need a more efficient algorithm (covered in later chapters).

Q3: break only exits the innermost loop. How do I break out of multiple nested loops at once?

A: Two common approaches: ① Use a bool found = false flag variable, and have the outer loop also check !found; ② Wrap the nested loops in a function and use return to exit directly. Approach ① is more common — see Section 2.2.6 for a complete example.

Q4: Which is faster, switch or if-else if?

A: For a small number of cases (< 10), performance is virtually identical. The advantage of switch is code readability, not speed. In competitions, you can freely choose either. If conditions involve range comparisons (like x > 10), you must use if-else.

Q5: My program produces correct output, but after submission it shows TLE (Time Limit Exceeded). What should I do?

A: Step one: estimate your algorithm's complexity. Look at the range of N → use the "nested loop complexity table" from this chapter to estimate total operations → if it exceeds 10^8, you need to optimize. Common optimization strategies include: reducing the number of loop levels, replacing brute-force search with sorting + binary search (Chapter 3.3), and replacing repeated summation with prefix sums (Chapter 3.2).

🔗 Connections to Later Chapters

• Chapter 2.3 (Functions & Arrays) will let you encapsulate the loop patterns from this chapter into functions, and use arrays to store collections of data
• Chapter 3.2 (Arrays & Prefix Sums) will teach you how to optimize O(N²) range sum queries to O(N) preprocessing + O(1) per query — one of the solutions for when "nested loops are too slow"
• Chapter 3.3 (Sorting & Searching) will teach you binary search, optimizing the O(N) linear search from this chapter to O(log N)
• The five classic loop patterns learned in this chapter (summation, finding max/min, counting, nested iteration, digit processing) are the foundational building blocks for all algorithms in this book
• Nested loop complexity analysis is the first step toward understanding time complexity (a theme throughout the entire book)

Practice Problems

🌡️ Warm-Up Problems

Warm-up 2.2.1 — Count to Ten Print the numbers 1 through 10, each on its own line. Use a for loop.

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

int main() {
    for (int i = 1; i <= 10; i++) {
        cout << i << "\n";
    }
    return 0;
}

Warm-up 2.2.2 — Even Numbers Print all even numbers from 2 to 20, each on its own line.

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

int main() {
    // Option 1: step by 2
    for (int i = 2; i <= 20; i += 2) {
        cout << i << "\n";
    }
    return 0;
}

Warm-up 2.2.3 — Sign Check Read one integer. Print Positive if it's > 0, Negative if it's < 0, Zero if it's 0.

Sample Input: -5 → Output: Negative

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

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

    if (n > 0) {
        cout << "Positive\n";
    } else if (n < 0) {
        cout << "Negative\n";
    } else {
        cout << "Zero\n";
    }

    return 0;
}

Warm-up 2.2.4 — Multiplication Table of 3 Print the first 10 multiples of 3 (i.e., 3, 6, 9, ..., 30), each on its own line.

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

int main() {
    for (int i = 1; i <= 10; i++) {
        cout << i * 3 << "\n";
    }
    return 0;
}

Warm-up 2.2.5 — Sum of Five Read exactly 5 integers (on separate lines or the same line). Print their sum.

Sample Input: 3 7 2 8 5 → Output: 25

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

int main() {
    long long sum = 0;
    for (int i = 0; i < 5; i++) {
        int x;
        cin >> x;
        sum += x;
    }
    cout << sum << "\n";
    return 0;
}

🏋️ Core Practice Problems

Problem 2.2.6 — FizzBuzz The classic programming challenge: print numbers from 1 to 100. But:

• If the number is divisible by 3, print Fizz instead
• If divisible by 5, print Buzz instead
• If divisible by both 3 and 5, print FizzBuzz instead

First few lines of output:

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz

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

int main() {
    for (int i = 1; i <= 100; i++) {
        if (i % 3 == 0 && i % 5 == 0) {
            cout << "FizzBuzz\n";
        } else if (i % 3 == 0) {
            cout << "Fizz\n";
        } else if (i % 5 == 0) {
            cout << "Buzz\n";
        } else {
            cout << i << "\n";
        }
    }
    return 0;
}

Problem 2.2.7 — Minimum of N Read N (1 ≤ N ≤ 1000), then read N integers. Print the minimum value.

Sample Input:

5
8 3 7 1 9

Sample Output: 1

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

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

    int n;
    cin >> n;

    int first;
    cin >> first;
    int minVal = first;  // initialize to first element

    for (int i = 1; i < n; i++) {   // read remaining n-1 elements
        int x;
        cin >> x;
        if (x < minVal) {
            minVal = x;
        }
    }

    cout << minVal << "\n";
    return 0;
}

Problem 2.2.8 — Count Positives Read N (1 ≤ N ≤ 1000), then read N integers. Print how many of them are strictly positive (> 0).

Sample Input:

6
3 -1 0 5 -2 7

Sample Output: 3

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

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

    int n;
    cin >> n;

    int count = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x > 0) {
            count++;
        }
    }

    cout << count << "\n";
    return 0;
}

Problem 2.2.9 — Star Triangle Read N. Print a right triangle of * characters with N rows, where row i has i stars.

Sample Input: 4

Sample Output:

*
**
***
****

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

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

    for (int row = 1; row <= n; row++) {
        for (int star = 1; star <= row; star++) {
            cout << "*";
        }
        cout << "\n";
    }

    return 0;
}

Problem 2.2.10 — Sum of Digits Read a positive integer N (1 ≤ N ≤ 10^9). Print the sum of its digits.

Sample Input: 12345 → Sample Output: 15 Sample Input: 9999 → Sample Output: 36

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

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

    int digitSum = 0;
    while (n > 0) {
        digitSum += n % 10;  // add last digit
        n /= 10;             // remove last digit
    }

    cout << digitSum << "\n";
    return 0;
}

🏆 Challenge Problems

Challenge 2.2.11 — Collatz Sequence The Collatz sequence starting from N works as follows:

• If N is even: next = N / 2
• If N is odd: next = N * 3 + 1
• Stop when N = 1

Read N. Print the entire sequence (including N and 1). Also print how many steps it takes to reach 1.

Sample Input: 6 Sample Output:

6 3 10 5 16 8 4 2 1
Steps: 8

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

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

    int steps = 0;
    cout << n;         // print starting number

    while (n != 1) {
        if (n % 2 == 0) {
            n = n / 2;
        } else {
            n = n * 3 + 1;
        }
        cout << " " << n;  // print each next number
        steps++;
    }
    cout << "\n";
    cout << "Steps: " << steps << "\n";

    return 0;
}

Challenge 2.2.12 — Prime Check Read N (2 ≤ N ≤ 10^6). Print prime if N is prime, composite otherwise.

A number is prime if it has no divisors other than 1 and itself.

Sample Input: 17 → Output: prime Sample Input: 100 → Output: composite

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

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

    bool isPrime = true;

    if (n < 2) {
        isPrime = false;
    } else {
        // Check divisors from 2 to sqrt(n)
        for (int i = 2; (long long)i * i <= n; i++) {
            if (n % i == 0) {
                isPrime = false;
                break;  // found a divisor, no need to continue
            }
        }
    }

    cout << (isPrime ? "prime" : "composite") << "\n";
    return 0;
}

Challenge 2.2.13 — Highest Rated Cow Read N (1 ≤ N ≤ 1000), then read N pairs of (cow name, rating). Find and print the name of the cow with the highest rating.

Sample Input:

4
Bessie 95
Elsie 82
Moo 95
Daisy 88

Sample Output: Bessie (If there's a tie, print the name of the first one that appeared.)

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

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

    int n;
    cin >> n;

    string bestName;
    int bestRating = -1;  // initialize to -1 so any real rating beats it

    for (int i = 0; i < n; i++) {
        string name;
        int rating;
        cin >> name >> rating;

        if (rating > bestRating) {
            bestRating = rating;
            bestName = name;
        }
    }

    cout << bestName << "\n";
    return 0;
}

Chapter 2.3: Functions & Arrays

📝 Prerequisites: Chapters 2.1 & 2.2 (variables, loops, if/else)

As your programs grow larger, you need ways to organize code (functions) and store collections of data (arrays and vectors). This chapter introduces both — two of the most important tools in competitive programming.

2.3.1 Functions — What and Why

🍕 The Recipe Analogy

A function is like a pizza recipe:

- Input (parameters):   ingredients — flour, cheese, tomatoes
- Process (body):       the cooking steps
- Output (return value): the finished pizza

Just like you can make many pizzas using one recipe,
you can call a function many times with different inputs.

pizza("thin crust", "pepperoni")  → one pizza
pizza("thick crust", "mushroom")  → another pizza

Without functions, if you need to compute "is this number prime?" in five different places, you'd copy-paste the same 10 lines of code five times. Then if you find a bug, you have to fix it in all five places!

When to Write a Function

Use a function when:

1. You repeat the same logic 3+ times in your program
2. A block of code does one clear, named thing (e.g., "check if prime", "compute distance")
3. Your main is getting too long to read comfortably

Basic Function Syntax

returnType functionName(parameter1Type param1, parameter2Type param2, ...) {
    // function body
    return value;  // must match returnType; omit for void functions
}

Your First Functions

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

// ---- FUNCTION DEFINITIONS (must come BEFORE they are used, or use prototypes) ----

// Takes one integer, returns its square
int square(int x) {
    return x * x;
}

// Takes two integers, returns the larger one
int maxOf(int a, int b) {
    if (a > b) return a;
    else return b;
}

// void function: does something but doesn't return a value
void printSeparator() {
    cout << "====================\n";
}

// ---- MAIN ----
int main() {
    cout << square(5) << "\n";       // calls square with x=5, prints 25
    cout << square(12) << "\n";      // calls square with x=12, prints 144

    cout << maxOf(7, 3) << "\n";     // prints 7
    cout << maxOf(-5, -2) << "\n";   // prints -2

    printSeparator();                // prints the divider line
    cout << "Done!\n";
    printSeparator();

    return 0;
}

🤔 Why do functions come before main?

C++ reads your file top-to-bottom. When it sees a call like square(5), it needs to already know what square means. If square is defined after main, the compiler will say "I've never heard of square!"

Solution 1: Define all functions above main (simplest approach).

Solution 2: Use a function prototype — a forward declaration telling the compiler "this function exists, I'll define it later":

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

int square(int x);       // prototype — just the signature, no body
int maxOf(int a, int b); // prototype

int main() {
    cout << square(5) << "\n";   // OK! compiler knows square exists
    return 0;
}

// Full definitions can come after main
int square(int x) {
    return x * x;
}

int maxOf(int a, int b) {
    return (a > b) ? a : b;
}

2.3.2 Void Functions vs Return Functions

void functions: Do something, return nothing

// void functions perform an action
void printLine(int n) {
    for (int i = 0; i < n; i++) {
        cout << "-";
    }
    cout << "\n";
}

// Calling a void function — just call it, don't try to capture a value
printLine(10);    // prints: ----------
printLine(20);    // prints: --------------------

Return functions: Compute and give back a value

// Returns the absolute value of x
int absoluteValue(int x) {
    if (x < 0) return -x;
    return x;
}

// Calling a return function — capture the result in a variable or use it directly
int result = absoluteValue(-7);
cout << result << "\n";           // 7
cout << absoluteValue(-3) << "\n"; // 3 (used directly)

Multiple return statements

A function can have multiple return statements — execution stops at the first one reached:

string classify(int n) {
    if (n < 0) return "negative";   // exits here if n < 0
    if (n == 0) return "zero";      // exits here if n == 0
    return "positive";              // exits here otherwise
}

cout << classify(-5) << "\n";   // negative
cout << classify(0) << "\n";    // zero
cout << classify(3) << "\n";    // positive

2.3.3 Pass by Value vs Pass by Reference

When you pass a variable to a function, there are two ways it can happen. Understanding this is crucial.

Pass by Value (default): Function gets a COPY

void addOne_byValue(int x) {
    x++;  // modifies the LOCAL COPY — original is unchanged
    cout << "Inside function: " << x << "\n";  // 6
}

int main() {
    int n = 5;
    addOne_byValue(n);
    cout << "After function: " << n << "\n";   // still 5! original unchanged
    return 0;
}

Think of it like a photocopy: the function works on a photocopy of the paper. Changes to the photocopy don't affect the original.

Pass by Reference (&): Function works on the ORIGINAL

void addOne_byRef(int& x) {  // & means "reference to the original"
    x++;  // modifies the ORIGINAL variable directly
    cout << "Inside function: " << x << "\n";  // 6
}

int main() {
    int n = 5;
    addOne_byRef(n);
    cout << "After function: " << n << "\n";   // now 6! original was changed
    return 0;
}

When to use each

Multiple Return Values via References

A C++ function can only return one value. But you can "return" multiple values through reference parameters:

// Computes both quotient AND remainder simultaneously
void divmod(int a, int b, int& quotient, int& remainder) {
    quotient = a / b;
    remainder = a % b;
}

int main() {
    int q, r;
    divmod(17, 5, q, r);  // q and r are modified by the function
    cout << "17 / 5 = " << q << " remainder " << r << "\n";
    // prints: 17 / 5 = 3 remainder 2
    return 0;
}

2.3.4 Recursion

A recursive function is one that calls itself. It's perfect for problems that break down into smaller versions of the same problem.

Classic Example: Factorial

5! = 5 × 4 × 3 × 2 × 1 = 120
   = 5 × (4!)              ← same problem, smaller input!

💡 Three-Step Recursive Thinking:

1. Find "self-similarity": Can the original problem be broken into smaller problems of the same type? 5! = 5 × 4!, and 4! and 5! are the same type ✓
2. Identify the base case: What is the smallest case? 0! = 1, cannot be broken down further
3. Write the inductive step: n! = n × (n-1)!, call yourself with smaller input

This thinking process will be used repeatedly in Graph Algorithms (Chapter 5.1) and Dynamic Programming (Chapters 6.1–6.3).

int factorial(int n) {
    if (n == 0) return 1;            // BASE CASE: stop recursing
    return n * factorial(n - 1);    // RECURSIVE CASE: reduce to smaller problem
}

Tracing factorial(4):

factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * (1 * factorial(0))))
= 4 * (3 * (2 * (1 * 1)))   ← base case!
= 4 * (3 * (2 * 1))
= 4 * (3 * 2)
= 4 * 6
= 24  ✓

Every recursive function needs:

1. A base case — stops the recursion (prevents infinite recursion)
2. A recursive case — calls itself with a smaller input

🐛 Common Bug: Forgetting the base case → infinite recursion → "Stack Overflow" crash!

2.3.5 Arrays — Fixed Collections

🏠 The Mailbox Analogy

An array is like a row of mailboxes on a street:
- All mailboxes are the same size (same type)
- Each has a number on the door (the index, starting from 0)
- You can go directly to any mailbox by its number

Visual: Array Memory Layout

Arrays are stored as consecutive blocks of memory. Each element sits right next to the previous one, allowing O(1) random access.

Array Basics

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

int main() {
    // Declare an array of 5 integers (elements are uninitialized — garbage values!)
    int arr[5];

    // Assign values one by one
    arr[0] = 10;
    arr[1] = 20;
    arr[2] = 30;
    arr[3] = 40;
    arr[4] = 50;

    // Declare AND initialize at the same time
    int nums[5] = {1, 2, 3, 4, 5};

    // Initialize all elements to zero
    int zeros[100] = {};          // all 100 elements = 0
    int zeros2[100];
    fill(zeros2, zeros2 + 100, 0); // another way

    // Access and print
    cout << arr[2] << "\n";       // 30

    // Loop through the array
    for (int i = 0; i < 5; i++) {
        cout << nums[i] << " ";   // 1 2 3 4 5
    }
    cout << "\n";

    return 0;
}

🐛 The Off-By-One Error — The #1 Array Bug

Arrays are 0-indexed: if you declare int arr[5], valid indices are 0, 1, 2, 3, 4. There is NO arr[5]!

int arr[5] = {10, 20, 30, 40, 50};

// WRONG: loop goes from i=0 to i=5 inclusive — index 5 doesn't exist!
for (int i = 0; i <= 5; i++) {   // BUG: <= 5 should be < 5
    cout << arr[i];               // CRASH or garbage value when i=5
}

// CORRECT: loop from i=0 to i=4 (i < 5 ensures i never reaches 5)
for (int i = 0; i < 5; i++) {    // i goes: 0, 1, 2, 3, 4 ✓
    cout << arr[i];               // always valid
}

This is called an "off-by-one error" — going one element past the end. It's the single most common array bug in competitive programming.

🤔 Why start at 0? C++ inherited this from C, which was designed close to hardware. The index is actually an offset from the start of the array. The first element is at offset 0 (no offset from the beginning).

Global Arrays for Large Sizes

The local variables inside main live on the "stack," which has limited space (~1-8 MB). For competitive programming with N up to 10^6, you need global arrays (live in a different memory area, much larger):

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

const int MAXN = 1000001;  // max size + 1 (common convention)
int arr[MAXN];              // declared globally — safe for large sizes
// Global arrays are automatically initialized to 0!

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    return 0;
}

⚡ Pro Tip: Global arrays are initialized to 0 automatically. Local arrays are NOT — they contain garbage values until you assign them!

2.3.6 Common Array Algorithms

Find Sum, Max, Min

int n;
cin >> n;

vector<int> arr(n);    // we'll learn vectors soon; this works like an array
for (int i = 0; i < n; i++) cin >> arr[i];

// Sum
long long sum = 0;
for (int i = 0; i < n; i++) sum += arr[i];
cout << "Sum: " << sum << "\n";

// Max (initialize to first element!)
int maxVal = arr[0];
for (int i = 1; i < n; i++) {
    if (arr[i] > maxVal) maxVal = arr[i];
}
cout << "Max: " << maxVal << "\n";

// Min (same idea)
int minVal = arr[0];
for (int i = 1; i < n; i++) {
    minVal = min(minVal, arr[i]);  // min() is a built-in function
}
cout << "Min: " << minVal << "\n";

Complexity Analysis:

• Time: O(N) — each algorithm only needs one pass through the array
• Space: O(1) — only a few extra variables (not counting the input array itself)

Reverse an Array

int arr[] = {1, 2, 3, 4, 5};
int n = 5;

// Swap elements from both ends, moving toward the middle
for (int i = 0, j = n - 1; i < j; i++, j--) {
    swap(arr[i], arr[j]);  // swap() is a built-in function
}
// arr is now {5, 4, 3, 2, 1}

Complexity Analysis:

• Time: O(N) — each pair of elements is swapped once, N/2 swaps total
• Space: O(1) — in-place swap, no extra array needed

Two-Dimensional Arrays

A 2D array is like a table or grid. Perfect for maps, grids, matrices:

int grid[3][4];  // 3 rows, 4 columns

// Fill with i * 10 + j
for (int r = 0; r < 3; r++) {
    for (int c = 0; c < 4; c++) {
        grid[r][c] = r * 10 + c;
    }
}

// Print
for (int r = 0; r < 3; r++) {
    for (int c = 0; c < 4; c++) {
        cout << grid[r][c] << "\t";
    }
    cout << "\n";
}

Output:

0   1   2   3
10  11  12  13
20  21  22  23

2.3.7 Vectors — Dynamic Arrays

Arrays have a major limitation: their size must be known at compile time (or must be declared large enough in advance). Vectors solve this — they can grow and shrink as needed while your program is running.

Array vs Vector Comparison

Vector Basics

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

int main() {
    // Create an empty vector
    vector<int> v;

    // Add elements to the back with push_back
    v.push_back(10);    // v = [10]
    v.push_back(20);    // v = [10, 20]
    v.push_back(30);    // v = [10, 20, 30]

    // Access by index (same as arrays, 0-indexed)
    cout << v[0] << "\n";     // 10
    cout << v[1] << "\n";     // 20

    // Useful functions
    cout << v.size() << "\n"; // 3 (number of elements)
    cout << v.front() << "\n"; // 10 (first element)
    cout << v.back() << "\n";  // 30 (last element)
    cout << v.empty() << "\n"; // 0 (false — not empty)

    // Remove last element
    v.pop_back();   // v = [10, 20]

    // Clear all elements
    v.clear();      // v = []
    cout << v.empty() << "\n"; // 1 (true — now empty)

    return 0;
}

Creating Vectors With Initial Values

vector<int> zeros(10, 0);       // ten 0s: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
vector<int> ones(5, 1);         // five 1s: [1, 1, 1, 1, 1]
vector<int> primes = {2, 3, 5, 7, 11};  // initialized from list
vector<int> empty;              // empty vector

Iterating Over a Vector

vector<int> v = {10, 20, 30, 40, 50};

// Method 1: index-based (like arrays)
for (int i = 0; i < (int)v.size(); i++) {
    cout << v[i] << " ";
}
cout << "\n";

// Method 2: range-based for loop (cleaner, preferred)
for (int x : v) {
    cout << x << " ";
}
cout << "\n";

// Method 3: range-based with reference (use when modifying)
for (int& x : v) {
    x *= 2;  // doubles each element in-place
}

🤔 Why (int)v.size() in the index-based loop? v.size() returns an unsigned integer. If you compare int i with an unsigned value, C++ can behave unexpectedly (especially if i goes negative). Casting to (int) is the safe habit.

The Standard USACO Pattern with Vectors

int n;
cin >> n;

vector<int> arr(n);         // create vector of size n
for (int i = 0; i < n; i++) {
    cin >> arr[i];          // read into each position
}

// Now process arr...
sort(arr.begin(), arr.end());  // sort ascending

2D Vectors

int rows = 3, cols = 4;
vector<vector<int>> grid(rows, vector<int>(cols, 0));  // 3×4 grid of 0s

// Access: grid[r][c]
grid[1][2] = 42;
cout << grid[1][2] << "\n";  // 42

2.3.8 Passing Arrays and Vectors to Functions

Arrays

When you pass an array to a function, the function receives a pointer to the first element. Changes inside the function affect the original:

void fillSquares(int arr[], int n) {  // arr[] syntax for array parameter
    for (int i = 0; i < n; i++) {
        arr[i] = i * i;   // modifies the original!
    }
}

int main() {
    int arr[5] = {0};
    fillSquares(arr, 5);
    // arr is now {0, 1, 4, 9, 16}
    for (int i = 0; i < 5; i++) cout << arr[i] << " ";
    cout << "\n";
    return 0;
}

Vectors

Vectors by default are copied when passed to functions (expensive for large vectors!). Use & to pass by reference:

// Pass by value — makes a copy (SLOW for large vectors)
void printVec(vector<int> v) {
    for (int x : v) cout << x << " ";
}

// Pass by reference — no copy, CAN modify original (use for output params)
void sortVec(vector<int>& v) {
    sort(v.begin(), v.end());
}

// Pass by const reference — no copy, CANNOT modify (best for read-only)
void printVecFast(const vector<int>& v) {
    for (int x : v) cout << x << " ";
}

⚡ Pro Tip: For any vector parameter that you're only reading (not modifying), always write const vector<int>&. It avoids the copy and also signals to readers that the function won't change the vector.

⚠️ Common Mistakes in Chapter 2.3

Chapter Summary

📌 Key Takeaways

❓ FAQ

Q1: Which is better, arrays or vectors?

A: Both are common in competitive programming. Rule of thumb: if the size is fixed and known, global arrays are simplest; if the size changes dynamically or needs to be passed to functions, use vector. Many contestants default to vector because it is more flexible and less error-prone.

Q2: Is there a limit to recursion depth? Can it crash?

A: Yes. Each function call allocates space on the stack, and the default stack size is about 1-8 MB. In practice, about 10^4 ~ 10^5 levels of recursion are supported. If exceeded, the program crashes with a "stack overflow". In contests, if recursion depth may exceed 10^4, consider switching to an iterative (loop) approach.

Q3: When should I use pass by reference (&)?

A: Two cases: ① You need to modify the original variable inside the function; ② The parameter is a large object (like vector or string) and you want to avoid copy overhead. For small types like int and double, copy overhead is negligible, so pass by value is fine.

Q4: Can a function return an array or vector?

A: Arrays cannot be returned directly, but vector can! vector<int> solve() { ... return result; } is perfectly valid. Modern C++ compilers optimize the return process (called RVO), so the entire vector is not actually copied.

Q5: Why does the prefix sum array have one extra index? prefix[n+1] instead of prefix[n]?

A: prefix[0] = 0 is a "sentinel value" that makes the formula prefix[R+1] - prefix[L] work in all cases. Without this sentinel, querying [0, R] would require special handling when L=0. This is a very common programming trick: use an extra sentinel value to simplify boundary handling.

🔗 Connections to Later Chapters

• Chapter 3.1 (STL Essentials) will introduce tools like sort, binary_search, and pair, letting you accomplish in one line what this chapter implements by hand
• Chapter 3.2 (Prefix Sums) will dive deeper into the prefix sum technique introduced in Problem 3.10, including 2D prefix sums and difference arrays
• Chapter 5.1 (Introduction to Graphs) will build on the recursion foundation in Section 2.3.4 to teach graph traversals like DFS and BFS
• Chapters 6.1–6.3 (Dynamic Programming): the core idea of "breaking large problems into smaller ones" is closely related to recursion; this chapter's recursive thinking is important groundwork
• The function encapsulation and array/vector operations learned in this chapter will be used continuously in every subsequent chapter

Practice Problems

🌡️ Warm-Up Problems

Warm-up 2.3.1 — Square Function Write a function int square(int x) that returns x². In main, read one integer and print its square.

Sample Input: 7 → Sample Output: 49

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

int square(int x) {
    return x * x;
}

int main() {
    int n;
    cin >> n;
    cout << square(n) << "\n";
    return 0;
}

Warm-up 2.3.2 — Max of Two Write a function int myMax(int a, int b) that returns the larger of two integers. In main, read two integers and print the larger.

Sample Input: 13 7 → Sample Output: 13

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

int myMax(int a, int b) {
    if (a > b) return a;
    return b;
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << myMax(a, b) << "\n";
    return 0;
}

Warm-up 2.3.3 — Reverse Array Declare an array of exactly 5 integers: {1, 2, 3, 4, 5}. Print them in reverse order (no input needed).

Expected Output:

5 4 3 2 1

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

int main() {
    int arr[5] = {1, 2, 3, 4, 5};

    for (int i = 4; i >= 0; i--) {
        cout << arr[i];
        if (i > 0) cout << " ";
    }
    cout << "\n";

    return 0;
}

Warm-up 2.3.4 — Vector Sum Create a vector, push the values 10, 20, 30, 40, 50 into it using push_back, then print their sum.

Expected Output: 150

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

int main() {
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);

    long long sum = 0;
    for (int x : v) {
        sum += x;
    }

    cout << sum << "\n";
    return 0;
}

Warm-up 2.3.5 — Hello N Times Write a void function sayHello(int n) that prints "Hello!" exactly n times. Call it from main after reading n.

Sample Input: 3 Sample Output:

Hello!
Hello!
Hello!

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

void sayHello(int n) {
    for (int i = 0; i < n; i++) {
        cout << "Hello!\n";
    }
}

int main() {
    int n;
    cin >> n;
    sayHello(n);
    return 0;
}

🏋️ Core Practice Problems

Problem 2.3.6 — Array Reverse Read N (1 ≤ N ≤ 100), then read N integers. Print them in reverse order.

5
1 2 3 4 5

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

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

    int n;
    cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    for (int i = n - 1; i >= 0; i--) {
        cout << arr[i];
        if (i > 0) cout << " ";
    }
    cout << "\n";

    return 0;
}

4
10 20 30 40

10.00
15.00
20.00
25.00

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

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

    int n;
    cin >> n;

    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sum += x;
        double avg = (double)sum / i;
        cout << fixed << setprecision(2) << avg << "\n";
    }

    return 0;
}

Problem 2.3.8 — Frequency Count Read N (1 ≤ N ≤ 100) integers. Each integer is between 1 and 10 inclusive. Print how many times each value from 1 to 10 appears.

Sample Input:

7
3 1 2 3 3 1 7

Sample Output:

1 appears 2 times
2 appears 1 times
3 appears 3 times
4 appears 0 times
5 appears 0 times
6 appears 0 times
7 appears 1 times
8 appears 0 times
9 appears 0 times
10 appears 0 times

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

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

    int n;
    cin >> n;

    int freq[11] = {};  // indices 0-10; we'll use 1-10. Initialize all to 0.

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        freq[x]++;    // increment the count for value x
    }

    for (int v = 1; v <= 10; v++) {
        cout << v << " appears " << freq[v] << " times\n";
    }

    return 0;
}

Problem 2.3.9 — Two Sum Read N (1 ≤ N ≤ 100) integers and a target value T. Print YES if any two different elements in the array sum to T, NO otherwise.

5 9
1 4 5 6 3

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

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

    int n, t;
    cin >> n >> t;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    bool found = false;
    for (int i = 0; i < n && !found; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] + arr[j] == t) {
                found = true;
                break;
            }
        }
    }

    cout << (found ? "YES" : "NO") << "\n";

    return 0;
}

5
1 2 3 4 5
3
0 2
1 3
2 4

6
9
12

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

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

    int n;
    cin >> n;

    vector<long long> arr(n), prefix(n + 1, 0);

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        prefix[i + 1] = prefix[i] + arr[i];  // build prefix sum
    }
    // prefix[0] = 0
    // prefix[1] = arr[0]
    // prefix[2] = arr[0] + arr[1]
    // prefix[i] = arr[0] + arr[1] + ... + arr[i-1]

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        // sum from l to r (inclusive) = prefix[r+1] - prefix[l]
        cout << prefix[r + 1] - prefix[l] << "\n";
    }

    return 0;
}

🏆 Challenge Problems

Challenge 2.3.11 — Rotate Array Read N (1 ≤ N ≤ 1000) and K (0 ≤ K < N). Read N integers. Print the array rotated right by K positions (the last K elements wrap to the front).

Sample Input:

5 2
1 2 3 4 5

Sample Output: 4 5 1 2 3

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

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

    int n, k;
    cin >> n >> k;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    // Print n elements starting from index (n - k) % n, wrapping around
    for (int i = 0; i < n; i++) {
        int idx = (n - k + i) % n;
        cout << arr[idx];
        if (i < n - 1) cout << " ";
    }
    cout << "\n";

    return 0;
}

Challenge 2.3.12 — Merge Sorted Arrays Read N₁, then N₁ sorted integers. Read N₂, then N₂ sorted integers. Print the merged sorted array.

Sample Input:

3
1 3 5
4
2 4 6 8

Sample Output: 1 2 3 4 5 6 8

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

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

    int n1;
    cin >> n1;
    vector<int> a(n1);
    for (int i = 0; i < n1; i++) cin >> a[i];

    int n2;
    cin >> n2;
    vector<int> b(n2);
    for (int i = 0; i < n2; i++) cin >> b[i];

    // Two-pointer merge
    int i = 0, j = 0;
    vector<int> result;

    while (i < n1 && j < n2) {
        if (a[i] <= b[j]) {
            result.push_back(a[i++]);  // take from a, advance i
        } else {
            result.push_back(b[j++]);  // take from b, advance j
        }
    }
    // One array may have leftover elements
    while (i < n1) result.push_back(a[i++]);
    while (j < n2) result.push_back(b[j++]);

    for (int idx = 0; idx < (int)result.size(); idx++) {
        cout << result[idx];
        if (idx < (int)result.size() - 1) cout << " ";
    }
    cout << "\n";

    return 0;
}

Challenge 2.3.13 — Smell Distance (Inspired by USACO Bronze)

N cows are standing in a line. Each cow has a position p[i] and a smell radius s[i]. A cow can smell another if the distance between them is at most the sum of their radii. Read N, then N pairs (position, radius). Print the number of pairs of cows that can smell each other.

Sample Input:

4
1 2
5 1
8 3
15 1

Sample Output: 1

(Pair (0,1): dist=|1-5|=4, radii sum=2+1=3. 4>3, NO. Pair (0,2): dist=|1-8|=7, sum=2+3=5. 7>5, NO. Pair (1,2): dist=|5-8|=3, sum=1+3=4. 3≤4, YES. Pair (0,3): 14>3 NO. Pair (1,3): 10>2 NO. Pair (2,3): 7>4 NO. Total: 1.)

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

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

    int n;
    cin >> n;

    vector<long long> pos(n), rad(n);
    for (int i = 0; i < n; i++) {
        cin >> pos[i] >> rad[i];
    }

    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            long long dist = abs(pos[i] - pos[j]);
            long long sumRad = rad[i] + rad[j];
            if (dist <= sumRad) {
                count++;
            }
        }
    }

    cout << count << "\n";
    return 0;
}

Chapter 2.4: Structs & Classes

📝 Prerequisites: Chapters 2.1–2.3 (variables, control flow, functions, arrays)

In competitive programming, you often need to group related data together — for example, a point has an x and y, an edge has two endpoints and a weight, a student has a name and a score. C++ provides struct and class to bundle data (and behavior) into a single type. This chapter covers both, with a strong focus on what matters most in competitive programming.

2.4.1 Why Group Data Together?

🎒 The Backpack Analogy

Imagine you're going on a trip. You could carry each item separately:
  - left hand: passport
  - right hand: phone
  - pocket: wallet
  - teeth: ticket 😬

Or you could put everything in a BACKPACK:
  - backpack.passport ✅
  - backpack.phone ✅
  - backpack.wallet ✅
  - backpack.ticket ✅

A struct/class is that backpack — it groups related items under one name.

Without structs, if you want to store 1000 students' names and scores, you'd need two separate arrays:

string names[1000];
int scores[1000];
// You have to manually keep indices in sync — error-prone!

With a struct, it's clean and safe:

struct Student {
    string name;
    int score;
};
Student students[1000];  // Each student carries its own name and score

2.4.2 Struct Basics

Defining a Struct

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

struct Point {
    int x;
    int y;
};  // <-- Don't forget the semicolon!

int main() {
    Point p;       // Declare a Point variable
    p.x = 3;       // Access members with the dot (.) operator
    p.y = 7;
    cout << "(" << p.x << ", " << p.y << ")" << endl;  // (3, 7)
    return 0;
}

Initialization Methods

// Method 1: Aggregate initialization (C++11, most common in CP)
Point p1 = {3, 7};

// Method 2: Designated initializers (C++20)
Point p2 = {.x = 3, .y = 7};

// Method 3: Assign fields one by one
Point p3;
p3.x = 3;
p3.y = 7;

💡 CP Tip: In competitive programming, aggregate initialization {val1, val2, ...} is the most commonly used style — fast to type, easy to read.

Struct with a Constructor

You can define a constructor so that creating an instance is even cleaner:

struct Point {
    int x, y;

    // Constructor
    Point(int _x, int _y) : x(_x), y(_y) {}
};

int main() {
    Point p(3, 7);  // Calls the constructor
    cout << p.x << " " << p.y << endl;  // 3 7
}

⚠️ Warning: Once you define a custom constructor, you can no longer use Point p; (no arguments) unless you also provide a default constructor or add default parameter values.

struct Point {
    int x, y;

    Point() : x(0), y(0) {}            // Default constructor
    Point(int _x, int _y) : x(_x), y(_y) {}  // Parameterized constructor
};

Point p1;       // OK — uses default constructor, x=0, y=0
Point p2(3, 7); // OK — uses parameterized constructor

2.4.3 Structs in Competitive Programming

Storing Edges in Graph Problems

struct Edge {
    int from, to, weight;
};

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

    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].from >> edges[i].to >> edges[i].weight;
    }
}

Sorting Structs with Custom Comparison

This is extremely common in USACO problems. You often need to sort objects by a specific field.

Method 1: Overload operator< inside the struct

struct Event {
    int start, end;

    // Sort by end time (greedy scheduling)
    bool operator<(const Event& other) const {
        return end < other.end;
    }
};

int main() {
    vector<Event> events = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8}, {5, 9}};
    sort(events.begin(), events.end());  // Uses operator< automatically

    for (auto& e : events) {
        cout << "[" << e.start << ", " << e.end << "] ";
    }
    // Output: [1, 4] [3, 5] [0, 6] [5, 7] [3, 8] [5, 9]
}

Method 2: Lambda comparator (more flexible)

struct Event {
    int start, end;
};

int main() {
    vector<Event> events = {{1, 4}, {3, 5}, {0, 6}, {5, 7}};

    // Sort by start time
    sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
        return a.start < b.start;
    });
}

Method 3: Write a comparison function

bool compareByEnd(const Event& a, const Event& b) {
    return a.end < b.end;
}

sort(events.begin(), events.end(), compareByEnd);

💡 CP Tip: For most USACO problems, Method 1 (operator overloading) is the cleanest when you have one natural sort order. Use Method 2 (lambda) when you need multiple different sort orders in the same program.

Multi-Key Sorting

Sometimes you need to sort by one field first, then break ties with another:

struct Student {
    string name;
    int score;

    bool operator<(const Student& other) const {
        if (score != other.score) return score > other.score;  // Higher score first
        return name < other.name;  // Alphabetical for ties
    }
};

Or use tie() for a cleaner approach:

struct Student {
    string name;
    int score;

    bool operator<(const Student& other) const {
        // Sort by score descending, then name ascending
        return tie(other.score, name) < tie(score, other.name);
    }
};

💡 tie() Trick: tie() creates a tuple for lexicographic comparison. Swapping the order of elements reverses the sort direction for that field. This is a very common competitive programming technique.

Structs in Sets and Maps

If you want to use a struct as a key in set or map, you must define operator<:

struct Point {
    int x, y;
    bool operator<(const Point& other) const {
        return tie(x, y) < tie(other.x, other.y);
    }
};

set<Point> visited;
visited.insert({1, 2});
visited.insert({3, 4});

if (visited.count({1, 2})) {
    cout << "Already visited!" << endl;
}

Structs in Priority Queues

struct State {
    int dist, node;

    // For min-heap: we want the SMALLEST dist on top
    // priority_queue is a MAX-heap by default, so we reverse the comparison
    bool operator>(const State& other) const {
        return dist > other.dist;
    }
};

// Min-heap using operator>
priority_queue<State, vector<State>, greater<State>> pq;
pq.push({0, 1});   // distance 0, node 1
pq.push({5, 2});   // distance 5, node 2

auto top = pq.top();  // {0, 1} — smallest distance

2.4.4 Struct vs. Class — What's the Difference?

Here's the truth: struct and class are almost identical in C++. The only difference is the default access level:

// These two are functionally identical:

struct PointS {
    int x, y;  // public by default
};

class PointC {
public:          // Must explicitly say "public"
    int x, y;
};

When to Use Which?

💡 CP Convention: In competitive programming, always use struct. It's simpler, shorter, and you almost never need private members. You'll see struct in virtually every competitive programmer's code.

2.4.5 Classes — The Full Picture

While struct is sufficient for competitive programming, understanding class is valuable for broader C++ knowledge.

Access Modifiers

class BankAccount {
private:    // Only accessible inside the class
    double balance;

public:     // Accessible from anywhere
    BankAccount(double initial) : balance(initial) {}

    void deposit(double amount) {
        if (amount > 0) {
            balance += amount;
        }
    }

    void withdraw(double amount) {
        if (amount > 0 && amount <= balance) {
            balance -= amount;
        }
    }

    double getBalance() const {
        return balance;
    }
};

int main() {
    BankAccount acc(100.0);
    acc.deposit(50.0);
    acc.withdraw(30.0);
    cout << acc.getBalance() << endl;  // 120.0

    // acc.balance = 999999;  // ERROR! balance is private
}

Why Encapsulation?

Think of a vending machine:

- PUBLIC interface:  insert coin, press button, take drink
- PRIVATE internals: coin counter, inventory, temperature control

You interact with the machine through its public buttons.
You can't directly reach in and grab a drink.

Encapsulation protects data from being misused.

In competitive programming, this level of protection is unnecessary — speed of writing code matters more. But in software engineering, it prevents bugs in large codebases.

Member Functions (Methods)

Both struct and class can have member functions:

struct Rect {
    int width, height;

    int area() const {
        return width * height;
    }

    int perimeter() const {
        return 2 * (width + height);
    }

    bool contains(int x, int y) const {
        return x >= 0 && x < width && y >= 0 && y < height;
    }
};

int main() {
    Rect r = {10, 5};
    cout << "Area: " << r.area() << endl;        // 50
    cout << "Perimeter: " << r.perimeter() << endl;  // 30
    cout << r.contains(3, 4) << endl;              // 1 (true)
}

💡 const After Method Name: The const keyword after a method name means "this method does not modify the object." Always mark methods as const if they only read data — this is good practice and required when working with const references.

2.4.6 Advanced Struct Patterns for CP

Pair — The Built-in "Two-Field Struct"

C++ provides pair as a lightweight alternative when you only need two fields:

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

int main() {
    pair<int, int> p = {3, 7};
    cout << p.first << " " << p.second << endl;  // 3 7

    // Pairs have built-in comparison (lexicographic)
    vector<pair<int, int>> v = {{3, 1}, {1, 5}, {3, 0}, {1, 2}};
    sort(v.begin(), v.end());
    // Result: {1, 2}, {1, 5}, {3, 0}, {3, 1}

    // You can use make_pair or just braces
    auto q = make_pair(10, 20);
}

When to use pair vs struct:

Tuple — The Built-in "N-Field Struct"

tuple<int, string, double> t = {42, "Alice", 3.14};
cout << get<0>(t) << endl;  // 42
cout << get<1>(t) << endl;  // Alice

// Structured bindings (C++17) — much cleaner
auto [id, name, gpa] = t;
cout << name << " has GPA " << gpa << endl;

💡 CP Tip: For anything more than 2 fields, a named struct is almost always more readable than tuple. Use pair freely, but avoid tuple when you can use a struct instead.

Struct with array or vector Members

struct Graph {
    int n;
    vector<vector<int>> adj;

    Graph(int _n) : n(_n), adj(_n) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(1, 2);

    for (int v : g.adj[1]) {
        cout << v << " ";  // 0 2
    }
}

2.4.7 Common Mistakes

❌ Mistake 1: Forgetting the Semicolon After }

struct Point {
    int x, y;
}   // ← Missing semicolon!

int main() { ... }
// Compiler gives a confusing error pointing at main()

Fix: Always put ; after the closing brace of a struct/class definition.

❌ Mistake 2: Forgetting const in Operator Overloads

struct Point {
    int x, y;
    // WRONG — missing const
    bool operator<(const Point& other) {  // ← won't work in some STL containers
        return tie(x, y) < tie(other.x, other.y);
    }
};

Fix: Always mark comparison operators as const:

bool operator<(const Point& other) const {  // ✅
    return tie(x, y) < tie(other.x, other.y);
}

❌ Mistake 3: Using Uninitialized Struct Members

struct State {
    int dist, node;
};

State s;
cout << s.dist;  // Undefined behavior! Could be any value

Fix: Always initialize, or provide default values:

struct State {
    int dist = 0;
    int node = 0;
};

❌ Mistake 4: Confusing operator< Direction for Priority Queues

struct State {
    int dist;
    // For min-heap, you might think:
    bool operator<(const State& other) const {
        return dist < other.dist;  // This gives MAX-heap! (opposite of what you want)
    }
};

Fix: For min-heap with priority_queue, either reverse the comparison or use greater<>:

// Option A: Reverse operator<
bool operator<(const State& other) const {
    return dist > other.dist;  // Larger dist has LOWER priority → min-heap
}
priority_queue<State> pq;

// Option B: Define operator> and use greater<>
bool operator>(const State& other) const {
    return dist > other.dist;
}
priority_queue<State, vector<State>, greater<State>> pq;

2.4.8 Practice Problems

🟢 Problem 1: Student Ranking

Read n students (name and score), sort them by score descending, and print the ranking.

Input:
3
Alice 85
Bob 92
Charlie 85

Output:
1. Bob 92
2. Alice 85
3. Charlie 85

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

struct Student {
    string name;
    int score;

    bool operator<(const Student& other) const {
        if (score != other.score) return score > other.score;
        return name < other.name;
    }
};

int main() {
    int n;
    cin >> n;
    vector<Student> students(n);
    for (int i = 0; i < n; i++) {
        cin >> students[i].name >> students[i].score;
    }
    sort(students.begin(), students.end());
    for (int i = 0; i < n; i++) {
        cout << i + 1 << ". " << students[i].name << " " << students[i].score << "\n";
    }
}

🟢 Problem 2: Closest Pair of Points (1D)

Given n points on a number line, find the pair with the smallest distance between them.

Input:
5
7 1 4 9 2

Output:
1
(between points 1 and 2)

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

struct PointVal {
    int val, originalIndex;

    bool operator<(const PointVal& other) const {
        return val < other.val;
    }
};

int main() {
    int n;
    cin >> n;
    vector<PointVal> points(n);
    for (int i = 0; i < n; i++) {
        cin >> points[i].val;
        points[i].originalIndex = i;
    }
    sort(points.begin(), points.end());

    int minDist = INT_MAX;
    int bestI = 0, bestJ = 1;
    for (int i = 0; i + 1 < n; i++) {
        int d = points[i + 1].val - points[i].val;
        if (d < minDist) {
            minDist = d;
            bestI = i;
            bestJ = i + 1;
        }
    }
    cout << minDist << "\n";
    cout << "(between points " << points[bestI].val << " and " << points[bestJ].val << ")\n";
}

🟡 Problem 3: Interval Scheduling (Greedy)

Given n intervals [start, end], find the maximum number of non-overlapping intervals.

Input:
6
1 4
3 5
0 6
5 7
3 8
5 9

Output:
3
(select [1,4], [5,7], [5,9] — wait, [5,7] and [5,9] overlap!)
Correct: select [1,4], [5,7] → 2 non-overlapping, or [1,4], [5,7] → Actually:
3

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

struct Interval {
    int start, end;

    bool operator<(const Interval& other) const {
        return end < other.end;
    }
};

int main() {
    int n;
    cin >> n;
    vector<Interval> intervals(n);
    for (int i = 0; i < n; i++) {
        cin >> intervals[i].start >> intervals[i].end;
    }
    sort(intervals.begin(), intervals.end());

    int count = 0, lastEnd = -1;
    for (auto& it : intervals) {
        if (it.start >= lastEnd) {
            count++;
            lastEnd = it.end;
        }
    }
    cout << count << "\n";
}

📋 Chapter Summary

🎯 Key CP Takeaways

1. Always use struct in competitive programming — simpler and shorter
2. Master operator< overloading — you'll use it in nearly every USACO problem
3. Use tie() for multi-key sorts — clean and bug-free
4. Remember const on comparison operators — required for STL compatibility
5. Initialize your members — avoid undefined behavior
6. pair for 2 fields, custom struct for 3+ — good rule of thumb

Part 3: Core Data Structures

Estimated time: 2–3 weeks

Part 3 is where competitive programming starts getting exciting. You'll learn the data structures that appear in nearly every USACO Bronze and Silver problem — and techniques that can turn O(N²) brute force into O(N) elegance.

What Topics Are Covered

What You'll Be Able to Solve After This Part

After completing Part 3, you'll be ready to tackle:

• USACO Bronze: Most Bronze problems use Part 3 techniques

  • Range queries (how many cows of type X in positions L to R?)
  • Sorting problems (closest pair, ranking, scheduling)
  • Frequency counting (how many times does each value appear?)
  • Stack-based problems (balanced brackets, monotonic processing)

• USACO Silver Intro:

  • Binary search on the answer (aggressive cows, rope cutting)
  • Sliding window maximum/minimum
  • Difference arrays for range updates

Key Algorithms Introduced

Prerequisites

Before starting Part 3, make sure you can:

• Write and compile a C++ program from scratch (Chapter 2.1)
• Use for loops and nested loops correctly (Chapter 2.2)
• Work with arrays and vector<int> (Chapter 2.3)

Note: Chapter 3.1 (STL Essentials) is the first chapter of this part and will teach you std::sort, map, set, and other key STL containers before you need them in later chapters.

Tips for This Part

1. Chapter 3.2 (Prefix Sums) is the most frequently tested technique in Bronze. Make sure you can implement it from scratch in 5 minutes.
2. Chapter 3.3 (Binary Search) introduces "binary search on the answer" — this is a Silver-level technique that separates good solutions from great ones.
3. Don't skip the practice problems. Each chapter's problems are specifically chosen to build the intuition you need.
4. After finishing Chapter 3.3, you have enough tools for most USACO Bronze problems. Try solving 5–10 Bronze problems before continuing.

🏆 USACO Tip: At USACO Bronze, the most common techniques are: simulation (Chapters 2.1–2.3), sorting (Chapter 3.3), and prefix sums (Chapter 3.2). If you master these, you can solve almost any Bronze problem.

Let's dive in!

Chapter 3.1: STL Essentials

📝 Prerequisites: Chapters 2.1–2.3 (variables, loops, functions, vectors)

The Standard Template Library (STL) is C++'s built-in collection of ready-made data structures and algorithms. Instead of writing your own linked lists, hash tables, or sorting algorithms from scratch, you use the STL — it's fast, reliable, and tested by millions of programmers.

Learning to pick the right STL container for a problem is one of the most important skills in competitive programming.

What you'll learn in this chapter:

• sort — sort any sequence in one line, with custom rules
• pair — bundle two values together cleanly
• map / set — ordered key-value store and unique-element collection
• stack / queue — LIFO and FIFO containers for classic algorithms
• priority_queue — always get the max (or min) in O(log N)
• unordered_map / unordered_set — hash-based O(1) lookup
• auto and range-based for — write cleaner, shorter code
• Useful STL algorithms: binary_search, lower_bound, accumulate, and more

3.1.0 The STL Toolbox

Think of the STL as a toolbox. Each tool is designed for a specific job:

Quick reference — which container to reach for:

Picking the right tool = half the solution in competitive programming!

"Which Container Should I Use?" Decision Tree

Visual: STL Containers Overview

3.1.1 sort — The Only Sort You Need

We start with sort because you'll use it in almost every problem.

What it is and why it matters

Sorting rearranges a sequence of elements into order. Rather than implementing your own sorting algorithm (which is error-prone and takes time), C++'s sort is:

• Fast: O(N log N) — the theoretical best for comparison-based sorting
• Easy to use: one line of code
• Flexible: sorts by any rule you define

⚠️ Important: sort requires #include <algorithm> (included automatically via #include <bits/stdc++.h>).

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

int main() {
    // Sorting a vector — ascending (default)
    vector<int> v = {5, 2, 8, 1, 9, 3};
    sort(v.begin(), v.end());
    // v is now: {1, 2, 3, 5, 8, 9}

    for (int x : v) cout << x << " ";
    cout << "\n";

    // Sorting descending
    sort(v.begin(), v.end(), greater<int>());
    // v is now: {9, 8, 5, 3, 2, 1}

    // Sorting an array
    int arr[] = {4, 2, 7, 1, 5};
    int n = 5;
    sort(arr, arr + n);  // sorts arr[0..n-1]
    // arr is now: {1, 2, 4, 5, 7}

    return 0;
}

Custom Sort (Lambda Functions)

What if you want to sort by something other than the natural order? Use a lambda — a small inline function:

vector<int> v = {5, -3, 2, -8, 1};

// Sort by absolute value
sort(v.begin(), v.end(), [](int a, int b) {
    return abs(a) < abs(b);  // return true if a should come BEFORE b
});
// v is now: {1, 2, -3, 5, -8}  (ordered by |value|)

The lambda [](int a, int b) { return ...; } is the comparison rule. It must return true if a should come before b in the sorted result.

🐛 Common mistake: Never return true when a == b — this violates the "strict weak ordering" rule and causes undefined behavior (crash or wrong answer). Always use < or >, never <= or >=.

// Sort a vector of pairs: by second element (descending), then first element (ascending)
vector<pair<int,int>> pts = {{3,5},{1,7},{2,5},{4,3}};
sort(pts.begin(), pts.end(), [](pair<int,int> a, pair<int,int> b) {
    if (a.second != b.second) return a.second > b.second;  // bigger second first
    return a.first < b.first;   // tie-break: smaller first first
});
// Result: {1,7}, {2,5}, {3,5}, {4,3}

3.1.2 pair — Storing Two Values Together

A pair bundles two values into one object. Think of it as a "mini-struct" for two values.

Why use pair? Often you need to keep two related values together — like (value, index), (x-coordinate, y-coordinate), or (score, name). pair does this cleanly.

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

int main() {
    // Create a pair
    pair<int, int> point = {3, 5};         // (x, y)
    pair<string, int> student = {"Alice", 95};  // (name, score)

    // Access elements: .first and .second
    cout << point.first << " " << point.second << "\n";    // 3 5
    cout << student.first << ": " << student.second << "\n"; // Alice: 95

    // Pairs support comparison: compares .first first, then .second
    pair<int,int> a = {1, 3};
    pair<int,int> b = {1, 5};
    cout << (a < b) << "\n";   // 1 (true) — same .first, so compare .second: 3 < 5

    // Very common pattern: sort by second element using pairs
    vector<pair<int,int>> v = {{3,9},{1,2},{4,1},{1,5}};
    sort(v.begin(), v.end());     // sorts by .first first, then .second
    // Result: {1,2}, {1,5}, {3,9}, {4,1}

    return 0;
}

⚡ Pro Tip: When you need to sort items by one value but keep track of their original index, store them as pair<value, index> and sort. After sorting, .second gives you the original index.

💡 make_pair vs brace initialization: Both make_pair(3, 5) and {3, 5} create a pair. The brace syntax {3, 5} is shorter and preferred in modern C++ (C++11 and later).

3.1.3 map — The Dictionary

A map stores key-value pairs, like a real dictionary: given a word (key), look up its definition (value). Each key appears at most once.

When to use map

• Counting frequencies: word → count, score → frequency
• Mapping IDs to names: student_id → name
• Storing properties: cow_name → milk_production

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

int main() {
    map<string, int> phoneBook;

    // Insert key-value pairs
    phoneBook["Alice"] = 555001;
    phoneBook["Bob"] = 555002;
    phoneBook["Charlie"] = 555003;

    // Lookup by key
    cout << phoneBook["Alice"] << "\n";  // 555001

    // Iterate (always in SORTED KEY order!)
    for (auto& entry : phoneBook) {
        cout << entry.first << " -> " << entry.second << "\n";
    }
    // Prints:
    // Alice -> 555001
    // Bob -> 555002
    // Charlie -> 555003

    // Erase a key
    phoneBook.erase("Charlie");
    cout << phoneBook.size() << "\n";  // 2

    return 0;
}

Common Operations with Time Complexity

🐛 The map Access Gotcha

This is one of the most common map bugs:

map<string, int> freq;

// DANGER: accessing a non-existent key CREATES IT with value 0!
cout << freq["apple"] << "\n";  // prints 0, but now "apple" is IN the map!
cout << freq.size() << "\n";    // 1 — even though we only "looked", not "inserted"!

// SAFE way 1: check count first
if (freq.count("apple") > 0) {
    cout << freq["apple"] << "\n";  // safe — key exists
}

// SAFE way 2: use .find()
auto it = freq.find("apple");
if (it != freq.end()) {          // .end() means "not found"
    cout << it->second << "\n";  // it->second is the value
}

Frequency Counting — The Most Common map Pattern

vector<string> words = {"apple", "banana", "apple", "cherry", "banana", "apple"};
map<string, int> freq;

for (const string& w : words) {
    freq[w]++;  // if "w" doesn't exist, it's created with 0, then incremented to 1
}

// freq: apple→3, banana→2, cherry→1
for (auto& p : freq) {
    cout << p.first << " appears " << p.second << " times\n";
}

💡 Why freq[w]++ works even for new keys: map default-initializes missing values. For int, the default is 0. So accessing a new key creates it with value 0, and ++ makes it 1. This is intentional and widely used for counting.

3.1.4 set — Unique Sorted Collection

A set stores unique elements in sorted order. Insert a duplicate — it's silently ignored.

When to use set

• Removing duplicates from a list
• Checking membership quickly: "have I seen this value before?"
• Getting the minimum/maximum of a dynamic collection

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

int main() {
    set<int> s;

    s.insert(5);
    s.insert(2);
    s.insert(8);
    s.insert(2);   // duplicate — ignored! set stays {2, 5, 8}
    s.insert(1);

    // s is now: {1, 2, 5, 8}  (automatically sorted, no duplicates)

    // Check membership
    cout << s.count(2) << "\n";   // 1 (exists)
    cout << s.count(7) << "\n";   // 0 (not there)

    // Erase
    s.erase(2);   // s = {1, 5, 8}

    // Iterate (always sorted)
    for (int x : s) cout << x << " ";
    cout << "\n";   // 1 5 8

    // Min and max
    cout << *s.begin() << "\n";   // 1 (smallest; * dereferences the iterator)
    cout << *s.rbegin() << "\n";  // 8 (largest; r = reverse)

    cout << s.size() << "\n";  // 3

    return 0;
}

Common Operations with Time Complexity

Deduplication with set

vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
set<int> unique_set(v.begin(), v.end());  // construct set from vector
// unique_set = {1, 2, 3, 4, 5, 6, 9}

cout << "Unique count: " << unique_set.size() << "\n";   // 7

// Convert back to sorted vector if needed:
vector<int> deduped(unique_set.begin(), unique_set.end());

💡 set vs multiset: set stores each value at most once. If you need to store duplicates but still want sorted order, use multiset<int> — it allows repeated elements.

3.1.5 stack — Last In, First Out

A stack works like a pile of plates: you can only add to the top or remove from the top. The last item added is the first one removed (LIFO: Last In, First Out).

When to use stack

• Matching brackets/parentheses
• Undo/redo history
• Depth-first search (DFS) — covered in later chapters
• Reversing a sequence

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

int main() {
    stack<int> st;

    st.push(1);    // [1]         (top is on the right)
    st.push(2);    // [1, 2]
    st.push(3);    // [1, 2, 3]

    cout << st.top() << "\n";   // 3 (peek at top without removing)
    st.pop();                    // remove top → [1, 2]
    cout << st.top() << "\n";   // 2

    cout << st.size() << "\n";  // 2
    cout << st.empty() << "\n"; // 0 (not empty)

    return 0;
}

Common Operations with Time Complexity

🐛 Common Stack Mistake: Pop Without Checking

stack<int> st;
// st.top();  // CRASH! Can't peek at top of empty stack
// st.pop();  // CRASH! Can't pop from empty stack

// Always check before accessing:
if (!st.empty()) {
    cout << st.top() << "\n";
    st.pop();
}

Classic Stack Problem: Balanced Parentheses

string expr = "((a+b)*(c-d))";
stack<char> parens;
bool balanced = true;

for (char ch : expr) {
    if (ch == '(') {
        parens.push(ch);         // opening: push onto stack
    } else if (ch == ')') {
        if (parens.empty()) {    // closing with no matching opening
            balanced = false;
            break;
        }
        parens.pop();            // match found: pop the opening
    }
}

if (!parens.empty()) balanced = false;  // unmatched opening parens remain

cout << (balanced ? "Balanced" : "Not balanced") << "\n";

3.1.6 queue — First In, First Out

A queue works like a line at a store: you join at the back and leave from the front. The first person who joined is the first to be served (FIFO: First In, First Out).

When to use queue

• Simulating a line of customers, processes, tasks
• Breadth-first search (BFS) — one of the most important algorithms in competitive programming (Chapter 5.2)
• Processing items in the order they arrived

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

int main() {
    queue<int> q;

    q.push(10);   // [10]
    q.push(20);   // [10, 20]
    q.push(30);   // [10, 20, 30]

    cout << q.front() << "\n";  // 10 (first in line — will leave first)
    cout << q.back() << "\n";   // 30 (last in line — will leave last)

    q.pop();                     // remove from front → [20, 30]
    cout << q.front() << "\n";  // 20

    cout << q.size() << "\n";   // 2

    return 0;
}

Common Operations with Time Complexity

Note: You'll use queue extensively in Chapter 5.2 for BFS — one of the most important graph algorithms for USACO.

🐛 Common mistake: queue has no top() method (that's stack). Use front() to peek at the front element and back() to peek at the rear.

3.1.7 priority_queue — The Heap

A priority_queue is like a magic queue: no matter what order you insert things, it always gives you the largest element first (max-heap by default).

When to use priority_queue

• Always need the largest (or smallest) element quickly
• Finding the K largest numbers
• Dijkstra's shortest path algorithm (Chapter 5.4)
• Greedy algorithms where you always process the "best" item next

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

int main() {
    // Max-heap: always gives you the MAXIMUM
    priority_queue<int> maxPQ;

    maxPQ.push(5);
    maxPQ.push(1);
    maxPQ.push(8);
    maxPQ.push(3);

    // Pop in decreasing order
    while (!maxPQ.empty()) {
        cout << maxPQ.top() << " ";  // always the current max
        maxPQ.pop();
    }
    cout << "\n";  // prints: 8 5 3 1

    return 0;
}

🐛 The Min-Heap Gotcha

By default, priority_queue is a max-heap (gives largest first). For a min-heap (gives smallest first), you need a special syntax:

// MAX-heap (default) — gives LARGEST first
priority_queue<int> maxPQ;

// MIN-heap — gives SMALLEST first (note the extra template arguments!)
priority_queue<int, vector<int>, greater<int>> minPQ;

minPQ.push(5);
minPQ.push(1);
minPQ.push(8);
minPQ.push(3);

while (!minPQ.empty()) {
    cout << minPQ.top() << " ";
    minPQ.pop();
}
// prints: 1 3 5 8  (smallest first)

Common Operations with Time Complexity

💡 Priority queue with pairs: You can store pair<int, int> in a priority queue. It compares by .first first, then .second — useful for Dijkstra's algorithm where you store {distance, node}.

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> minPQ;
// min-heap of (distance, node) pairs — used in Dijkstra

3.1.8 unordered_map and unordered_set — Hash-Based Speed

The regular map and set are sorted (using a balanced binary search tree internally), giving O(log N) operations. The unordered_ variants use a hash table for O(1) average time — faster, but no guaranteed ordering.

💡 Underlying Principle: Why is map O(log N) while unordered_map is O(1)?

• map / set internally use a red-black tree (a self-balancing binary search tree). Each insert, find, or delete traverses from root to leaf, with tree height ≈ log₂N, hence O(log N). Advantage: elements are always sorted, supporting lower_bound and range queries.
• unordered_map / unordered_set internally use a hash table. The hash function directly computes the storage location, averaging O(1). But element order is not guaranteed, and worst case can degrade to O(N) (with severe hash collisions).
• Contest experience: If you only need lookup/insert without ordered traversal, prefer unordered_map. But if you get TLE from worst-case unordered_map behavior (being hacked), switching back to map is the safest choice.

unordered_map<string, int> freq;
freq["apple"]++;
freq["banana"]++;
freq["apple"]++;

cout << freq["apple"] << "\n";   // 2 (same interface as map)

unordered_set<int> seen;
seen.insert(5);
seen.insert(10);
cout << seen.count(5) << "\n";   // 1 (found)
cout << seen.count(7) << "\n";   // 0 (not found)

Hack-Resistant unordered_map

In competitive programming, adversaries can craft inputs that cause many hash collisions, degrading unordered_map to O(N) per operation. A simple defense is to use a custom hash:

// Add this before main() to make unordered_map harder to hack
struct custom_hash {
    size_t operator()(long long x) const {
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9LL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebLL;
        return x ^ (x >> 31);
    }
};
unordered_map<long long, int, custom_hash> safe_map;

For most problems, the default unordered_map is fine. Use the custom hash only when you suspect anti-hash tests.

When to use which

⚡ Pro Tip: unordered_map can be 5-10× faster than map for large inputs with string keys. But it has rare "worst case" behavior that can be exploited in competitive programming — use map if you're getting TLE with unordered_map and suspect a hack.

3.1.9 The auto Keyword and Range-Based For

C++ can often figure out the type of a variable automatically. The auto keyword tells the compiler: "you figure out the type."

auto x = 42;          // x is int
auto y = 3.14;        // y is double
auto v = vector<int>{1, 2, 3};  // v is vector<int>

map<string, int> freq;
auto it = freq.find("cat");  // type would be map<string,int>::iterator — very long!
// auto saves you from writing that

⚠️ auto pitfall: auto deduces the type at compile time — it doesn't make variables dynamically typed. Also, auto x = 1000000000 * 2; deduces int and may overflow; write auto x = 1000000000LL * 2; to get long long.

Range-Based For

Clean iteration over any container:

vector<int> nums = {10, 20, 30, 40, 50};

// Read-only iteration (copies each element — fine for int, wasteful for string)
for (int x : nums) {
    cout << x << " ";
}

// Reference: no copy, can modify elements
for (int& x : nums) {
    x *= 2;   // doubles each element in-place
}

// Const reference: no copy, read-only (best for large types like string)
for (const auto& x : nums) {
    cout << x << " ";
}

Rule of thumb for range-based for:

• Small types (int, char): for (int x : v) — copy is fine
• Large types (string, pair, structs): for (const auto& x : v) — avoid copying
• Need to modify: for (auto& x : v)

3.1.10 Useful STL Algorithms

These functions from <algorithm> and <numeric> work on any sequence:

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

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

    // Sort ascending
    sort(v.begin(), v.end());
    // v = {1, 1, 2, 3, 4, 5, 6, 9}

    // Binary search (on SORTED sequence only!)
    cout << binary_search(v.begin(), v.end(), 5) << "\n";  // 1 (found)
    cout << binary_search(v.begin(), v.end(), 7) << "\n";  // 0 (not found)

    // lower_bound: first position where value >= target
    auto it = lower_bound(v.begin(), v.end(), 4);
    cout << *it << "\n";   // 4
    cout << (it - v.begin()) << "\n";  // index: 3

    // upper_bound: first position where value > target
    auto it2 = upper_bound(v.begin(), v.end(), 4);
    cout << (it2 - v.begin()) << "\n";  // index: 4 (first element > 4)
    // Elements in range [lo, hi]: upper_bound(hi+1) - lower_bound(lo)

    // Min and max
    cout << *min_element(v.begin(), v.end()) << "\n";  // 1
    cout << *max_element(v.begin(), v.end()) << "\n";  // 9

    // Sum of all elements
    long long total = accumulate(v.begin(), v.end(), 0LL);
    cout << total << "\n";  // 31

    // Count occurrences
    cout << count(v.begin(), v.end(), 1) << "\n";  // 2

    // Reverse
    reverse(v.begin(), v.end());

    // Fill with a value
    fill(v.begin(), v.end(), 0);  // all zeros

    return 0;
}

3.1.11 Putting It All Together: Word Frequency Counter

Let's build a complete mini-program that uses map, vector, and sort together.

Problem: Read N words, count how many times each word appears, then print:

1. All words and their counts in alphabetical order
2. The most frequently appearing word

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

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

    int n;
    cin >> n;

    // Step 1: Count word frequencies using a map
    map<string, int> freq;
    for (int i = 0; i < n; i++) {
        string word;
        cin >> word;
        freq[word]++;   // if word is new, creates entry with 0, then increments
    }

    // Step 2: Print all words in alphabetical order (map iterates in sorted key order)
    cout << "All words:\n";
    for (auto& entry : freq) {
        // entry.first = word, entry.second = count
        cout << entry.first << ": " << entry.second << "\n";
    }

    // Step 3: Find the most frequent word
    // max_element on the map: compare by value (.second)
    auto best = max_element(
        freq.begin(),
        freq.end(),
        [](const pair<string,int>& a, const pair<string,int>& b) {
            return a.second < b.second;  // compare by count
        }
    );

    cout << "\nMost frequent: \"" << best->first << "\" (appears "
         << best->second << " times)\n";

    return 0;
}

Sample Input:

10
the cat sat on the mat the cat sat on

Sample Output:

All words:
cat: 2
mat: 1
on: 2
sat: 2
the: 3

Most frequent: "the" (appears 3 times)

Complexity Analysis:

• Time: O(N log N) — each freq[word]++ is O(log N), N times total; max_element traverses the map in O(M), where M is the number of distinct words
• Space: O(M) — map stores M distinct words

🤔 Why does iterating over map give alphabetical order? map internally uses a balanced BST (binary search tree), which keeps keys sorted. So when you iterate, you always get keys in sorted order automatically — no extra sorting needed!

💡 Alternative for finding max: Instead of max_element on the map, you could also transfer entries to a vector<pair<string,int>>, sort by .second descending, and take the first element. Both approaches are O(M) after counting.

Chapter Summary

📌 Key Takeaways

❓ FAQ

Q1: What is the difference between vector and a plain array? When to use which?

A: vector can grow dynamically (push_back), knows its own size (.size()), and can be safely passed to functions. Plain arrays have fixed size but are slightly faster (global arrays auto-initialize to 0). In contests, use vector for most cases; global large arrays (like int dp[100001]) are sometimes more convenient as C arrays.

Q2: When to choose map vs unordered_map?

A: If you only need lookup/insert/delete, use unordered_map (O(1)) for speed. If you need ordered traversal or lower_bound/upper_bound, use map (O(log N)). In contests without special requirements, map is safer (cannot be hacked).

Q3: Is priority_queue a max-heap or min-heap by default?

A: Max-heap. pq.top() returns the maximum element. For a min-heap, declare as priority_queue<int, vector<int>, greater<int>>.

Q4: When is a custom struct better than pair?

A: pair's .first/.second have poor readability — three months later you may forget what .first means. struct lets you give members meaningful names (like .weight, .value). When data has 3 or more fields, struct is necessary.

Q5: Why does sort on a vector<pair<int,int>> sort by .first first?

A: pair has a built-in operator< that compares .first first; if equal, it compares .second. This is called lexicographic order — the same way words are sorted in a dictionary. You can rely on this behavior without writing a custom comparator.

Q6: What's the difference between s.count(x) and s.find(x) != s.end() for a set?

A: For set and map, both are O(log N) and functionally equivalent for checking existence. count returns 0 or 1 (sets have no duplicates), while find returns an iterator you can use to access the element directly. Prefer find when you also need to read the value; prefer count for a simple yes/no check.

🔗 Connections to Later Chapters

• Chapter 3.4 (Monotonic Stack & Queue): monotonic stack for next-greater-element problems; monotonic deque for sliding window max/min
• Chapter 3.6 (Stacks & Queues): deep dive into stack and queue algorithm applications — bracket matching, BFS
• Chapter 3.8 (Maps & Sets): advanced usage of map/set — frequency counting, multiset
• Chapter 3.3 (Sorting): sort with custom comparators used with vector and pair
• priority_queue appears frequently in Chapter 4.1 (Greedy) and Chapter 5.3 (Kruskal MST)
• The STL containers in this chapter are the foundational tools for all subsequent chapters in this book

Practice Problems

🌡️ Warm-Up Problems

Warm-up 3.1.1 — Set Membership Read N integers, then read Q queries. For each query, read one integer and print YES if it appeared in the original N integers, NO otherwise.

5
10 20 30 40 50
3
20
35
50

YES
NO
YES

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

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

    int n;
    cin >> n;

    set<int> s;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);
    }

    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        cout << (s.count(x) ? "YES" : "NO") << "\n";
    }

    return 0;
}

Warm-up 3.1.2 — Character Frequency Read a string (no spaces). Print each character that appears in it along with its count, in alphabetical order.

Sample Input: hello Sample Output:

e: 1
h: 1
l: 2
o: 1

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

int main() {
    string s;
    cin >> s;

    map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }

    for (auto& entry : freq) {
        cout << entry.first << ": " << entry.second << "\n";
    }

    return 0;
}

Warm-up 3.1.3 — Reverse with Stack Read a string (no spaces). Use a stack to print the string in reverse.

Sample Input: hello → Sample Output: olleh

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

int main() {
    string s;
    cin >> s;

    stack<char> st;
    for (char c : s) {
        st.push(c);
    }

    while (!st.empty()) {
        cout << st.top();
        st.pop();
    }
    cout << "\n";

    return 0;
}

Warm-up 3.1.4 — Queue Simulation Simulate a line of exactly 5 people. Their names are: Alice, Bob, Charlie, Dave, Eve. They join in that order. Serve them one at a time (pop from front) and print each name as they're served.

Expected Output:

Serving: Alice
Serving: Bob
Serving: Charlie
Serving: Dave
Serving: Eve

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

int main() {
    queue<string> line;
    line.push("Alice");
    line.push("Bob");
    line.push("Charlie");
    line.push("Dave");
    line.push("Eve");

    while (!line.empty()) {
        cout << "Serving: " << line.front() << "\n";
        line.pop();
    }

    return 0;
}

Warm-up 3.1.5 — Top 3 Largest Read N integers. Using a priority_queue, find and print the 3 largest values (in descending order).

Sample Input:

7
5 1 9 3 7 2 8

Sample Output:

9
8
7

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

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

    priority_queue<int> pq;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pq.push(x);
    }

    for (int i = 0; i < 3 && !pq.empty(); i++) {
        cout << pq.top() << "\n";
        pq.pop();
    }

    return 0;
}

🏋️ Core Practice Problems

Problem 3.1.6 — Unique Elements Read N integers. Print only the unique values, in the order they first appeared (not sorted). If a value appears more than once, print it only on its first occurrence.

8
3 1 4 1 5 9 2 6

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

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

    int n;
    cin >> n;

    unordered_set<int> seen;
    bool first = true;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (seen.count(x) == 0) {   // haven't seen x yet
            seen.insert(x);
            if (!first) cout << " ";
            cout << x;
            first = false;
        }
    }
    cout << "\n";

    return 0;
}

7
apple banana apple cherry banana apple cherry

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

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

    int n;
    cin >> n;

    map<string, int> freq;
    for (int i = 0; i < n; i++) {
        string w;
        cin >> w;
        freq[w]++;
    }

    string bestWord;
    int bestCount = 0;

    // Map iterates in sorted (alphabetical) order — so first word we see with max count wins
    for (auto& entry : freq) {
        if (entry.second > bestCount) {
            bestCount = entry.second;
            bestWord = entry.first;
        }
    }

    cout << bestWord << "\n";
    return 0;
}

6 9
1 8 3 6 4 5

1 8
3 6
4 5

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

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

    int n, t;
    cin >> n >> t;

    set<int> seen;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    for (int i = 0; i < n; i++) {
        int complement = t - arr[i];  // we need arr[i] + complement = t
        if (seen.count(complement)) {
            // complement came before arr[i], print in order: complement arr[i]
            cout << complement << " " << arr[i] << "\n";
        }
        seen.insert(arr[i]);
    }

    return 0;
}

Problem 3.1.9 — Bracket Matching Read a string containing only (, ), [, ], {, }. Print YES if all brackets are properly matched and nested, NO otherwise.

Sample Input 1: {[()]} → Output: YES Sample Input 2: ([)] → Output: NO Sample Input 3: ((() → Output: NO

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

int main() {
    string s;
    cin >> s;

    stack<char> st;
    bool ok = true;

    for (char ch : s) {
        if (ch == '(' || ch == '[' || ch == '{') {
            st.push(ch);    // opening: push
        } else {
            // closing bracket
            if (st.empty()) {
                ok = false;  // no matching opening
                break;
            }
            char top = st.top();
            st.pop();

            // Check if it matches
            if ((ch == ')' && top != '(') ||
                (ch == ']' && top != '[') ||
                (ch == '}' && top != '{')) {
                ok = false;
                break;
            }
        }
    }

    if (!st.empty()) ok = false;  // leftover unmatched opening brackets

    cout << (ok ? "YES" : "NO") << "\n";
    return 0;
}

Problem 3.1.10 — Top K Elements Read N integers and K. Print the K largest values in descending order.

Sample Input:

8 3
4 9 1 7 3 5 2 8

Sample Output:

9
8
7

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

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

    int n, k;
    cin >> n >> k;

    priority_queue<int> pq;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pq.push(x);
    }

    for (int i = 0; i < k && !pq.empty(); i++) {
        cout << pq.top() << "\n";
        pq.pop();
    }

    return 0;
}

🏆 Challenge Problems

Challenge 3.1.11 — Inventory System Process M commands on a store inventory. Each command is one of:

• ADD name quantity — add quantity units of product name
• REMOVE name quantity — remove quantity units (if removing more than available, set to 0)
• QUERY name — print current quantity of name (0 if never added)

6
ADD apple 10
ADD banana 5
QUERY apple
REMOVE apple 3
QUERY apple
QUERY grape

10
7
0

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

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

    int m;
    cin >> m;

    map<string, long long> inventory;

    while (m--) {
        string cmd;
        cin >> cmd;

        if (cmd == "ADD") {
            string name;
            long long qty;
            cin >> name >> qty;
            inventory[name] += qty;
        } else if (cmd == "REMOVE") {
            string name;
            long long qty;
            cin >> name >> qty;
            inventory[name] -= qty;
            if (inventory[name] < 0) inventory[name] = 0;
        } else {  // QUERY
            string name;
            cin >> name;
            // Use count to avoid creating an entry for missing items
            if (inventory.count(name)) {
                cout << inventory[name] << "\n";
            } else {
                cout << 0 << "\n";
            }
        }
    }

    return 0;
}

Challenge 3.1.12 — Sliding Window Maximum Read N integers and a window size K. Print the maximum value in each window of K consecutive elements.

Sample Input:

8 3
1 3 -1 -3 5 3 6 7

Sample Output:

3
3
5
5
6
7

(Windows: [1,3,-1]→3, [3,-1,-3]→3, [-1,-3,5]→5, [-3,5,3]→5, [5,3,6]→6, [3,6,7]→7)

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

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

    int n, k;
    cin >> n >> k;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    deque<int> dq;  // stores indices, front = index of current maximum

    for (int i = 0; i < n; i++) {
        // Remove indices that are out of the current window
        while (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }

        // Remove indices of elements smaller than arr[i] from the back
        // (they can never be the maximum while arr[i] is in the window)
        while (!dq.empty() && arr[dq.back()] <= arr[i]) {
            dq.pop_back();
        }

        dq.push_back(i);

        // Print maximum for windows that are full (starting from index k-1)
        if (i >= k - 1) {
            cout << arr[dq.front()] << "\n";
        }
    }

    return 0;
}

Challenge 3.1.13 — Haybales Range Count (USACO Bronze style)

N haybales are placed at various positions on a number line. Process Q queries: for each query (L, R), print how many haybales have positions in the range [L, R] inclusive.

5 4
3 1 7 5 2
1 3
2 6
4 8
1 10

3
3
2
5

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

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

    int n, q;
    cin >> n >> q;

    vector<int> pos(n);
    for (int i = 0; i < n; i++) cin >> pos[i];

    sort(pos.begin(), pos.end());  // must sort for binary search to work

    while (q--) {
        int l, r;
        cin >> l >> r;

        // lower_bound(l): first position >= l
        // upper_bound(r): first position > r
        // Elements in [l, r] = count between these two iterators
        auto lo = lower_bound(pos.begin(), pos.end(), l);
        auto hi = upper_bound(pos.begin(), pos.end(), r);

        cout << (hi - lo) << "\n";  // distance between iterators = count
    }

    return 0;
}

Looking Ahead: Beyond Basic STL

This chapter covered the core STL containers you'll use in 90% of problems. As you progress, you'll encounter more specialized structures:

• deque<T> — double-ended queue; supports O(1) push/pop at both front and back. Used in the sliding window maximum problem (Challenge 3.1.12) and monotonic deque (Chapter 3.4).
• multiset<T> — like set but allows duplicate elements. Useful when you need sorted order with repeats.
• bitset<N> — fixed-size sequence of bits; extremely fast for subset/membership problems.
• Trie (prefix tree) — stores strings by sharing common prefixes, enabling O(L) lookup where L is string length.

Visual: Trie Data Structure

A trie (prefix tree) stores strings by sharing common prefixes. Words "bat", "car", "card", "care", "cat" share prefixes efficiently: "ca" is stored once, branching to "r" and "t". Double-ringed nodes mark word endings. Tries are used for autocomplete, spell checking, and string matching. For string hashing alternatives, see Chapter 3.7 (Hashing Techniques).

Chapter 3.2: Arrays & Prefix Sums

📝 Before You Continue: Make sure you're comfortable with arrays, vectors, and basic loops (Chapters 2.2–2.3). You'll also want to understand long long overflow (Chapter 2.1).

Imagine you have an array of N numbers, and someone asks you 100,000 times: "What is the sum of elements from index L to index R?" A naive approach recomputes the sum from scratch each time — that's O(N) per query, or O(N × Q) total. With N = Q = 10^5, that's 10^10 operations. Way too slow.

Prefix sums solve this in O(N) preprocessing and O(1) per query. This is one of the most elegant and useful techniques in all of competitive programming.

💡 Key Insight: Prefix sums transform a "range query" problem into a subtraction. Instead of summing L to R every time, you precompute cumulative sums and subtract two of them. This trades O(Q) repeated work for one-time O(N) preprocessing.

3.2.1 The Prefix Sum Idea

The prefix sum of an array is a new array where each element stores the cumulative sum up to that index.

Visual: Prefix Sum Array

The diagram above shows how the prefix sum array is constructed from the original array, and how a range query sum(L, R) = P[R] - P[L-1] is computed in O(1) time. The blue cells highlight a query range while the red and green cells show the two prefix values being subtracted.

Given array: A = [3, 1, 4, 1, 5, 9, 2, 6] (1-indexed for clarity)

Index:  1  2  3  4  5  6  7  8
A:      3  1  4  1  5  9  2  6
P:      3  4  8  9  14 23 25 31

Where P[i] = A[1] + A[2] + ... + A[i].

Why 1-Indexing?

Using 1-indexed arrays lets us define P[0] = 0 (the "empty prefix" sums to zero). This makes the query formula P[R] - P[L-1] work even when L = 1 — we'd compute P[R] - P[0] = P[R], which is correct.

Building the Prefix Sum Array

// Solution: Build Prefix Sum Array — O(N)
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    // Step 1: Read input (1-indexed)
    vector<int> A(n + 1);
    for (int i = 1; i <= n; i++) cin >> A[i];

    // Step 2: Build prefix sums
    vector<long long> P(n + 1, 0);  // P[0] = 0 (base case)
    for (int i = 1; i <= n; i++) {
        P[i] = P[i - 1] + A[i];   // ← KEY LINE: each P[i] = all elements up to i
    }

    return 0;
}

Complexity Analysis:

• Time: O(N) — one pass through the array
• Space: O(N) — stores the prefix array

Step-by-step trace for A = [3, 1, 4, 1, 5]:

i=1: P[1] = P[0] + A[1] = 0 + 3 = 3
i=2: P[2] = P[1] + A[2] = 3 + 1 = 4
i=3: P[3] = P[2] + A[3] = 4 + 4 = 8
i=4: P[4] = P[3] + A[4] = 8 + 1 = 9
i=5: P[5] = P[4] + A[5] = 9 + 5 = 14

3.2.2 Range Sum Queries in O(1)

Once you have the prefix sum array, the sum from index L to R is:

sum(L, R) = P[R] - P[L-1]

Why? P[R] = sum of elements 1..R. P[L-1] = sum of elements 1..(L-1). Their difference = sum of elements L..R.

💡 Key Insight: Think of P[i] as "the total sum of the first i elements." To get the sum of a window [L, R], you subtract the "prefix before L" from the "prefix through R." It's like: big triangle minus smaller triangle = trapezoid.

// Solution: Range Sum Queries — Preprocessing O(N), Each Query O(1)
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;
long long A[MAXN];
long long P[MAXN];

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

    int n, q;
    cin >> n >> q;

    // Step 1: Read array
    for (int i = 1; i <= n; i++) cin >> A[i];

    // Step 2: Build prefix sum — O(n)
    P[0] = 0;
    for (int i = 1; i <= n; i++) {
        P[i] = P[i - 1] + A[i];
    }

    // Step 3: Answer q range sum queries — O(1) each
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        cout << P[r] - P[l - 1] << "\n";  // ← KEY LINE: range sum formula
    }

    return 0;
}

Sample Input:

8 3
3 1 4 1 5 9 2 6
1 4
3 7
2 6

Sample Output:

9
21
20

Verification:

• sum(1,4) = P[4] - P[0] = 9 - 0 = 9 → A[1]+A[2]+A[3]+A[4] = 3+1+4+1 = 9 ✓
• sum(3,7) = P[7] - P[2] = 25 - 4 = 21 → A[3]+...+A[7] = 4+1+5+9+2 = 21 ✓
• sum(2,6) = P[6] - P[1] = 23 - 3 = 20 → A[2]+...+A[6] = 1+4+1+5+9 = 20 ✓

⚠️ Common Mistake: Writing P[R] - P[L] instead of P[R] - P[L-1]. The formula includes both endpoints L and R — you want to subtract the sum before L, not the sum at L.

Total Complexity: O(N + Q) — perfect for N, Q up to 10^5.

3.2.3 USACO Example: Breed Counting

This is a classic USACO Bronze problem (2015 December).

Problem: N cows in a line. Each cow is breed 1, 2, or 3. Answer Q queries: how many cows of breed B are in positions L to R?

Solution: Maintain one prefix sum array per breed.

// Solution: Multi-Breed Prefix Sums — O(N + Q)
#include <bits/stdc++.h>
using namespace std;

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

    int n, q;
    cin >> n >> q;

    vector<int> breed(n + 1);
    vector<vector<long long>> P(4, vector<long long>(n + 1, 0));
    // P[b][i] = number of cows of breed b in positions 1..i

    // Step 1: Build prefix sums for each breed
    for (int i = 1; i <= n; i++) {
        cin >> breed[i];
        for (int b = 1; b <= 3; b++) {
            P[b][i] = P[b][i - 1] + (breed[i] == b ? 1 : 0);  // ← KEY LINE
        }
    }

    // Step 2: Answer each query in O(1)
    for (int i = 0; i < q; i++) {
        int l, r, b;
        cin >> l >> r >> b;
        cout << P[b][r] - P[b][l - 1] << "\n";
    }

    return 0;
}

🏆 USACO Tip: Many USACO Bronze problems involve "count elements satisfying property X in a range." If Q is large, always consider prefix sums.

3.2.4 USACO-Style Problem Walkthrough: Farmer John's Grass Fields

🔗 Related Problem: This is a fictional USACO-style problem inspired by "Breed Counting" and "Tallest Cow" — both classic Bronze problems.

Problem Statement: Farmer John has N fields in a row. Field i has grass[i] units of grass. He needs to answer Q queries: "What is the total grass in fields L through R (inclusive)?" With N, Q up to 10^5, he needs each query answered in O(1).

6 4
4 2 7 1 8 3
1 3
2 5
4 6
1 6

13
18
12
25

Step-by-Step Solution:

Step 1: Understand the problem. We have an array [4, 2, 7, 1, 8, 3] and need range sums.

Step 2: Build the prefix sum array.

Index:  0  1  2  3  4  5  6
grass:  -  4  2  7  1  8  3
P:      0  4  6  13 14 22 25

Step 3: Answer queries using P[R] - P[L-1]:

• Query (1,3): P[3] - P[0] = 13 - 0 = 13 ✓
• Query (2,5): P[5] - P[1] = 22 - 4 = 18 ✓
• Query (4,6): P[6] - P[3] = 25 - 13 = 12 ✓
• Query (1,6): P[6] - P[0] = 25 - 0 = 25 ✓

Complete C++ Solution:

// Farmer John's Grass Fields — Prefix Sum Solution O(N + Q)
#include <bits/stdc++.h>
using namespace std;

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

    int n, q;
    cin >> n >> q;

    // Step 1: Read grass values and build prefix sum simultaneously
    vector<long long> P(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long g;
        cin >> g;
        P[i] = P[i - 1] + g;   // ← KEY LINE: incremental prefix sum
    }

    // Step 2: Answer each query in O(1)
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << P[r] - P[l - 1] << "\n";
    }

    return 0;
}

Why is this O(N + Q)?

• Building prefix sums: one loop, N iterations → O(N)
• Each query: one subtraction → O(1) per query, O(Q) total
• Total: O(N + Q) — much better than the O(NQ) brute force

⚠️ Common Mistake: Using int instead of long long for the prefix sum. If grass values are up to 10^9 and N = 10^5, the total could be up to 10^14 — way beyond int's range of ~2×10^9.

3.2.5 2D Prefix Sums

For 2D grids, you can extend prefix sums to answer rectangular range queries in O(1).

Given an R×C grid, define P[r][c] = sum of all elements in the rectangle from (1,1) to (r,c).

Building the 2D Prefix Sum

P[r][c] = A[r][c] + P[r-1][c] + P[r][c-1] - P[r-1][c-1]

The subtraction removes the overlap (otherwise the top-left rectangle is counted twice).

💡 Key Insight (Inclusion-Exclusion): Visualize the four rectangles:

• P[r-1][c] = the "top" rectangle
• P[r][c-1] = the "left" rectangle
• P[r-1][c-1] = the "top-left corner" (counted in BOTH above — so subtract once)
• A[r][c] = the single new cell

Step-by-Step 2D Prefix Sum Worked Example

Let's trace through a 4×4 grid:

Original Grid A:

     c=1  c=2  c=3  c=4
r=1:  1    2    3    4
r=2:  5    6    7    8
r=3:  9   10   11   12
r=4: 13   14   15   16

Building P step by step (left-to-right, top-to-bottom):

P[1][1] = A[1][1] = 1

P[1][2] = A[1][2] + P[0][2] + P[1][1] - P[0][1] = 2 + 0 + 1 - 0 = 3
P[1][3] = A[1][3] + P[0][3] + P[1][2] - P[0][2] = 3 + 0 + 3 - 0 = 6
P[1][4] = 4 + 0 + 6 - 0 = 10

P[2][1] = A[2][1] + P[1][1] + P[2][0] - P[1][0] = 5 + 1 + 0 - 0 = 6
P[2][2] = A[2][2] + P[1][2] + P[2][1] - P[1][1] = 6 + 3 + 6 - 1 = 14
P[2][3] = 7 + 6 + 14 - 3 = 24
P[2][4] = 8 + 10 + 24 - 6 = 36

P[3][1] = 9 + 6 + 0 - 0 = 15
P[3][2] = 10 + 14 + 15 - 6 = 33
P[3][3] = 11 + 24 + 33 - 14 = 54
P[3][4] = 12 + 36 + 54 - 24 = 78

P[4][1] = 13 + 15 + 0 - 0 = 28
P[4][2] = 14 + 33 + 28 - 15 = 60
P[4][3] = 15 + 54 + 60 - 33 = 96
P[4][4] = 16 + 78 + 96 - 54 = 136

Resulting prefix sum grid P:

     c=1  c=2  c=3  c=4
r=1:  1    3    6   10
r=2:  6   14   24   36
r=3: 15   33   54   78
r=4: 28   60   96  136

Query: Sum of subgrid (r1=2, c1=2) to (r2=3, c2=3):

ans = P[3][3] - P[1][3] - P[3][1] + P[1][1]
    = 54     -  6     -  15     +  1
    = 34

Verify: A[2][2]+A[2][3]+A[3][2]+A[3][3] = 6+7+10+11 = 34 ✓

Visualization of the inclusion-exclusion:

// Solution: 2D Prefix Sums — Build O(R×C), Query O(1)
#include <bits/stdc++.h>
using namespace std;

const int MAXR = 1001, MAXC = 1001;
int A[MAXR][MAXC];
long long P[MAXR][MAXC];

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

    int R, C;
    cin >> R >> C;

    for (int r = 1; r <= R; r++)
        for (int c = 1; c <= C; c++)
            cin >> A[r][c];

    // Step 1: Build 2D prefix sum — O(R × C)
    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            P[r][c] = A[r][c]
                    + P[r-1][c]    // rectangle above
                    + P[r][c-1]    // rectangle to the left
                    - P[r-1][c-1]; // ← KEY LINE: remove overlap (counted twice)
        }
    }

    // Step 2: Answer each query in O(1)
    int q;
    cin >> q;
    while (q--) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        long long ans = P[r2][c2]
                      - P[r1-1][c2]    // subtract top strip
                      - P[r2][c1-1]    // subtract left strip
                      + P[r1-1][c1-1]; // add back top-left corner
        cout << ans << "\n";
    }

    return 0;
}

Complexity Analysis:

• Build time: O(R × C)
• Query time: O(1) per query
• Space: O(R × C)

⚠️ Common Mistake: Forgetting to add P[r1-1][c1-1] back in the query formula. The top strip and left strip both include the top-left corner, so it gets subtracted twice — you need to add it back once!

3.2.6 Difference Arrays

Now that you've seen how 2D prefix sums extend the 1D idea to grids, let's look at the dual operation: the difference array. Just as differentiation is the inverse of integration in calculus, the difference array is the inverse of the prefix sum — if prefix sums accumulate values (turning point data into range data), difference arrays decompose range operations into point markers. Having mastered 2D prefix sums first makes this duality especially clear.

This duality is powerful: to apply a range update efficiently, you mark the boundaries in the difference array, and later take a prefix sum to recover the final result.

Problem: Start with all zeros. Apply M updates: "add V to all positions from L to R." Then print the final array.

Naively, each update is O(R-L+1). With a difference array, each update is O(1), and reconstruction is O(N).

💡 Key Insight: Instead of adding V to every position in [L, R] (slow), we record "+V at position L" and "-V at position R+1" (fast). When we later do a prefix sum of these markers, the +V and -V "cancel out" outside [L,R], so the net effect is exactly adding V to [L,R].

// Solution: Difference Array for Range Updates — O(N + M)
#include <bits/stdc++.h>
using namespace std;

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

    int n, m;
    cin >> n >> m;

    vector<long long> diff(n + 2, 0);  // difference array (extra space for R+1 case)

    // Step 1: Process all range updates in O(1) each
    for (int i = 0; i < m; i++) {
        int l, r, v;
        cin >> l >> r >> v;
        diff[l] += v;      // ← KEY LINE: mark start of range
        diff[r + 1] -= v;  // ← KEY LINE: mark end+1 to undo the addition
    }

    // Step 2: Reconstruct the final array by taking prefix sums of diff
    long long running = 0;
    for (int i = 1; i <= n; i++) {
        running += diff[i];
        cout << running;
        if (i < n) cout << " ";
    }
    cout << "\n";

    return 0;
}

Sample Input:

5 3
1 3 2
2 5 3
3 4 -1

Step-by-step trace:

📝 索引说明： 以下追踪中 diff 数组使用 1-indexed（即 diff[1]..diff[n+1]），与代码 vector<long long> diff(n + 2, 0) 一致。方括号内的数字表示 diff[1], diff[2], ..., diff[6]（n=5 时，数组共 7 个位置，有效使用 diff[1..6]）。

初始状态:           diff[1..6] = [0,  0,  0,  0,  0,  0]

After update(1,3,+2): diff[1]+=2, diff[4]-=2
                      diff[1..6] = [2,  0,  0, -2,  0,  0]

After update(2,5,+3): diff[2]+=3, diff[6]-=3
                      diff[1..6] = [2,  3,  0, -2,  0, -3]

After update(3,4,-1): diff[3]+=-1 即 diff[3]-=1, diff[5]-=(-1) 即 diff[5]+=1
                      diff[1..6] = [2,  3, -1, -2,  1, -3]

Prefix sum reconstruction:
i=1: running = 0+2 = 2  → result[1] = 2
i=2: running = 2+3 = 5  → result[2] = 5
i=3: running = 5-1 = 4  → result[3] = 4
i=4: running = 4-2 = 2  → result[4] = 2
i=5: running = 2+1 = 3  → result[5] = 3

Sample Output:

2 5 4 2 3

Complexity Analysis:

• Time: O(N + M) — O(1) per update, O(N) reconstruction
• Space: O(N) — just the difference array

⚠️ Common Mistake: Declaring diff with size N+1 instead of N+2. When R=N, you write to diff[R+1] = diff[N+1], which needs to exist!

3.2.7 2D Difference Arrays

Just as the 1D difference array is the inverse of the 1D prefix sum, the 2D difference array is the inverse of the 2D prefix sum. It lets you add a value V to an entire rectangular subgrid [r1,c1]..[r2,c2] in O(1) time.

The Four-Corner Update

To add V to all cells in rectangle [r1,c1] to [r2,c2], mark four corners in the diff array:

diff[r1][c1]     += V   // start of rectangle
diff[r1][c2+1]   -= V   // cancel right overflow
diff[r2+1][c1]   -= V   // cancel bottom overflow
diff[r2+1][c2+1] += V   // add back double-cancelled corner

This is the 2D analogue of the 1D trick diff[L] += V; diff[R+1] -= V. After all updates, take a 2D prefix sum of the diff array to recover the final values.

💡 Key Insight: The four-corner marking is the exact inverse of the inclusion-exclusion query formula for 2D prefix sums. In queries we subtract two strips and add back a corner; in updates we add two strips and subtract a corner. They are mirror operations!

Complete C++ Implementation

// Solution: 2D Difference Array — O(1) per update, O(RC) rebuild
#include <bits/stdc++.h>
using namespace std;

const int MAXR = 1002, MAXC = 1002;
long long diff[MAXR][MAXC];  // extra row+col for sentinels

void update(int r1, int c1, int r2, int c2, long long V) {
    diff[r1][c1]     += V;  // ← top-left corner
    diff[r1][c2+1]   -= V;  // ← top-right+1
    diff[r2+1][c1]   -= V;  // ← bottom+1-left
    diff[r2+1][c2+1] += V;  // ← bottom+1-right+1 (add back)
}

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

    int R, C, M;
    cin >> R >> C >> M;

    memset(diff, 0, sizeof diff);

    // Step 1: Apply all rectangle updates in O(1) each
    for (int i = 0; i < M; i++) {
        int r1, c1, r2, c2;
        long long V;
        cin >> r1 >> c1 >> r2 >> c2 >> V;
        update(r1, c1, r2, c2, V);
    }

    // Step 2: Rebuild via 2D prefix sum — O(R × C)
    for (int r = 1; r <= R; r++)
        for (int c = 1; c <= C; c++)
            diff[r][c] += diff[r-1][c] + diff[r][c-1] - diff[r-1][c-1];

    // Now diff[r][c] holds the final value at (r,c)
    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            cout << diff[r][c];
            if (c < C) cout << " ";
        }
        cout << "\n";
    }

    return 0;
}

Worked Example

Consider a 3×3 grid, initially all zeros. Two updates:

• update(1,1, 2,2, +5) — add 5 to the top-left 2×2 block
• update(2,2, 3,3, +3) — add 3 to the bottom-right 2×2 block

After marking diff[][]:

       c=0  c=1  c=2  c=3  c=4
r=0:    0    0    0    0    0
r=1:    0   +5    0   -5    0
r=2:    0    0   +3    0   -3
r=3:    0   -5    0   +5    0
r=4:    0    0   -3    0   +3

After 2D prefix sum rebuild:

       c=1  c=2  c=3
r=1:    5    5    0
r=2:    5    8    3
r=3:    0    3    3

Verification: Cell (2,2) = 5+3 = 8 ✓ (covered by both updates).

Complexity Analysis:

• Update time: O(1) per rectangle — just 4 additions
• Rebuild time: O(R × C) — one 2D prefix sum pass
• Space: O(R × C)

⚠️ Common Mistake: Declaring the diff array as diff[R+1][C+1] instead of diff[R+2][C+2]. When r2=R and c2=C, you write to diff[R+1][C+1], which must exist!

3.2.8 USACO Example: Max Subarray Sum

Problem (variation of Kadane's algorithm): Find the contiguous subarray with the maximum sum.

// Solution: Kadane's Algorithm — O(N) Time, O(1) Space
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    vector<int> A(n);
    for (int &x : A) cin >> x;

    // Kadane's Algorithm: O(n)
    long long maxSum = LLONG_MIN;  // LLONG_MIN = smallest long long
    long long current = 0;

    for (int i = 0; i < n; i++) {
        current += A[i];
        maxSum = max(maxSum, current);
        if (current < 0) current = 0;  // ← KEY LINE: restart if sum goes negative
    }

    cout << maxSum << "\n";

    return 0;
}

💡 Key Insight: Why reset current to 0 when it goes negative? Because a negative prefix sum hurts any future subarray. If the running sum so far is -5, any future subarray starting fresh (sum 0) will always beat continuing from -5.

Alternative with prefix sums: The max subarray sum equals max over all pairs (i,j) of P[j] - P[i-1]. For each j, this is maximized when P[i-1] is minimized. Track the running minimum of prefix sums!

// Alternative: Min Prefix Trick — also O(N)
long long maxSum = LLONG_MIN, minPrefix = 0, prefix = 0;
for (int x : A) {
    prefix += x;
    maxSum = max(maxSum, prefix - minPrefix);  // best sum ending here
    minPrefix = min(minPrefix, prefix);         // track minimum prefix seen so far
    // ⚠️ 注意：minPrefix 的更新必须在 maxSum 之后。
    // 若提前更新 minPrefix，相当于允许空子数组（长度为0，和为0）参与比较，
    // 会导致结果在全负数组时错误地返回 0 而非最大负数。
}

⚠️ Common Mistakes in Chapter 3.2

1. Off-by-one in range queries: P[R] - P[L] instead of P[R] - P[L-1]. Always verify on a small example.
2. Overflow: Prefix sums of large values can exceed int range (2×10^9). Use long long for the prefix array even if elements are int.
3. 2D query formula: Forgetting the +P[r1-1][c1-1] term in the 2D query — a very easy slip.
4. Difference array size: Declaring diff[n+1] when you need diff[n+2] (because you write to index r+1 which could be n+1).
5. 1-indexing vs 0-indexing: If you use 0-indexed prefix sums, the query formula changes to P[R+1] - P[L]. Pick one convention and stick to it within a problem.
6. 2D difference array size: Declaring diff[R+1][C+1] when you need diff[R+2][C+2] — the four-corner update writes to (r2+1, c2+1), which must be in bounds.
7. 2D difference rebuild order: The 2D prefix sum rebuild must process cells left-to-right, top-to-bottom (same order as building a 2D prefix sum). Mixing the order produces wrong results.

Chapter Summary

📌 Key Takeaways

*After O(N) reconstruction pass to read all values.

🧩 Core Formula Quick Reference

❓ FAQ

Q1: What is the relationship between prefix sums and difference arrays?

A: They are inverse operations. Taking the prefix sum of an array gives the prefix sum array; taking the difference (adjacent element differences) of the prefix sum array restores the original. Conversely, taking the prefix sum of a difference array also restores the original. This is analogous to integration and differentiation in mathematics.

Q2: When to use prefix sums vs. difference arrays?

A: Rule of thumb — look at the operation type:

• Multiple range sum queries → prefix sum (preprocess O(N), query O(1))
• Multiple range add/subtract operations → difference array (update O(1), restore O(N) at the end)
• If both operations alternate, you need a more advanced data structure (like Segment Tree in Chapter 3.9)

Q3: Can prefix sums handle dynamic modifications? (array elements change)

A: No. Prefix sums are a one-time preprocessing; the array cannot change afterward. If elements are modified, use Fenwick Tree (BIT) or Segment Tree, which support point updates and range queries in O(log N) time.

Q4: Why are there two versions of Kadane's algorithm (current=0 vs minPrefix)?

A: Both are essentially the same, both O(N). The first (classic Kadane) is more intuitive: restart when the current subarray sum goes negative. The second (min-prefix method) uses prefix sum thinking: max subarray = max(P[j] - P[i-1]) = max(P[j]) - min(P[i]). Choose based on personal preference.

Q5: What are the space constraints for 2D prefix sums?

A: If R, C are both up to 10^4, the P array needs 10^8 long long values (about 800MB) — exceeding memory limits. Generally R×C ≤ 10^6~10^7 is safe. For larger grids, consider compression or offline processing.

🔗 Connections to Later Chapters

• Chapter 3.4 (Two Pointers): sliding window can also do range queries, but only for fixed-size or monotonically moving windows; prefix sums are more general
• Chapter 3.3 (Sorting & Searching): binary search can combine with prefix sums — e.g., binary search on the prefix sum array for the first position ≥ target
• Chapter 3.9 (Segment Trees): solves "dynamic update + range query" problems that prefix sums cannot handle
• Chapters 6.1–6.3 (DP): many state transitions involve range sums; prefix sums are an important tool for optimizing DP
• The difference array idea ("+V at start, -V after end") recurs in sweep line algorithms, event sorting, and other advanced techniques

Practice Problems

Problem 3.2.1 — Range Sum 🟢 Easy Read N integers and Q queries. Each query gives L and R. Print the sum of elements from index L to R (1-indexed).

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, q; cin >> n >> q;
    vector<long long> P(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        P[i] = P[i-1] + x;  // prefix sum
    }
    while (q--) {
        int l, r; cin >> l >> r;
        cout << P[r] - P[l-1] << "\n";
    }
}

Problem 3.2.2 — Range Add, Point Query 🟢 Easy Start with N zeros. Process M operations: each adds V to all positions from L to R. After all operations, print the value at each position.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m; cin >> n >> m;
    vector<long long> diff(n + 2, 0);  // 1-indexed, size n+2
    while (m--) {
        int l, r; long long v; cin >> l >> r >> v;
        diff[l] += v;
        diff[r+1] -= v;
    }
    long long cur = 0;
    for (int i = 1; i <= n; i++) {
        cur += diff[i];
        cout << cur << " \n"[i == n];
    }
}

Problem 3.2.3 — Rectangular Sum 🟡 Medium Read an N×M grid and Q queries. Each query gives (r1,c1,r2,c2). Print the sum of the subgrid.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, m, q; cin >> n >> m >> q;
    vector<vector<long long>> P(n+1, vector<long long>(m+1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int x; cin >> x;
            P[i][j] = x + P[i-1][j] + P[i][j-1] - P[i-1][j-1];  // inclusion-exclusion
        }
    while (q--) {
        int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
        cout << P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1] << "\n";
    }
}

(r1-1,c1-1) ─── (r1-1,c2)
     │  subtract   │
     │             │
(r2,c1-1) ───  (r2,c2)
  add back        actual

Problem 3.2.4 — USACO 2016 January Bronze: Mowing the Field 🔴 Hard Farmer John mows grass along a path. Cells visited more than once contribute to "double-mowed" area. Count cells visited at least twice.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;  // number of moves
    map<pair<int,int>, int> cnt;
    int x = 0, y = 0; cnt[{x,y}]++;
    while (n--) {
        char dir; int steps; cin >> dir >> steps;
        int dx = (dir=='E') - (dir=='W');
        int dy = (dir=='N') - (dir=='S');
        while (steps--) {
            x += dx; y += dy;
            cnt[{x,y}]++;
        }
    }
    int doubleMowed = 0;
    for (auto& [pos, c] : cnt) if (c >= 2) doubleMowed++;
    cout << doubleMowed << "\n";
}

Problem 3.2.5 — 2D Range Add 🟡 Medium Given N×M grid (initially zero), Q operations each adds V to rectangle [r1,c1] to [r2,c2]. Output final grid.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, q; cin >> n >> m >> q;
    vector<vector<long long>> D(n+2, vector<long long>(m+2, 0));
    while (q--) {
        int r1, c1, r2, c2; long long v;
        cin >> r1 >> c1 >> r2 >> c2 >> v;
        D[r1][c1] += v;
        D[r1][c2+1] -= v;
        D[r2+1][c1] -= v;
        D[r2+1][c2+1] += v;  // 4 corner updates
    }
    // Rebuild via 2D prefix sum (in-place)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            D[i][j] += D[i-1][j] + D[i][j-1] - D[i-1][j-1];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cout << D[i][j] << " \n"[j == m];
}

Problem 3.2.6 — Maximum Subarray (Kadane's Algorithm) 🟡 Medium Read N integers (possibly negative). Find the maximum sum of a contiguous subarray.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    long long best = LLONG_MIN, cur = 0;
    for (int i = 0; i < n; i++) {
        long long x; cin >> x;
        cur = max(x, cur + x);  // start fresh or extend
        best = max(best, cur);
    }
    cout << best << "\n";
}

x=-2: cur=-2, best=-2
x=1:  cur=max(1, -2+1)=1, best=1
x=-3: cur=max(-3, 1-3)=-2, best=1
x=4:  cur=max(4, -2+4)=4, best=4
x=-1: cur=max(-1, 4-1)=3, best=4
x=2:  cur=5, best=5
x=1:  cur=6, best=6 ✓
x=-5: cur=1, best=6
x=4:  cur=5, best=6

🏆 Challenge Problem: Cows and Paint Buckets An N×M grid contains paint buckets, each with a positive value. Select any rectangular subgrid. Score = (max value in subgrid) − (sum of border cells). Find optimal rectangle. (N, M ≤ 500)

Chapter 3.3: Sorting & Searching

📝 Before You Continue: You should be comfortable with arrays, vectors, and basic loops (Chapters 2.2–2.3). Familiarity with std::sort from Chapter 3.1 helps, but this chapter covers it in depth.

Sorting and searching are two of the most fundamental operations in computer science. In USACO, a huge fraction of problems become easy once you sort the data correctly. And binary search — the ability to search a sorted array in O(log n) — is a technique you'll reach for again and again.

3.3.1 Why Sorting Matters

Consider this problem: "Given N cow heights, find the two cows whose heights are closest together."

• Unsorted approach: Compare every pair → O(N²). For N = 10^5, that's 10^10 operations. TLE.
• Sorted approach: Sort the heights → O(N log N). Then the closest pair must be adjacent! Check N-1 pairs → O(N). Total: O(N log N). ✓

💡 Key Insight: Sorting transforms many O(N²) brute-force solutions into O(N log N) or O(N) solutions. When you see "find the pair with property X" or "find the minimum/maximum of something involving two elements," always consider sorting first.

Complexity Analysis:

• Sorting: O(N log N) time, O(log N) space (recursion stack depth; std::sort uses Introsort — a hybrid of Quicksort + Heapsort + Insertion Sort — all three branches use at most O(log N) stack space)
• After sorting: adjacent comparisons or two-pointer techniques are O(N)

3.3.2 How Sorting Works (Conceptual)

You don't need to implement sorting algorithms yourself — std::sort does it for you. But understanding the ideas helps you reason about time complexity and choose the right approach.

Here are four classic sorting algorithms, each with an interactive visualization to help you understand how they work.

🫧 Bubble Sort — O(N²)

Repeatedly scan the array, swapping adjacent elements that are out of order. Each pass "bubbles" the current maximum to its final position at the end of the unsorted region:

Initial: [64, 34, 25, 12, 22, 11, 90]
Pass 1:  [64, 34, 25, 12, 22, 11, 90] → [34, 25, 12, 22, 11, 64, 90]   ← 64 bubbles to 2nd-to-last
Pass 2:  [34, 25, 12, 22, 11, 64, 90] → [25, 12, 22, 11, 34, 64, 90]   ← 34 bubbles to 3rd-to-last
Pass 3:  [25, 12, 22, 11, 34, 64, 90] → [12, 22, 11, 25, 34, 64, 90]   ← 25 bubbles to 4th-to-last
...

📝 Note: 90 was already in its correct position at the start, so Pass 1 doesn't move it — instead, 64 (the next largest) bubbles to the second-to-last position. Each pass guarantees one more element is in its final sorted position at the end.

Bubble sort is O(N²). Never use it on large inputs in competitive programming. We cover it only because it's conceptually the simplest.

🃏 Insertion Sort — O(N²) / O(N) best case

Divide the array into a left "sorted region" and a right "unsorted region." Each step takes the first element of the unsorted region and inserts it into the correct position in the sorted region:

Start: [64 | 34, 25, 12, 22, 11, 90]   ← | sorted on left
i=1:   [34, 64 | 25, 12, 22, 11, 90]   ← 34 inserted before 64
i=2:   [25, 34, 64 | 12, 22, 11, 90]   ← 25 inserted at front
i=3:   [12, 25, 34, 64 | 22, 11, 90]   ← 12 inserted at front
...

💡 Insertion sort's strength: Very fast on nearly-sorted arrays (approaches O(N)). std::sort switches to insertion sort for small subarrays.

void insertionSort(vector<int>& a) {
    int n = a.size();
    for (int i = 1; i < n; i++) {
        int key = a[i];   // element to insert
        int j = i - 1;
        // shift elements greater than key one position to the right
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;  // place key in its correct position
    }
}

🔀 Merge Sort — O(N log N) always

Divide and conquer: recursively split the array in half, then merge the two sorted halves back together:

[38, 27, 43, 3, 9, 82, 10]
        ↓ split recursively
[38,27,43,3]    [9,82,10]
[38,27] [43,3]  [9,82] [10]
[38][27][43][3] [9][82][10]
        ↓ merge bottom-up
[27,38] [3,43]  [9,82] [10]
  [3,27,38,43]    [9,10,82]
      [3,9,10,27,38,43,82] ✓

Merge sort is O(N log N) in all cases and is a stable sort.

void merge(vector<int>& a, int lo, int mid, int hi) {
    vector<int> tmp(a.begin() + lo, a.begin() + hi + 1);
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (tmp[i - lo] <= tmp[j - lo]) {
            a[k++] = tmp[i - lo];  // 左半部分当前元素更小，优先放入以保持稳定性
            i++;
        } else {
            a[k++] = tmp[j - lo];  // 右半部分当前元素更小，放入
            j++;
        }
    }
    while (i <= mid) { a[k++] = tmp[i - lo]; i++; }  // 追加左半部分剩余元素
    while (j <= hi)  { a[k++] = tmp[j - lo]; j++; }  // 追加右半部分剩余元素
}

void mergeSort(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid);       // sort left half
    mergeSort(a, mid + 1, hi);   // sort right half
    merge(a, lo, mid, hi);       // merge two sorted halves
}

⚡ Quicksort — O(N log N) average

Quicksort is one of the core algorithms underlying std::sort. Its key idea is divide and conquer:

1. Pick a pivot element (typically the last element)
2. Partition: move all elements ≤ pivot to the left, all > pivot to the right; pivot lands in its final position
3. Recurse on the left and right subarrays

[8, 3, 6, 1, 9, 2, 7, 4]   ← pivot = 4
         ↓ partition
[3, 1, 2, 4, 9, 6, 7, 8]   ← 4 in final position; left ≤ 4, right > 4
 ↑_______↑  ↑  ↑__________↑
 left subarray  right subarray

Recurse on [3,1,2] → [1,2,3]
Recurse on [9,6,7,8] → [6,7,8,9]

Final: [1, 2, 3, 4, 6, 7, 8, 9] ✓

// Partition arr[lo..hi] using last element as pivot.
// Returns the final index of the pivot.
int partition(vector<int>& arr, int lo, int hi) {
    int pivot = arr[hi];   // choose last element as pivot
    int i = lo - 1;        // i points to end of "≤ pivot" region

    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);  // bring arr[j] into ≤ pivot region
        }
    }
    swap(arr[i + 1], arr[hi]);  // place pivot in its final position
    return i + 1;               // return pivot's index
}

void quickSort(vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return;           // base case: subarray length ≤ 1
    int p = partition(arr, lo, hi); // p is pivot's final position
    quickSort(arr, lo, p - 1);      // sort left subarray
    quickSort(arr, p + 1, hi);      // sort right subarray
}

⚠️ Worst case: If the pivot is always the max or min (e.g., already-sorted input), recursion depth degrades to O(N) and total time becomes O(N²). std::sort avoids this via random pivot selection or median-of-three, guaranteeing O(N log N) worst case.

3.3.3 std::sort in Practice

⚠️ Stability Note: std::sort is NOT stable — it uses Introsort (Quicksort + Heapsort + Insertion sort hybrid), which does not preserve the relative order of equal elements. If you need stable sorting, use std::stable_sort instead (see the comparison table in this section).

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

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

    int n;
    cin >> n;
    vector<int> v(n);
    for (int &x : v) cin >> x;

    // Sort ascending
    sort(v.begin(), v.end());

    // Sort descending
    sort(v.begin(), v.end(), greater<int>());

    // Sort only part of a vector (indices 2 through 5 inclusive)
    sort(v.begin() + 2, v.begin() + 6);

    for (int x : v) cout << x << " ";
    cout << "\n";

    return 0;
}

Sorting by Multiple Criteria

Often you want to sort by one field, and break ties with another. With pair, this is automatic (sorts by .first, then .second):

vector<pair<int, string>> students;
students.push_back({85, "Alice"});
students.push_back({92, "Bob"});
students.push_back({85, "Charlie"});

sort(students.begin(), students.end());
// Result: {85, "Alice"}, {85, "Charlie"}, {92, "Bob"}
// Sorted by score first, then alphabetically by name

Custom Comparators

A comparator is a function that returns true if the first argument should come before the second in the sorted order.

The clearest way to write a comparator is as a standalone function:

struct Cow {
    string name;
    int weight;
    int height;
};

// Sort by weight ascending; break ties by height descending
bool cmpCow(const Cow &a, const Cow &b) {
    if (a.weight != b.weight) return a.weight < b.weight;  // lighter first
    return a.height > b.height;                             // taller first (tie-break)
}

int main() {
    vector<Cow> cows = {{"Bessie", 500, 140}, {"Elsie", 480, 135}, {"Moo", 500, 138}};

    sort(cows.begin(), cows.end(), cmpCow);

    for (auto &c : cows) {
        cout << c.name << " " << c.weight << " " << c.height << "\n";
    }
    // Output:
    // Elsie 480 135
    // Bessie 500 140
    // Moo 500 138
    return 0;
}

💡 Style Note: Defining cmp as a standalone function (rather than an inline lambda) makes the sorting logic easier to read, test, and reuse — especially when the comparison involves multiple fields.

Sorting Algorithm Stability

⚠️ Important: std::sort is NOT stable — equal elements may appear in any order after sorting. Use std::stable_sort if relative order of equal elements must be preserved.

Sorting Algorithm Stability Comparison

📝 Note: std::sort uses Introsort (a hybrid of Quicksort + Heapsort + Insertion sort). Because Quicksort is not stable, std::sort makes no guarantee on the relative order of equal elements. When you sort students by score and need students with the same score to remain in their original order, use std::stable_sort.

* std::stable_sort is O(N log N) when sufficient extra memory (O(N)) is available. It degrades to O(N log² N) only when memory is limited and in-place merging is required.

Visual: Sorting Algorithm Comparison

This chart compares the time complexity, space usage, and stability of common sorting algorithms, helping you choose the right one for each situation.

Counting Sort — O(N+K) for Small Value Ranges

When values are bounded integers in a small range [0, MAXVAL], counting sort beats std::sort by a wide margin:

// Counting sort: for integers in range [0, MAXVAL]
// Time O(N+MAXVAL), stable sort
void countingSort(vector<int>& arr, int maxVal) {
    vector<int> cnt(maxVal + 1, 0);
    for (int x : arr) cnt[x]++;
    int idx = 0;
    for (int v = 0; v <= maxVal; v++)
        for (int i = 0; i < cnt[v]; i++) arr[idx++] = v;  // 用 for 循环避免 cnt[v] 被减为 -1 的副作用
}
// USACO use case: faster than std::sort when value range is small (e.g., cow IDs 1-1000)

When to use counting sort in USACO:

• Cow IDs in range [1, 1000], N = 10^6 → counting sort is O(N + 1000) vs O(N log N)
• Grade values [0, 100] → trivially fast
• Color categories [0, 3] → instant

Caution: If MAXVAL is large (e.g., 10^9), counting sort requires O(MAXVAL) memory — don't use it. Coordinate compress first (Section 3.3.6), then count.

3.3.4 Binary Search

Binary search finds a target in a sorted array in O(log n) — instead of O(n) for linear search.

Analogy: Searching for a word in a dictionary. You don't start from A and read every entry — you open to the middle, check if your word is before or after, then repeat. Each step cuts the search space in half: after k steps, you've gone from N candidates to N/2^k. When N/2^k < 1, you're done — that takes k = log₂(N) steps.

💡 Key Insight: Binary search works whenever you have a monotone predicate — a condition that is false false false ... true true true (or the reverse). You can binary search for the boundary between false and true in O(log N).

Visual: Binary Search in Action

The diagram above shows a single-step binary search finding 7 in [1,3,5,7,9,11,13]. The left (L), right (R), and mid (M) pointers are shown. The key insight: computing mid = left + (right - left) / 2 avoids integer overflow compared to (left + right) / 2.

Manual Binary Search

// Solution: Binary Search — O(log N)
#include <bits/stdc++.h>
using namespace std;

// Returns index of target in sorted arr, or -1 if not found
int binarySearch(const vector<int> &arr, int target) {
    int lo = 0, hi = (int)arr.size() - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // ← KEY LINE: avoid overflow (don't use (lo+hi)/2)

        if (arr[mid] == target) {
            return mid;         // found!
        } else if (arr[mid] < target) {
            lo = mid + 1;       // target is in the right half
        } else {
            hi = mid - 1;       // target is in the left half
        }
    }

    return -1;  // not found
}

int main() {
    vector<int> v = {1, 3, 5, 7, 9, 11, 13, 15};
    cout << binarySearch(v, 7) << "\n";   // 3 (index)
    cout << binarySearch(v, 6) << "\n";   // -1 (not found)
    return 0;
}

Step-by-step trace for searching 7 in [1, 3, 5, 7, 9, 11, 13, 15]:

lo=0, hi=7: mid=3, arr[3]=7 → FOUND at index 3 ✓

Searching for 6:
lo=0, hi=7: mid=3, arr[3]=7 > 6 → hi=2
lo=0, hi=2: mid=1, arr[1]=3 < 6 → lo=2
lo=2, hi=2: mid=2, arr[2]=5 < 6 → lo=3
lo=3 > hi=2: loop ends → return -1 ✓

Why lo + (hi - lo) / 2? If lo and hi are both large (close to INT_MAX), then lo + hi overflows! This formula is equivalent but safe.

The STL Way: lower_bound and upper_bound

These are almost always what you actually want in competitive programming:

// STL Binary Search Operations — all O(log N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1, 3, 3, 5, 7, 9, 9, 11};

    // lower_bound: iterator to first element >= target
    auto lb = lower_bound(v.begin(), v.end(), 3);
    cout << *lb << "\n";                    // 3 (first 3)
    cout << lb - v.begin() << "\n";         // 1 (index)

    // upper_bound: iterator to first element > target
    auto ub = upper_bound(v.begin(), v.end(), 3);
    cout << *ub << "\n";                    // 5 (first element after all 3s)
    cout << ub - v.begin() << "\n";         // 3 (index)

    // Count occurrences: upper_bound - lower_bound
    int count_of_3 = upper_bound(v.begin(), v.end(), 3)
                   - lower_bound(v.begin(), v.end(), 3);
    cout << count_of_3 << "\n";   // 2

    // Check if value exists
    bool exists = binary_search(v.begin(), v.end(), 7);
    cout << exists << "\n";  // 1

    // Find largest value <= target (floor)
    auto it = upper_bound(v.begin(), v.end(), 6);
    if (it != v.begin()) {
        --it;
        cout << *it << "\n";  // 5 (largest value <= 6)
    }

    return 0;
}

⚠️ Common Mistake: Using lower_bound/upper_bound on an unsorted container. These functions assume sorted order — on unsorted data, they give wrong results with no error!

3.3.5 Binary Search on the Answer

This is one of the most powerful and commonly-tested techniques in USACO Silver. The idea:

Instead of searching for a value in an array, binary search over the answer space itself.

When does this apply? When:

1. The answer is a number in some range [lo, hi]
2. There's a function canAchieve(X) that checks if X is feasible
3. The function is monotone: if X works, all values ≤ X also work (or all ≥ X work)

💡 Key Insight: Monotonicity means there's a "threshold" separating feasible from infeasible answers. Binary search finds this threshold in O(log(hi-lo)) calls to canAchieve. If each call takes O(f(N)), total time is O(f(N) × log(answer_range)).

Classic Example: Aggressive Cows (SPOJ AGGRCOW / Classic Problem)

Problem: N stalls at positions p[1..N], place C cows to maximize the minimum distance between any two cows.

Why binary search? If we can place cows with minimum gap D, we can also place them with gap D-1. So feasibility is monotone: there's a threshold D* where ≥ D* is infeasible and < D* is feasible. We binary search for D*.

The canPlace(minDist) function: Place the first cow at the leftmost stall, then greedily pick the next stall that is at least minDist away. Count how many cows we can place this way — if ≥ C, return true.

// Solution: Binary Search on Answer — O(N log N log(max_distance))
#include <bits/stdc++.h>
using namespace std;

int n, c;
vector<int> stalls;

// Can we place c cows such that the minimum gap between any two cows is >= minDist?
bool canPlace(int minDist) {
    int placed = 1;           // place first cow at stall 0
    int lastPos = stalls[0];  // position of last placed cow

    for (int i = 1; i < n; i++) {
        if (stalls[i] - lastPos >= minDist) {  // this stall is far enough
            placed++;
            lastPos = stalls[i];
        }
    }
    return placed >= c;  // did we place all c cows?
}

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

    cin >> n >> c;
    stalls.resize(n);
    for (int &x : stalls) cin >> x;
    sort(stalls.begin(), stalls.end());  // must sort first!

    // Binary search on the answer: what's the maximum possible minimum distance?
    int lo = 1, hi = stalls.back() - stalls.front();
    int answer = 0;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (canPlace(mid)) {
            answer = mid;    // mid works, try larger
            lo = mid + 1;
        } else {
            hi = mid - 1;    // mid doesn't work, try smaller
        }
    }

    cout << answer << "\n";
    return 0;
}

Trace for stalls = [1, 2, 4, 8, 9], C = 3:

Sorted: [1, 2, 4, 8, 9]
lo=1, hi=8

mid=4: canPlace(4)?
  Place cow at 1. Next stall ≥ 1+4=5: that's 8. Place at 8.
  Next stall ≥ 8+4=12: none. Total placed=2 < 3. Return false.
  → hi = 3

mid=2: canPlace(2)?
  Place cow at 1. Next stall ≥ 3: that's 4. Place at 4.
  Next stall ≥ 6: that's 8. Place at 8. Total placed=3 ≥ 3. Return true.
  → answer=2, lo=3

mid=3: canPlace(3)?
  Place cow at 1. Next ≥ 4: that's 4. Place at 4.
  Next ≥ 7: that's 8. Place at 8. Total placed=3 ≥ 3. Return true.
  → answer=3, lo=4

lo=4 > hi=3: done. Answer = 3

Another Classic: Minimum Time to Complete Tasks (Rope Cutting)

Problem: Given N ropes of lengths L[i], cut K ropes of equal length. What's the maximum length you can cut each piece to?

📝 Code Snippet: The following is a code fragment — for a complete runnable program structure, refer to the Aggressive Cows example above.

// 代码片段 — 完整程序请参考 Aggressive Cows 示例
// Can we get K pieces of length >= len from the ropes?
bool canCut(vector<int> &ropes, long long len, int K) {
    long long count = 0;
    for (int r : ropes) count += r / len;  // pieces from each rope
    return count >= K;
}

// Binary search: maximize len such that canCut(len) is true
long long lo = 1, hi = *max_element(ropes.begin(), ropes.end());
long long answer = 0;
while (lo <= hi) {
    long long mid = lo + (hi - lo) / 2;
    if (canCut(ropes, mid, K)) {
        answer = mid;
        lo = mid + 1;
    } else {
        hi = mid - 1;
    }
}

Template for Binary Search on Answer:

// Generic template — adapt lo, hi, and check() for your problem
long long lo = min_possible_answer;
long long hi = max_possible_answer;
long long answer = lo;  // or -1 if no valid answer exists

while (lo <= hi) {
    long long mid = lo + (hi - lo) / 2;
    if (check(mid)) {       // mid is feasible
        answer = mid;       // save it
        lo = mid + 1;       // try to do better (or worse, depending on problem)
    } else {
        hi = mid - 1;       // mid not feasible, go lower
    }
}

🏆 USACO Tip: Whenever a USACO problem asks "find the maximum X such that [some condition]" or "find the minimum X such that [some condition]," consider binary search on the answer. This technique solves USACO Silver problems frequently.

3.3.6 Coordinate Compression

Sometimes values are large (up to 10^9), but there are few distinct values. Coordinate compression maps them to small indices (0, 1, 2, ...).

// Solution: Coordinate Compression — O(N log N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> A = {100, 500, 200, 100, 700, 200};

    // Step 1: Get sorted unique values
    vector<int> sorted_unique = A;
    sort(sorted_unique.begin(), sorted_unique.end());
    sorted_unique.erase(unique(sorted_unique.begin(), sorted_unique.end()),
                        sorted_unique.end());
    // sorted_unique = {100, 200, 500, 700}

    // Step 2: Map each original value to its compressed index
    vector<int> compressed(A.size());
    for (int i = 0; i < (int)A.size(); i++) {
        compressed[i] = lower_bound(sorted_unique.begin(), sorted_unique.end(), A[i])
                        - sorted_unique.begin();
        // 100→0, 200→1, 500→2, 700→3
    }

    for (int x : compressed) cout << x << " ";
    cout << "\n";  // 0 2 1 0 3 1

    return 0;
}

3.3.7 Advanced Binary Search on Answer — Three Examples

Example 1: Minimum Time to Finish Tasks (Parametric Search)

Problem: N workers, M tasks with effort[i]. Assign tasks to workers (each worker gets contiguous tasks). Minimize the maximum time any worker spends (minimize the bottleneck).

This is the "Painter's Partition" problem. Binary search on the answer (max time T), check if T is achievable.

📝 Template Switch Notice: This example uses while (lo < hi) with hi = mid — different from the while (lo <= hi) template in Section 3.3.5. We switch here because we are minimizing the answer: when canFinish(mid) is true, mid itself is a candidate, so we set hi = mid (not hi = mid - 1) to avoid skipping it. When the loop ends, lo == hi is the answer directly — no need for a separate answer variable. See FAQ Q2 for a detailed comparison of the two templates.

// Check: can we distribute tasks among K workers so max work <= T?
bool canFinish(vector<int>& tasks, int K, long long T) {
    int workers = 1;
    long long current = 0;
    for (int t : tasks) {
        if (t > T) return false;  // single task exceeds T — impossible
        if (current + t > T) {
            workers++;             // start new worker
            current = t;
            if (workers > K) return false;
        } else {
            current += t;
        }
    }
    return true;
}

// Binary search on T — using "lo < hi" template (minimizing the answer)
long long lo = *max_element(tasks.begin(), tasks.end());  // minimum possible T
long long hi = accumulate(tasks.begin(), tasks.end(), 0LL);  // maximum T (1 worker)

while (lo < hi) {
    long long mid = lo + (hi - lo) / 2;
    if (canFinish(tasks, K, mid)) hi = mid;  // mid works, try smaller
    else lo = mid + 1;                        // mid doesn't work, need larger
}
cout << lo << "\n";  // minimum possible maximum time (lo == hi when loop ends)

📝 Note: Here we binary search for the minimum feasible T, so we use hi = mid when feasible (not answer = mid; lo = mid+1). The two templates are mirror images.

Example 2: Kth Smallest in Multiplication Table

Problem: N×M multiplication table. Find the Kth smallest value.

The table has values i*j for 1≤i≤N, 1≤j≤M. Binary search on the answer X: count how many values are ≤ X.

// Count values <= X in N×M multiplication table
long long countLE(long long X, int N, int M) {
    long long count = 0;
    for (int i = 1; i <= N; i++) {
        count += min((long long)M, X / i);
        // Row i has values i, 2i, ..., Mi
        // Count of values <= X in row i: min(M, floor(X/i))
    }
    return count;
}

// Binary search for Kth smallest
long long lo = 1, hi = (long long)N * M;
while (lo < hi) {
    long long mid = lo + (hi - lo) / 2;
    if (countLE(mid, N, M) >= K) hi = mid;
    else lo = mid + 1;
}
cout << lo << "\n";

Complexity: O(N log(NM)) — O(N) per check, O(log(NM)) iterations.

Example 3: USACO-Style Cable Length (Agri-Net inspired)

Problem: Given N farm locations, connect them all with cables. The cables must be at most length L. Find the maximum L such that you can form a spanning tree with all edges ≤ L.

// Binary search on maximum cable length L
// Check: does a spanning tree exist using only edges of length <= L?
// (This reduces to: is the graph connected when restricted to edges <= L?)
bool canConnect(vector<tuple<int,int,int>>& edges, int n, int L) {
    DSU dsu(n);
    for (auto [w, u, v] : edges) {
        if (w <= L) dsu.unite(u, v);
    }
    return dsu.components == 1;  // all nodes connected
}

3.3.8 lower_bound / upper_bound Complete Cheat Sheet

// 注意：以下代码假设已定义：#define all(v) (v).begin(), (v).end()
// 示例中 all 即 v.begin(), v.end()
vector<int> v = {1, 3, 3, 5, 7, 9, 9, 11};
//                0  1  2  3  4  5  6   7

// ── lower_bound: first position >= x ──
lower_bound(all(v), 3)  → index 1  (first 3)
lower_bound(all(v), 4)  → index 3  (first element >= 4, which is 5)
lower_bound(all(v), 12) → index 8  (past-end: no element ≥ 12 exists in the array)

// ── upper_bound: first position > x ──
upper_bound(all(v), 3)  → index 3  (first element after all 3s)
upper_bound(all(v), 4)  → index 3  (same as above: no 4s)
upper_bound(all(v), 11) → index 8  (past-end)

// ── Derived operations ──
// Count occurrences of x:
// upper_bound(all(v),3) - lower_bound(all(v),3) = 3 - 1 = 2 ✓
int cnt = upper_bound(all(v), 3) - lower_bound(all(v), 3);  // cnt = 2

// Does x exist?
binary_search(all(v), x)  // O(log N), returns bool

// Largest value <= x (floor):
auto it = upper_bound(all(v), x);
if (it != v.begin()) cout << *prev(it);  // *--it

// Smallest value >= x (ceil):
auto it = lower_bound(all(v), x);
if (it != v.end()) cout << *it;

// Largest value < x (strict floor):
auto it = lower_bound(all(v), x);
if (it != v.begin()) cout << *prev(it);

// Count elements < x:
lower_bound(all(v), x) - v.begin()

// Count elements <= x:
upper_bound(all(v), x) - v.begin()

// Count elements in range [a, b]:
upper_bound(all(v), b) - lower_bound(all(v), a)

3.3.9 Custom Predicate Binary Search

For non-standard sorted structures or custom criteria:

// Binary search with custom predicate
// Find first index i where pred(i) is true, in range [lo, hi]
// Assumption: pred is monotone: false...false, true...true

int lo = 0, hi = n - 1, answer = -1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (/* some condition on mid */) {
        answer = mid;
        hi = mid - 1;  // look for smaller index
    } else {
        lo = mid + 1;
    }
}

// Example: first index where arr[i] - arr[0] >= D
// (For a sorted array, arr[i] - arr[0] is monotonically non-decreasing,
//  so this predicate is monotone: false...false, true...true)
// ⚠️ Key requirement: the predicate MUST be monotone for binary search to work!
{
    int lo = 0, hi = n - 1, firstFar = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] - arr[0] >= D) {  // monotone: once true, stays true for all larger indices
            firstFar = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    // firstFar is the answer
}

// Floating point binary search (epsilon-based)
double lo_f = 0.0, hi_f = 1e9;
for (int iter = 0; iter < 100; iter++) {  // 100 iterations → error < 1e-30
    double mid = (lo_f + hi_f) / 2;
    if (check(mid)) hi_f = mid;
    else lo_f = mid;
}
// Answer: lo_f (or hi_f, they converge to same value)

🏆 USACO Pro Tip: "Binary search on answer" is one of the most common Silver techniques. When you see "maximize/minimize X subject to [constraint]," ask yourself: Is the feasibility function monotone? If yes, binary search.

3.3.10 Ternary Search — Finding the Peak of a Unimodal Function 🔮 Advanced / Gold+

⚠️ Scope Note: Ternary search is rarely required in USACO Silver. It appears occasionally in Gold/Platinum problems involving geometric optimization or parametric search. Treat this section as supplementary knowledge — understand the concept, but don't prioritize it over mastering binary search.

Binary search requires a monotone predicate (false→true boundary). For unimodal functions (increases then decreases), use ternary search to find the maximum.

💡 When to use: A function f is unimodal on [lo, hi] if it first strictly increases then strictly decreases (or is always one direction). Ternary search finds the maximum point in O(log((hi-lo)/eps)) evaluations.

USACO appearances: Ternary search rarely appears at Silver level. At Gold/Platinum level, it occasionally appears in problems involving geometric optimization (e.g., "find the optimal point on a line to minimize the sum of distances") or parametric search over a continuous unimodal function.

// Ternary search: find maximum of unimodal function f on [lo, hi]
// Prerequisite: f increases then decreases (unimodal)
// Time: O(log((hi-lo)/eps)) for continuous, or O(log N) for integers

// f must be declared/defined before calling this
double ternarySearch(double lo, double hi) {
    for (int iter = 0; iter < 200; iter++) {
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2)) lo = m1;  // maximum is in [m1, hi]
        else hi = m2;                 // maximum is in [lo, m2]
    }
    return (lo + hi) / 2;  // Maximum point (lo ≈ hi after convergence)
}

// Integer ternary search (when f is defined on integers):
int ternarySearchInt(int lo, int hi) {
    // 使用 > 2 而非 >= 2：保留至少 3 个候选值再暴力枚举。
    // 当范围缩至 2 个元素时，m1 == m2（因为 (hi-lo)/3 == 0），
    // 会导致死循环。用 > 2 可确保安全退出并正确处理边界。
    while (hi - lo > 2) {
        int m1 = lo + (hi - lo) / 3;
        int m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2)) lo = m1 + 1;
        else hi = m2 - 1;
    }
    // Check remaining candidates [lo, hi] (at most 3 elements)
    int best = lo;
    for (int x = lo + 1; x <= hi; x++)
        if (f(x) > f(best)) best = x;
    return best;
}

Contrast with binary search:

⚠️ Note: Ternary search on integers requires care — use while (hi - lo > 2) to avoid infinite loops when the range shrinks to 2 or 3 elements, then brute-force the remaining candidates.

⚠️ Common Mistakes in Chapter 3.3

1. Sorting with wrong comparator: Your lambda must return true if a should come BEFORE b. If it returns true for a == b, you get undefined behavior (strict weak ordering violation).
2. Binary search on unsorted array: lower_bound and upper_bound assume sorted order. On unsorted data, results are meaningless.
3. Off-by-one in binary search: lo <= hi vs lo < hi matters. When in doubt, test your binary search on a 1-element and 2-element array.
4. Wrong answer range in "binary search on answer": If the answer could be 0, set lo = 0, not lo = 1. If it could be very large, make sure hi is large enough (use long long if necessary).
5. Integer overflow in mid computation: Always write mid = lo + (hi - lo) / 2, never (lo + hi) / 2.

Chapter Summary

📌 Key Takeaways

🧩 Binary Search Template Quick Reference

❓ FAQ

Q1: Is sort's time complexity O(N log N) or O(N²)?

A: C++'s std::sort uses Introsort (a hybrid of Quicksort + Heapsort + Insertion sort), guaranteeing O(N log N) worst case. No need to worry about degrading to O(N²). But note: if your custom comparator doesn't satisfy strict weak ordering, behavior is undefined (may infinite loop or crash).

Q2: What's the difference between lo <= hi and lo < hi in binary search?

A: The two styles correspond to different templates:

• while (lo <= hi): when search ends, lo > hi, answer is stored in answer variable. Good for "find target value" or "maximize value satisfying condition".
• while (lo < hi): when search ends, lo == hi, answer is lo. Good for "minimize value satisfying condition". Both can solve all problems; the key is pairing with the correct update rule. Beginners should pick one style and stick with it.

Q3: What problems is "binary search on answer" applicable to? How to identify them?

A: Three signals: ① The problem asks "the maximum/minimum X such that..."; ② There exists a decision function check(X) that can determine feasibility in polynomial time; ③ The decision function is monotone (X feasible → X-1 also feasible, or vice versa). If all three hold, binary search on answer applies.

Q4: What is coordinate compression actually useful for?

A: When the value range is large (e.g., 10^9) but the number of distinct values is small (e.g., 10^5), coordinate compression maps large values to small indices 0~N-1. This lets you use arrays instead of maps (faster), or perform prefix sums/BIT operations over the value domain. Frequently needed in USACO Silver.

Q5: Why can't the sort comparator use <=?

A: C++ sorting requires the comparator to satisfy strict weak ordering: when a == b, comp(a,b) must return false. <= returns true when a==b, violating this rule. The result is undefined behavior — may infinite loop, crash, or produce incorrect ordering.

🔗 Connections to Later Chapters

• Chapter 3.4 (Two Pointers): two-pointer techniques are often used after sorting — sort first O(N log N), then two pointers O(N)
• Chapter 3.2 (Prefix Sums): prefix sum arrays are naturally ordered, enabling binary search on them (e.g., find first prefix sum ≥ target)
• Chapters 4.1 & 5.4 (Greedy + Shortest Paths): Dijkstra internally uses a priority queue + greedy strategy, fundamentally related to sorting
• Chapter 6.2 (DP): LIS (Longest Increasing Subsequence) can be optimized to O(N log N) using binary search
• "Binary search on answer" is one of the most core techniques in USACO Silver, also frequently combined in Chapter 4.1 (Greedy)

Practice Problems

Problem 3.3.1 — Closest Pair 🟢 Easy Read N integers. Find the pair with the minimum difference.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n); for (int& x : a) cin >> x;
    sort(a.begin(), a.end());
    int best = INT_MAX;
    for (int i = 1; i < n; i++)
        best = min(best, a[i] - a[i-1]);
    cout << best << "\n";
}

Problem 3.3.2 — Room Allocation 🟡 Medium N events with start/end times. What is the maximum number of events overlapping at any moment?

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<pair<int,int>> evs;  // (time, delta)
    for (int i = 0; i < n; i++) {
        int s, e; cin >> s >> e;
        evs.push_back({s, +1});
        evs.push_back({e, -1});
    }
    // End-before-start tie-break: when equal time,
    // process ends first (delta=-1) so "touching" intervals don't overlap.
    sort(evs.begin(), evs.end(),
         [](auto& a, auto& b){ return a.first != b.first ? a.first < b.first : a.second < b.second; });
    int cur = 0, best = 0;
    for (auto& [t, d] : evs) { cur += d; best = max(best, cur); }
    cout << best << "\n";
}

Events: (1,+1), (2,+1), (3,+1), (4,-1), (5,-1), (6,-1)
Sweep:   1       2       3       2       1       0
Max: 3 (at time 3, all three intervals active)

Problem 3.3.3 — Kth Smallest 🟡 Medium Find K-th smallest element in array.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k; cin >> n >> k;
    vector<int> a(n); for (int& x : a) cin >> x;
    // nth_element partitions so that a[k-1] is in correct sorted position
    nth_element(a.begin(), a.begin() + (k-1), a.end());
    cout << a[k-1] << "\n";
}

int lo = *min_element(a.begin(), a.end());
int hi = *max_element(a.begin(), a.end());
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    int cnt = count_if(a.begin(), a.end(), [&](int x){ return x <= mid; });
    if (cnt >= k) hi = mid;
    else lo = mid + 1;
}
cout << lo << "\n";

Problem 3.3.4 — Aggressive Cows 🔴 Hard N stalls at positions p[1..N]. Place C cows to maximize the minimum pairwise distance.

#include <bits/stdc++.h>
using namespace std;
int N, C;
vector<int> p;

bool canPlace(int D) {
    int placed = 1, last = p[0];
    for (int i = 1; i < N; i++) {
        if (p[i] - last >= D) { placed++; last = p[i]; }
        if (placed >= C) return true;
    }
    return false;
}

int main() {
    cin >> N >> C;
    p.resize(N); for (int& x : p) cin >> x;
    sort(p.begin(), p.end());

    int lo = 1, hi = p.back() - p.front(), ans = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (canPlace(mid)) { ans = mid; lo = mid + 1; }  // feasible, try larger
        else hi = mid - 1;
    }
    cout << ans << "\n";
}

Problem 3.3.5 — Painter's Partition 🔴 Hard N boards with widths. K painters, each paints 1 unit time per unit width. Assign contiguous boards to minimize total painting time.

#include <bits/stdc++.h>
using namespace std;
int N, K;
vector<long long> W;

bool canFinish(long long T) {
    int painters = 1;
    long long cur = 0;
    for (long long w : W) {
        if (w > T) return false;  // single board exceeds budget
        if (cur + w > T) { painters++; cur = w; }
        else cur += w;
    }
    return painters <= K;
}

int main() {
    cin >> N >> K;
    W.resize(N); for (long long& x : W) cin >> x;
    long long lo = *max_element(W.begin(), W.end());  // lower bound: largest board
    long long hi = accumulate(W.begin(), W.end(), 0LL);  // upper bound: total sum
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (canFinish(mid)) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << "\n";
}

⚠️ Common Mistakes in Sorting & Searching

🏆 Challenge Problem: USACO 2016 February Silver: Fencing the Cows Fence all N points in a convex region using minimum fencing. This is the Convex Hull problem — look up the Graham scan or Jarvis march algorithms. While this is a Gold-level topic, thinking about it now will prime your intuition.

Chapter 3.4: Two Pointers & Sliding Window

📝 Before You Continue: You should be comfortable with arrays, vectors, and std::sort (Chapters 2.3–3.3). This technique requires a sorted array for the classic two-pointer approach.

Two pointers and sliding window are among the most elegant tricks in competitive programming. They transform naive O(N²) solutions into O(N) by exploiting monotonicity: as one pointer moves forward, the other never needs to go backward.

3.4.1 The Two Pointer Technique

The idea: maintain two indices, left and right, into a sorted array. Move them toward each other (or in the same direction) based on the current sum/window.

When to use:

• Finding a pair/triplet with a given sum in a sorted array
• Checking if a sorted array contains two elements with a specific relationship
• Problems where "if we can do X with window size k, we can do X with window size k-1"

The diagram shows how two pointers converge toward the center, each step eliminating an entire row/column of pairs from consideration.

The sliding window variant keeps both pointers moving right. When the condition is met, shrink from the left to find the minimum window:

Problem: Find All Pairs with Sum = Target

Naïve O(N²) approach:

// O(N²): check every pair
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (arr[i] + arr[j] == target) {
            cout << arr[i] << " + " << arr[j] << "\n";
        }
    }
}

Two Pointer O(N) approach (requires sorted array):

// Solution: Two Pointer — O(N log N) for sort + O(N) for search
#include <bits/stdc++.h>
using namespace std;

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

    int n, target;
    cin >> n >> target;
    vector<int> arr(n);
    for (int &x : arr) cin >> x;

    sort(arr.begin(), arr.end());  // MUST sort first

    int left = 0, right = n - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) {
            cout << arr[left] << " + " << arr[right] << " = " << target << "\n";
            left++;
            right--;  // advance both pointers
        } else if (sum < target) {
            left++;   // sum too small: move left pointer right (increase sum)
        } else {
            right--;  // sum too large: move right pointer left (decrease sum)
        }
    }

    return 0;
}

Why Does This Work?

Key insight: After sorting, if arr[left] + arr[right] < target, then no element smaller than arr[right] can pair with arr[left] to reach target. So we safely advance left.

Similarly, if the sum is too large, no element larger than arr[left] can pair with arr[right] to reach target. So we safely decrease right.

Each step eliminates at least one element from consideration → O(N) total steps.

Complete Trace

Array = [1, 2, 3, 4, 5, 6, 7, 8], target = 9:

State: left=0(1), right=7(8)
  sum = 1+8 = 9 ✓ → print (1,8), left++, right--

State: left=1(2), right=6(7)
  sum = 2+7 = 9 ✓ → print (2,7), left++, right--

State: left=2(3), right=5(6)
  sum = 3+6 = 9 ✓ → print (3,6), left++, right--

State: left=3(4), right=4(5)
  sum = 4+5 = 9 ✓ → print (4,5), left++, right--

State: left=4, right=3 → left >= right, STOP

All pairs: (1,8), (2,7), (3,6), (4,5)

3-Sum Extension

Finding a triplet that sums to target: fix one element, use two pointers for the remaining pair.

// O(N²) — much better than O(N³) brute force
sort(arr.begin(), arr.end());
for (int i = 0; i < n - 2; i++) {
    int left = i + 1, right = n - 1;
    while (left < right) {
        int sum = arr[i] + arr[left] + arr[right];
        if (sum == target) {
            cout << arr[i] << " " << arr[left] << " " << arr[right] << "\n";
            left++; right--;
        } else if (sum < target) left++;
        else right--;
    }
}

3.4.2 Sliding Window — Fixed Size

A sliding window of fixed size K moves across an array, maintaining a running aggregate (sum, max, count of distinct, etc.).

Problem: Find the maximum sum of any contiguous subarray of size K.

Array: [2, 1, 5, 1, 3, 2], K=3
Windows: [2,1,5]=8, [1,5,1]=7, [5,1,3]=9, [1,3,2]=6
Answer: 9

Naïve O(NK): Compute sum from scratch for each window.

Sliding window O(N): Add the new element entering the window, subtract the element leaving.

// Solution: Sliding Window Fixed Size — O(N)
#include <bits/stdc++.h>
using namespace std;

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

    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for (int &x : arr) cin >> x;

    // Compute sum of first window
    long long windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += arr[i];

    long long maxSum = windowSum;

    // Slide the window: add arr[i], remove arr[i-k]
    for (int i = k; i < n; i++) {
        windowSum += arr[i];        // new element enters window
        windowSum -= arr[i - k];   // old element leaves window
        maxSum = max(maxSum, windowSum);
    }

    cout << maxSum << "\n";
    return 0;
}

Trace for [2, 1, 5, 1, 3, 2], K=3:

Initial window [2,1,5]: sum=8, max=8
i=3: add 1, remove 2 → sum=7, max=8
i=4: add 3, remove 1 → sum=9, max=9
i=5: add 2, remove 5 → sum=6, max=9
Answer: 9 ✓

3.4.3 Sliding Window — Variable Size

The most powerful variant: the window expands when we need more, and shrinks when a constraint is violated.

Problem: Find the smallest contiguous subarray with sum ≥ target.

// Solution: Variable Window — O(N)
#include <bits/stdc++.h>
using namespace std;

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

    int n, target;
    cin >> n >> target;
    vector<int> arr(n);
    for (int &x : arr) cin >> x;

    int left = 0;
    long long windowSum = 0;
    int minLen = INT_MAX;

    for (int right = 0; right < n; right++) {
        windowSum += arr[right];   // expand: add right element

        // Shrink window from left while constraint satisfied
        while (windowSum >= target) {
            minLen = min(minLen, right - left + 1);
            windowSum -= arr[left];
            left++;                // shrink: remove left element
        }
    }

    if (minLen == INT_MAX) cout << 0 << "\n";  // no such subarray
    else cout << minLen << "\n";

    return 0;
}

Why O(N)? Each element is added once (when right passes it) and removed at most once (when left passes it). Total operations: O(2N) = O(N).

Problem: Longest Subarray with At Most K Distinct Values

// Variable window: longest subarray with at most K distinct values
int left = 0, maxLen = 0;
map<int, int> freq;  // frequency of each value in window

for (int right = 0; right < n; right++) {
    freq[arr[right]]++;

    // Shrink while we have > k distinct values
    while ((int)freq.size() > k) {
        freq[arr[left]]--;
        if (freq[arr[left]] == 0) freq.erase(arr[left]);
        left++;
    }

    maxLen = max(maxLen, right - left + 1);
}
cout << maxLen << "\n";

3.4.4 USACO Example: Haybale Stacking

Problem (USACO 2012 November Bronze): N haybales in a line. M operations, each adds 1 to all bales in range [a, b]. How many bales have an odd number of additions at the end?

This is actually best solved with a difference array (Chapter 3.2), but a simpler version:

Problem: Given array of integers, find the longest subarray where all elements are ≥ K.

// Two pointer: longest contiguous subarray where all elements >= K
int left = 0, maxLen = 0;
for (int right = 0; right < n; right++) {
    if (arr[right] < K) {
        left = right + 1;  // reset window: current element violates constraint
    } else {
        maxLen = max(maxLen, right - left + 1);
    }
}

⚠️ Common Mistakes

1. Not sorting before two-pointer: The two-pointer technique for pair sum only works on sorted arrays. Without sorting, you'll miss pairs or get wrong answers.
2. Moving both pointers when a pair is found: When you find a matching pair, you must move BOTH left++ AND right--. Moving only one misses some pairs (unless duplicates aren't relevant).
3. Off-by-one in window size: The window [left, right] has size right - left + 1, not right - left.
4. Forgetting to handle empty answer: For the "minimum subarray" problem, initialize minLen = INT_MAX and check if it changed before outputting.

Chapter Summary

📌 Key Takeaways

❓ FAQ

Q1: Does two-pointer always require sorting?

A: Not necessarily. "Opposite-direction two pointers" (like pair sum) require sorting; "same-direction two pointers" (like sliding window) do not. The key is monotonicity — pointers only move in one direction.

Q2: Both sliding window and prefix sum can compute range sums — which to use?

A: For fixed-size window sum/max, sliding window is more intuitive. For arbitrary range queries, prefix sum is more general. Sliding window can only handle "continuously moving windows"; prefix sum can answer any [L,R] query.

Q3: Can sliding window handle both "longest subarray satisfying condition" and "shortest subarray satisfying condition"?

A: Both, but with slightly different logic. "Longest": expand right until condition fails, then shrink left until condition holds again. "Shortest": expand right until condition holds, then shrink left until it no longer holds, recording the minimum length throughout.

Q4: How does two-pointer handle duplicate elements?

A: Depends on the problem. If you want "all distinct pair values", after finding a pair do left++; right-- and skip duplicate values. If you want "count of all pairs", you need to carefully count duplicates (may require extra counting logic).

🔗 Connections to Later Chapters

• Chapter 3.2 (Prefix Sums): prefix sums and sliding window are complementary — prefix sums suit offline queries, sliding window suits online processing
• Chapter 3.3 (Sorting): sorting is a prerequisite for two pointers — opposite-direction two pointers require a sorted array
• Chapter 3.5 (Monotonic): monotonic deque can enhance sliding window — maintaining window min/max in O(N)
• Chapters 6.1–6.3 (DP): some problems (like LIS variants) can be optimized with two pointers

Practice Problems

Problem 3.4.1 — Pair Sum Count 🟢 Easy Given N integers and a target T, count the number of pairs (i < j) with arr[i] + arr[j] = T.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, T; cin >> n >> T;
    vector<int> a(n); for (int& x : a) cin >> x;
    sort(a.begin(), a.end());
    long long cnt = 0;
    int L = 0, R = n - 1;
    while (L < R) {
        int s = a[L] + a[R];
        if (s == T) {
            if (a[L] == a[R]) {
                // all pairs within [L..R] are valid
                long long len = R - L + 1;
                cnt += len * (len - 1) / 2;
                break;
            }
            // count duplicates on both sides
            long long cl = 1, cr = 1;
            while (L+1 < R && a[L+1] == a[L]) { cl++; L++; }
            while (R-1 > L && a[R-1] == a[R]) { cr++; R--; }
            cnt += cl * cr;
            L++; R--;
        } else if (s < T) L++;
        else R--;
    }
    cout << cnt << "\n";
}

Problem 3.4.2 — Maximum Average Subarray 🟡 Medium Find the contiguous subarray of length exactly K with the maximum average.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k; cin >> n >> k;
    vector<double> a(n); for (double& x : a) cin >> x;
    double windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += a[i];
    double maxSum = windowSum;
    for (int i = k; i < n; i++) {
        windowSum += a[i] - a[i-k];  // slide: add new, remove old
        maxSum = max(maxSum, windowSum);
    }
    cout << fixed << setprecision(5) << maxSum / k << "\n";
}

Problem 3.4.3 — Minimum Window Covering 🔴 Hard Given string S and string T, find the shortest substring of S containing all characters of T.

#include <bits/stdc++.h>
using namespace std;
int main() {
    string S, T; cin >> S >> T;
    unordered_map<char,int> need, have;
    for (char c : T) need[c]++;
    int formed = 0, required = need.size();
    int L = 0, minLen = INT_MAX, minL = 0;
    for (int R = 0; R < (int)S.size(); R++) {
        have[S[R]]++;
        if (need.count(S[R]) && have[S[R]] == need[S[R]]) formed++;
        while (formed == required) {  // try to shrink
            if (R - L + 1 < minLen) { minLen = R-L+1; minL = L; }
            have[S[L]]--;
            if (need.count(S[L]) && have[S[L]] < need[S[L]]) formed--;
            L++;
        }
    }
    if (minLen == INT_MAX) cout << "no solution\n";
    else cout << S.substr(minL, minLen) << "\n";
}

🏆 Challenge: USACO 2017 February Bronze — Why Did the Cow Cross the Road Given a grid with cows and their destinations, find which cow can reach its destination fastest. Use two-pointer / greedy on sorted intervals.

Chapter 3.5: Monotonic Stack & Monotonic Queue

📝 Before You Continue: Make sure you're comfortable with two pointers / sliding window (Chapter 3.4) and basic stack/queue operations (Chapter 3.1). This chapter builds directly on those techniques.

Monotonic stacks and queues are elegant tools that solve "nearest greater/smaller element" and "sliding window extremum" problems in O(N) time — problems that would naively require O(N²).

3.5.1 Monotonic Stack: Next Greater Element

Problem: Given an array A of N integers, for each element A[i], find the next greater element (NGE): the index of the first element to the right of i that is greater than A[i]. If none exists, output -1.

Naive approach: O(N²) — for each i, scan right until finding a greater element.

Monotonic stack approach: O(N) — maintain a stack that is always decreasing from bottom to top. When we push a new element, pop all smaller elements first (they just found their NGE!).

💡 Key Insight: The stack contains indices of elements that haven't found their NGE yet. When A[i] arrives, every element in the stack that is smaller than A[i] has found its NGE (it's i!). We pop them and record the answer.

Monotonic stack state changes — step-by-step for A = [2, 1, 5, 6, 2, 3]:

Array A: [2, 1, 5, 6, 2, 3]
         idx: 0  1  2  3  4  5

Processing i=0 (A[0]=2): stack empty → push 0
Stack: [0]          // stack holds indices of unresolved elements

Processing i=1 (A[1]=1): A[1]=1 < A[0]=2 → just push
Stack: [0, 1]

Processing i=2 (A[2]=5): 
  A[2]=5 > A[1]=1 → pop 1, NGE[1] = 2  (A[2]=5 is next greater for A[1])
  A[2]=5 > A[0]=2 → pop 0, NGE[0] = 2  (A[2]=5 is next greater for A[0])
  Stack empty → push 2
Stack: [2]

Processing i=3 (A[3]=6): 
  A[3]=6 > A[2]=5 → pop 2, NGE[2] = 3
  Push 3
Stack: [3]

Processing i=4 (A[4]=2): A[4]=2 < A[3]=6 → just push
Stack: [3, 4]

Processing i=5 (A[5]=3): 
  A[5]=3 > A[4]=2 → pop 4, NGE[4] = 5
  A[5]=3 < A[3]=6 → stop, push 5
Stack: [3, 5]

End: remaining stack [3, 5] → NGE[3] = NGE[5] = -1 (no greater element to the right)

Result: NGE = [2, 2, 3, -1, 5, -1]
Verify: 
  A[0]=2, next greater is A[2]=5 ✓
  A[1]=1, next greater is A[2]=5 ✓
  A[2]=5, next greater is A[3]=6 ✓
  A[3]=6, no greater → -1 ✓

Complete Implementation

// Solution: Next Greater Element using Monotonic Stack — O(N)
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    vector<int> A(n);
    for (int& x : A) cin >> x;

    vector<int> nge(n, -1);   // nge[i] = index of next greater element, -1 if none
    stack<int> st;             // monotonic decreasing stack (stores indices)

    for (int i = 0; i < n; i++) {
        // While the top of stack has a smaller value than A[i]
        // → the current element A[i] is the NGE of all those elements
        while (!st.empty() && A[st.top()] < A[i]) {
            nge[st.top()] = i;  // ← KEY: record NGE for stack top
            st.pop();
        }
        st.push(i);  // push current index (not yet resolved)
    }
    // Remaining elements in stack have no NGE → already initialized to -1

    for (int i = 0; i < n; i++) {
        cout << nge[i];
        if (i < n - 1) cout << " ";
    }
    cout << "\n";

    return 0;
}

Complexity Analysis:

• Each element is pushed exactly once and popped at most once
• Total operations: O(2N) = O(N)
• Space: O(N) for the stack

⚠️ Common Mistake: Storing values instead of indices in the stack. Always store indices — you need to know where in the array to record the answer.

3.5.2 Variations: Previous Smaller, Previous Greater

By changing the comparison direction and the traversal direction, you get four related problems:

Template for Previous Smaller Element:

// Previous Smaller Element: for each i, find the nearest j < i where A[j] < A[i]
vector<int> pse(n, -1);  // pse[i] = index of previous smaller, -1 if none
stack<int> st;

for (int i = 0; i < n; i++) {
    while (!st.empty() && A[st.top()] >= A[i]) {
        st.pop();  // pop elements that are >= A[i] (not the "previous smaller")
    }
    pse[i] = st.empty() ? -1 : st.top();  // stack top is the previous smaller
    st.push(i);
}

3.5.3 USACO Application: Largest Rectangle in Histogram

Problem: Given an array of heights H[0..N-1], find the area of the largest rectangle that fits under the histogram.

Key insight: For each bar i, the largest rectangle with height H[i] extends left and right until it hits a shorter bar. Use monotonic stack to find, for each i:

• left[i] = previous smaller element index
• right[i] = next smaller element index

Left/right boundaries for each bar — H = [2, 1, 5, 6, 2, 3]:

💡 Formula: width = right[i] - left[i] - 1, area = H[i] × width. Left boundary = index of previous smaller element; right boundary = index of next smaller element.

// Solution: Largest Rectangle in Histogram — O(N)
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    vector<int> H(n);
    for (int& h : H) cin >> h;

    // Find previous smaller for each position
    vector<int> left(n), right(n);
    stack<int> st;

    // Previous smaller (left boundary)
    for (int i = 0; i < n; i++) {
        while (!st.empty() && H[st.top()] >= H[i]) st.pop();
        left[i] = st.empty() ? -1 : st.top();  // index before rectangle starts
        st.push(i);
    }

    while (!st.empty()) st.pop();

    // Next smaller (right boundary)
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && H[st.top()] >= H[i]) st.pop();
        right[i] = st.empty() ? n : st.top();  // index after rectangle ends
        st.push(i);
    }

    // Compute maximum area
    long long maxArea = 0;
    for (int i = 0; i < n; i++) {
        long long width = right[i] - left[i] - 1;  // width of rectangle
        long long area = (long long)H[i] * width;
        maxArea = max(maxArea, area);
    }

    cout << maxArea << "\n";
    return 0;
}

Trace for H = [2, 1, 5, 6, 2, 3]:

left  = [-1, -1, 1, 2, 1, 4]   (index of previous smaller, -1 = none)
right = [1, 6, 4, 4, 6, 6]     (index of next smaller, n=6 = none)

Widths:  1-(-1)-1=1, 6-(-1)-1=6, 4-1-1=2, 4-2-1=1, 6-1-1=4, 6-4-1=1
Areas:   2×1=2, 1×6=6, 5×2=10, 6×1=6, 2×4=8, 3×1=3

Maximum area = 10
  i=2: H[2]=5, left[2]=1, right[2]=4, width=4-1-1=2, area=5×2=10 ✓
  (bars at indices 2 and 3 both have height ≥ 5, so the rectangle of height 5 spans width 2)

📌 Note for Students: Always trace through your algorithm on the sample input before submitting. Small off-by-one errors in index boundary calculations are the #1 source of bugs in monotonic stack problems.

3.5.4 Monotonic Deque: Sliding Window Maximum

Problem: Given array A of N integers and window size K, find the maximum value in each window of size K as it slides from left to right. Output N-K+1 values.

Naive approach: O(NK) — scan each window for its maximum.

Monotonic deque approach: O(N) — maintain a decreasing deque (front = maximum of current window).

💡 Key Insight: We want the maximum in a sliding window. We maintain a deque of indices such that:

1. The deque is decreasing in value (front is always the maximum)
2. The deque only contains indices within the current window

When a new element arrives:

• Remove all smaller elements from the back (they can never be the maximum while this new element is in the window)
• Remove the front if it's outside the current window

Step-by-Step Trace

Array A: [1, 3, -1, -3, 5, 3, 6, 7], K = 3

Window [1,3,-1]: max = 3
Window [3,-1,-3]: max = 3
Window [-1,-3,5]: max = 5
Window [-3,5,3]: max = 5
Window [5,3,6]: max = 6
Window [3,6,7]: max = 7

i=0, A[0]=1: deque=[0]
i=1, A[1]=3: 3>1 → pop 0; deque=[1]
i=2, A[2]=-1: -1<3 → push; deque=[1,2]; window [0..2]: max=A[1]=3 ✓
i=3, A[3]=-3: -3<-1 → push; deque=[1,2,3]; window [1..3]: front=1 still in window, max=A[1]=3 ✓
i=4, A[4]=5: 5>-3→pop 3; 5>-1→pop 2; 5>3→pop 1; deque=[4]; window [2..4]: max=A[4]=5 ✓
i=5, A[5]=3: 3<5→push; deque=[4,5]; window [3..5]: front=4 in window, max=A[4]=5 ✓
i=6, A[6]=6: 6>3→pop 5; 6>5→pop 4; deque=[6]; window [4..6]: max=A[6]=6 ✓
i=7, A[7]=7: 7>6→pop 6; deque=[7]; window [5..7]: max=A[7]=7 ✓

Complete Implementation

// Solution: Sliding Window Maximum using Monotonic Deque — O(N)
#include <bits/stdc++.h>
using namespace std;

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

    int n, k;
    cin >> n >> k;
    vector<int> A(n);
    for (int& x : A) cin >> x;

    deque<int> dq;   // monotonic decreasing deque, stores indices
    vector<int> result;

    for (int i = 0; i < n; i++) {
        // 1. Remove elements outside the current window
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();   // ← KEY: expired window front
        }

        // 2. Maintain decreasing property
        //    Remove from back all elements smaller than A[i]
        //    (they'll never be the max while A[i] is in the window)
        while (!dq.empty() && A[dq.back()] <= A[i]) {
            dq.pop_back();    // ← KEY: pop smaller elements from back
        }

        dq.push_back(i);   // add current element

        // 3. Record maximum once first full window is formed
        if (i >= k - 1) {
            result.push_back(A[dq.front()]);  // front = maximum of current window
        }
    }

    for (int i = 0; i < (int)result.size(); i++) {
        cout << result[i];
        if (i + 1 < (int)result.size()) cout << "\n";
    }
    cout << "\n";

    return 0;
}

Complexity:

• Each element is pushed/popped from the deque at most once → O(N) total
• Space: O(K) for the deque

⚠️ Common Mistake #1: Forgetting to check dq.front() <= i - k for window expiration. The deque must only contain indices in [i-k+1, i].

⚠️ Common Mistake #2: Using < instead of <= when popping from the back. With <, equal elements are preserved, but duplicates can cause issues. Use <= to maintain strict decreasing deque.

3.5.5 USACO Problem: Haybale Stacking (Monotonic Stack)

🔗 Inspiration: This problem type appears in USACO Bronze/Silver ("Haybale Stacking" style).

Problem: There are N positions on a number line. You have K operations: each operation sets all positions in [L, R] to 1. After all operations, output 1 for each position that was set, 0 otherwise.

Solution: Difference array (Chapter 3.2). But let's see a harder variant:

Harder Variant: Given an array H of N "heights," find for each position i the leftmost j such that H[j] < H[i] for all k in [j+1, i-1]. (Find the span of each bar in a histogram.)

This is exactly the "stock span problem" and solves using a monotonic stack — identical to the previous smaller element pattern.

// Stock Span Problem: for each day i, find how many consecutive days
// before i had price <= price[i]
// (the "span" of day i)
vector<int> stockSpan(vector<int>& prices) {
    int n = prices.size();
    vector<int> span(n, 1);
    stack<int> st;  // monotonic decreasing stack of indices

    for (int i = 0; i < n; i++) {
        while (!st.empty() && prices[st.top()] <= prices[i]) {
            st.pop();
        }
        span[i] = st.empty() ? (i + 1) : (i - st.top());
        st.push(i);
    }
    return span;
}
// span[i] = number of consecutive days up to and including i with price <= prices[i]

3.5.6 USACO-Style Problem: Barn Painting Temperatures

Problem: N readings, find the maximum value in each window of size K.

(This is the sliding window maximum — solution already shown in 3.5.4.)

A trickier USACO variant: Given N cows in a line, each with temperature T[i]. A "fever cluster" is a maximal contiguous subarray where all temperatures are above threshold X. Find the maximum cluster size for each of Q threshold queries.

Offline approach: Sort queries by X, process with monotonic deque.

⚠️ Common Mistakes in Chapter 3.5

1. Storing values instead of indices — Always store indices. You need them to check window bounds and to record answers.

2. Wrong comparison in deque (< vs <=) — For sliding window MAXIMUM, pop when A[dq.back()] <= A[i] (strict non-increase). For MINIMUM, pop when A[dq.back()] >= A[i].

3. Forgetting window expiration — In sliding window deque, always check dq.front() < i - k + 1 (or <= i - k) before recording the maximum.

4. Stack bottom-top direction confusion — The "monotonic" property means: bottom-to-top, the stack is increasing (for NGE) or decreasing (for NSE). Draw it out if confused.

5. Processing order for NGE vs PSE:

   • Next Greater Element: left-to-right traversal
   • Previous Greater Element: right-to-left traversal (OR: left-to-right, record stack.top() before pushing)

Chapter Summary

📌 Key Summary