Skip to main content

Documentation Index

Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt

Use this file to discover all available pages before exploring further.

Codeforces Problem Types

Problems LeetCode Doesn’t Prepare You For

LeetCode focuses on specific data structures and algorithms. Codeforces has its own flavor of problems that can feel alien at first.

Type 1: Construction Problems

What It Is

Given constraints, construct an array/string/sequence that satisfies them—or report impossible.

Example Pattern

“Construct an array of n integers where sum is S and maximum element is M, or print -1 if impossible.”

How to Approach

Construction problems reward laziness---build the simplest possible valid output, not the cleverest. The judge does not give bonus points for elegance.
1

Find Necessary Conditions

What must be true for a solution to exist? For example: “sum must be at least n” or “max element must not exceed X.”
2

Check Impossibility

If conditions fail, print -1 or NO. Be thorough---missing an impossibility condition is the #1 WA cause on construction problems.
3

Construct Greedily

Build the simplest valid answer. Start with a “base” configuration (all 1s, all 0s, sorted order) and adjust minimally to satisfy constraints.
Contest Tip: When constructing, start by assigning the minimum possible value to every position, then distribute the remaining “budget” to one or two positions. This greedy baseline handles most construction problems at the 800-1400 level.

Example

Problem: Construct an array of n positive integers with sum S.
void solve() {
    int n, s;
    cin >> n >> s;
    
    // Necessary: minimum sum is n (all 1s)
    if (s < n) {
        cout << -1 << "\n";
        return;
    }
    
    // Construction: all 1s, then put remainder in first element
    for (int i = 0; i < n; i++) {
        if (i == 0) cout << s - (n - 1);
        else cout << 1;
        cout << " \n"[i == n - 1];
    }
}

Classic CF Problems

ProblemKey Insight
CF 1352DConstruct array with given conditions
CF 1367CConstruct balanced string
CF 1352CSplit n into k distinct summands

Type 2: Binary String Problems

What It Is

Operations on binary strings (0s and 1s) with specific rules.

Common Operations

  • Flip a character
  • Swap adjacent characters
  • Remove/add characters
  • Make all characters same

Key Observations

// Count transitions (places where adjacent chars differ)
int transitions = 0;
for (int i = 1; i < n; i++) {
    if (s[i] != s[i-1]) transitions++;
}

// Blocks of consecutive same characters
// "00110" has 3 blocks: "00", "11", "0"

// Parity often matters
int zeros = count(s.begin(), s.end(), '0');
int ones = n - zeros;

Example

Problem: Minimum operations to make binary string alternating.
int solve(string s) {
    int n = s.size();
    // Two targets: "010101..." or "101010..."
    int cost1 = 0, cost2 = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] != ('0' + i % 2)) cost1++;
        if (s[i] != ('1' - i % 2)) cost2++;
    }
    return min(cost1, cost2);
}

Classic CF Problems

ProblemKey Insight
CF 1505ABinary string operations
CF 1379AAlternating subsequence
CF 1353CBoard moves

Type 3: MEX Problems

What It Is

MEX = Minimum EXcludant = Smallest non-negative integer NOT in a set. Think of it like numbering seats in a theater. If seats 0, 1, and 2 are taken, the MEX is 3---the first empty seat. If seats 0, 2, and 3 are taken, the MEX is 1---it finds the gap. MEX problems appear constantly on Codeforces (especially Div 3/4) because they combine simple definitions with tricky observations.
// MEX examples:
// MEX({0, 1, 2}) = 3   -- all seats 0-2 taken, first gap is 3
// MEX({0, 2, 3}) = 1   -- seat 1 is missing
// MEX({1, 2, 3}) = 0   -- seat 0 is missing
// MEX({}) = 0           -- nothing taken, first gap is 0

Computing MEX

// O(n log n) version using set -- simple but has log factor
int mex(vector<int>& arr) {
    set<int> s(arr.begin(), arr.end());
    int m = 0;
    while (s.count(m)) m++;
    return m;
}

// O(n) version using boolean array -- preferred in contests
// Key insight: MEX of n elements is at most n, so we only need
// a boolean array of size n+1. Any value > n cannot affect MEX.
int mex(vector<int>& arr, int n) {
    vector<bool> present(n + 1, false);
    for (int x : arr) {
        if (x >= 0 && x <= n) present[x] = true;
    }
    for (int i = 0; i <= n; i++) {
        if (!present[i]) return i;
    }
    return n + 1;
}
Contest Tip: When you see a MEX problem, the first thing to ask is: “What happens when I add or remove a single element?” MEX can only change by at most 1 in predictable ways. Many MEX problems are solved by maintaining a frequency array and tracking where the gap is.

Classic CF Problems

ProblemKey Insight
CF 1406ASubstring MEX
CF 1375DMEX transformations
CF 1436CBinary search + MEX

Type 4: Permutation Problems

What It Is

An array of n elements containing each number from 1 to n exactly once.

Key Properties

Permutations have rich structure that makes seemingly hard problems tractable. The most important properties to remember:
// Sum of permutation = n*(n+1)/2 (always, regardless of order)
// This means: if you know the sum and one element is missing, subtraction finds it.

// Finding missing element in O(n) time, O(1) space
int missing = n * (n + 1) / 2 - sum;

// Inverse permutation: p[q[i]] = i
vector<int> inv(n + 1);
for (int i = 1; i <= n; i++) {
    inv[p[i]] = i;
}

// Cycle decomposition: follow where each element "wants to go"
// Every permutation decomposes into disjoint cycles.
// Example: p = [2, 3, 1, 5, 4] has cycles (1->2->3->1) and (4->5->4)
// Key insight: minimum swaps to sort a permutation = n - (number of cycles)
vector<bool> visited(n + 1, false);
int numCycles = 0;
for (int i = 1; i <= n; i++) {
    if (!visited[i]) {
        numCycles++;
        int j = i;
        while (!visited[j]) {
            visited[j] = true;
            j = p[j];  // Follow the permutation
        }
    }
}
// Minimum swaps to sort = n - numCycles

Classic CF Problems

ProblemKey Insight
CF 1256DPermutation swaps
CF 1385CMake increasing with swaps
CF 1462DAdd to permutation

Type 5: Game Theory / Turn-Based

What It Is

Alice and Bob take turns. Who wins with optimal play? These problems look intimidating but most Codeforces game theory problems (rated 800-1600) boil down to one of three tricks: parity, XOR, or symmetry. You almost never need full Sprague-Grundy theory at these levels.

Key Patterns

// XOR trick (Nim Game)
// If XOR of all piles is 0, second player wins
// Otherwise, first player wins

// Parity trick -- the most common pattern at Div 3/4 level
// If total moves is odd, first player wins
// If even, second player wins
// Example: 5 stones, remove 1 per turn. 5 is odd -> first player wins.

// Greedy games
// First player takes optimal choice each turn

Classic Insights

  1. Nim: XOR of pile sizes. If XOR = 0, the position is losing for the player whose turn it is. Think of XOR as a “balance indicator”---when piles are “balanced” in binary, the current player cannot break the balance without the opponent restoring it.
  2. Sprague-Grundy: Every game position has a Grundy number (advanced, rarely needed below 1800 rating)
  3. Parity: Count total moves. If total is odd, first player makes the last move and wins.
  4. Symmetry: Copy opponent’s moves. If first player can always mirror what second player does, first player wins.
Contest Tip: When you see “Alice and Bob,” immediately check parity. Count the total number of moves in the game. If it is fixed regardless of strategy, the answer depends only on whether the count is odd or even. This solves about 60% of game theory problems on Codeforces.

Classic CF Problems

ProblemKey Insight
CF 1527BParity game
CF 1538EGame with removing
CF 1451CString game

Type 6: Counting / Combinatorics

What It Is

Count arrangements, combinations, or ways to achieve something, often modulo 10^9+7.

Key Formulas

const int MOD = 1e9 + 7;

// Power function (binary exponentiation) -- needed for modular inverse
// Computes base^exp mod MOD in O(log exp) time
long long power(long long base, long long exp) {
    long long result = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) result = result * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return result;
}

// Precompute factorials and their modular inverses
// This allows O(1) nCr queries after O(N) preprocessing
vector<long long> fact(N), inv_fact(N);
void precompute() {
    fact[0] = 1;
    for (int i = 1; i < N; i++)
        fact[i] = fact[i-1] * i % MOD;
    // Compute inverse of largest factorial, then work backwards
    // inv_fact[i] = 1 / i! mod MOD
    inv_fact[N-1] = power(fact[N-1], MOD - 2);  // Fermat's little theorem
    for (int i = N-2; i >= 0; i--)
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
}

// nCr = n! / (r! * (n-r)!) mod MOD
long long C(int n, int r) {
    if (r < 0 || r > n) return 0;  // Guard against invalid inputs
    return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD;
}
Common Mistake: Forgetting to call precompute() before using C(). Place the call at the top of main() or in a global initializer. Also, make sure N is large enough for the maximum value of n in the problem---off-by-one here causes out-of-bounds access with no helpful error message.

Classic CF Problems

ProblemKey Insight
CF 1312DCount arrays
CF 1462EClose elements
CF 1409DDecreasing string

Type 7: Interval / Range Problems

What It Is

Problems involving segments [l, r] on a number line.

Key Techniques

// Sorting by end point for interval scheduling
sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
    return a.second < b.second;
});

// Difference array for range updates
// Add +d to [l, r]:
diff[l] += d;
diff[r + 1] -= d;

// Sweep line
// Process events in sorted order
sort(events.begin(), events.end());
int current = 0;
for (auto& [pos, type] : events) {
    current += type;  // +1 for start, -1 for end
    // current = number of active intervals at pos
}

Classic CF Problems

ProblemKey Insight
CF 1389ALCM in range
CF 1399CMinimum window
CF 1430DString segments

Type 8: Interactive Problems

What It Is

Your program asks queries, the judge responds, and you find the answer within a query limit.

Key Rules

// Always flush output after every query!
// Without flushing, your query sits in a buffer and the judge never sees it.
// Your program then waits for a response that never comes -> TLE.
cout << "? " << query << endl;  // endl flushes automatically

// Or use explicit flush:
cout << "? " << query << "\n" << flush;

// Read response
int response;
cin >> response;

// If response is -1, the judge is telling you something went wrong
// (too many queries, invalid query, etc.) -- exit immediately
if (response == -1) exit(0);

// Submit final answer
cout << "! " << answer << endl;
The #1 Interactive Problem Mistake: Forgetting to flush. Without flushing, your output sits in an internal buffer. The judge never receives your query, so it never sends a response. Your program hangs waiting for input, and you get TLE. This looks identical to a slow solution, which makes it very confusing to debug. Always use endl or flush after every query.

Common Patterns

  1. Binary Search: Query middle, narrow range
  2. Comparison Queries: “Is A > B?”
  3. Subset Queries: “What is f(subset)?”

Example: Binary Search Interactive

int lo = 1, hi = n;
while (lo < hi) {
    int mid = (lo + hi) / 2;
    cout << "? " << mid << endl;
    int response;
    cin >> response;
    if (response == 1) hi = mid;
    else lo = mid + 1;
}
cout << "! " << lo << endl;

Classic CF Problems

ProblemKey Insight
CF 1520DBinary search
CF 1486CTernary search
CF 1451DCircle game

Type 9: Ad-Hoc / Observation

What It Is

Problems that require a clever observation rather than standard algorithms.

How to Approach

1

Try Small Cases

Work through n=1, 2, 3, 4 by hand.
2

Look for Patterns

Does a formula emerge? Parity? Special structure?
3

Simplify the Problem

What’s the simplest version of this problem?
4

Think About Necessary Conditions

What must be true for a solution to exist?

Red Flags for Ad-Hoc

  • Problem seems “too simple” for its rating
  • Constraints are unusual (very small or very specific)
  • Problem involves specific numerical properties
  • Standard algorithms don’t obviously apply

Classic CF Problems

ProblemKey Insight
CF 1474AParity puzzle
CF 1454BUnique elements
CF 1426AFloor division

Quick Recognition Guide

See ThisThink This
”Construct array…”Construction problem
Binary string, 0s and 1sBinary string manipulation
MEX, mex, minimum excludantMEX techniques
”Permutation of 1 to n”Permutation properties
”Alice and Bob”Game theory
”Count the number”Combinatorics
”In range [l, r]“Interval techniques
”Query” + output flushInteractive
Nothing standard appliesAd-hoc observation

Practice by Type

Solve 5-10 problems of each type to build recognition:
  1. Construction: Filter by “constructive algorithms” tag
  2. Binary String: Search for binary string in recent problems
  3. MEX: Filter by “games” + MEX keyword
  4. Permutation: Filter by “math” + permutation keyword
  5. Game Theory: Filter by “games” tag
  6. Counting: Filter by “combinatorics” tag
  7. Interactive: Filter by “interactive” tag

Next Steps

8-Week Roadmap

Follow a structured practice plan.

CF Survival Guide

Learn the Codeforces platform basics.

Interview Deep-Dive

Strong Answer:
  • First identify impossibility: minimum sum with n positive integers is n (all 1s), but adjacency constraint means I need at least alternating 1s and 2s. For even n, base sum is 1.5n. For odd n, base sum is ceil(n/2) + floor(n/2)*2 or similar. If S is below the minimum achievable, output -1.
  • Construction: start with alternating [1, 2, 1, 2, …]. Compute remaining budget = S - base_sum. Add the entire surplus to one element (e.g., the first), ensuring it remains different from its neighbor. If the first element becomes equal to its neighbor after adding, add to a different position.
  • Edge cases: n=1 (just output S), S=n (all 1s, but adjacent equality — need 1,2,1,2 pattern which requires S >= 1.5n roughly).
  • Complexity: O(n) to build the array. Construction problems are about correctness of the invariant, not algorithmic complexity.
Follow-up: How do you prove your construction is always valid when it does not report impossible?I verify the two invariants: (1) all elements are positive — the base uses 1s and 2s (positive), and adding surplus only increases values, so positivity holds. (2) No two adjacent elements are equal — the base alternates 1 and 2. Adding surplus to one position changes only that element. As long as the modified element differs from both neighbors (which it will since it increased and its neighbors stayed at 1 or 2), the invariant holds. Edge case: if surplus makes an element equal to a neighbor, redistribute to a non-conflicting position.
Strong Answer:
  • MEX is the smallest non-negative integer absent from a set. Static computation is O(n): boolean array of size n+1, mark present values, scan for first gap.
  • For dynamic updates, maintain a frequency array and a sorted set of “gaps” (missing values below the current MEX). On insert(x): if x was missing and below MEX, remove x from gaps; if gaps is empty, MEX increases (scan forward). On delete(x): if x < MEX, add x to gaps and MEX drops to min(gaps).
  • Using an ordered set for gaps gives O(log n) per operation. For most contest constraints, a simple approach with a frequency array and a global pointer that lazily advances works in O(1) amortized.
Follow-up: A problem asks you to split an array into two parts maximizing MEX(part1) + MEX(part2). What is your approach?Compute global MEX = M. For values 0 to M-1, count frequencies. Every value appearing 2+ times can contribute to both parts’ MEX. The bottleneck is the smallest value with frequency exactly 1 — it can only appear in one part, so the other part’s MEX stops there. The answer is M + (smallest value with freq=1), or 2M if all values 0..M-1 appear at least twice. O(n) time.
Strong Answer:
  • Step 1: If total moves is fixed, the answer is pure parity. Odd total = first player wins. This covers 60% of contest game problems.
  • Step 2: If the game decomposes into independent sub-games, apply Sprague-Grundy. Compute Grundy number for each sub-game, XOR them all. XOR = 0 means second player wins.
  • Step 3: For complex games, simulate small cases (n=1 through 5), classify each as W (first player wins) or L, and look for a pattern — often a simple modular condition emerges.
  • Step 4: For non-standard games, model as a directed graph of game states. A state is losing if all moves lead to winning states. A state is winning if any move leads to a losing state. Compute via BFS/DFS from terminal states.
Follow-up: When do you need full Sprague-Grundy versus just parity or Nim XOR?Full Sprague-Grundy is needed when move sets are non-standard (e.g., “remove 1, 3, or 4 stones” instead of “remove 1 to k”), or when the game is a sum of heterogeneous sub-games. Below rating 1800, parity and basic Nim XOR cover almost everything. Above 1800, you occasionally compute Grundy numbers via memoized search over game states.