> ## 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.

# CF Problem Types

> Recognize and solve the most common Codeforces problem types—what LeetCode doesn't teach you

# 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.

<Steps>
  <Step title="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."
  </Step>

  <Step title="Check Impossibility">
    If conditions fail, print -1 or NO. Be thorough---missing an impossibility condition is the #1 WA cause on construction problems.
  </Step>

  <Step title="Construct Greedily">
    Build the simplest valid answer. Start with a "base" configuration (all 1s, all 0s, sorted order) and adjust minimally to satisfy constraints.
  </Step>
</Steps>

<Tip>
  **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.
</Tip>

### Example

**Problem**: Construct an array of n positive integers with sum S.

```cpp theme={null}
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

| Problem                                                      | Key Insight                           |
| ------------------------------------------------------------ | ------------------------------------- |
| [CF 1352D](https://codeforces.com/problemset/problem/1352/D) | Construct array with given conditions |
| [CF 1367C](https://codeforces.com/problemset/problem/1367/C) | Construct balanced string             |
| [CF 1352C](https://codeforces.com/problemset/problem/1352/C) | Split 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

```cpp theme={null}
// 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.

```cpp theme={null}
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

| Problem                                                      | Key Insight              |
| ------------------------------------------------------------ | ------------------------ |
| [CF 1505A](https://codeforces.com/problemset/problem/1505/A) | Binary string operations |
| [CF 1379A](https://codeforces.com/problemset/problem/1379/A) | Alternating subsequence  |
| [CF 1353C](https://codeforces.com/problemset/problem/1353/C) | Board 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.

```cpp theme={null}
// 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

```cpp theme={null}
// 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;
}
```

<Tip>
  **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.
</Tip>

### Classic CF Problems

| Problem                                                      | Key Insight         |
| ------------------------------------------------------------ | ------------------- |
| [CF 1406A](https://codeforces.com/problemset/problem/1406/A) | Substring MEX       |
| [CF 1375D](https://codeforces.com/problemset/problem/1375/D) | MEX transformations |
| [CF 1436C](https://codeforces.com/problemset/problem/1436/C) | Binary 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:

```cpp theme={null}
// 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

| Problem                                                      | Key Insight                |
| ------------------------------------------------------------ | -------------------------- |
| [CF 1256D](https://codeforces.com/problemset/problem/1256/D) | Permutation swaps          |
| [CF 1385C](https://codeforces.com/problemset/problem/1385/C) | Make increasing with swaps |
| [CF 1462D](https://codeforces.com/problemset/problem/1462/D) | Add 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

```cpp theme={null}
// 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.

<Tip>
  **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.
</Tip>

### Classic CF Problems

| Problem                                                      | Key Insight        |
| ------------------------------------------------------------ | ------------------ |
| [CF 1527B](https://codeforces.com/problemset/problem/1527/B) | Parity game        |
| [CF 1538E](https://codeforces.com/problemset/problem/1538/E) | Game with removing |
| [CF 1451C](https://codeforces.com/problemset/problem/1451/C) | String game        |

***

## Type 6: Counting / Combinatorics

### What It Is

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

### Key Formulas

```cpp theme={null}
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;
}
```

<Warning>
  **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.
</Warning>

### Classic CF Problems

| Problem                                                      | Key Insight       |
| ------------------------------------------------------------ | ----------------- |
| [CF 1312D](https://codeforces.com/problemset/problem/1312/D) | Count arrays      |
| [CF 1462E](https://codeforces.com/problemset/problem/1462/E) | Close elements    |
| [CF 1409D](https://codeforces.com/problemset/problem/1409/D) | Decreasing string |

***

## Type 7: Interval / Range Problems

### What It Is

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

### Key Techniques

```cpp theme={null}
// 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

| Problem                                                      | Key Insight     |
| ------------------------------------------------------------ | --------------- |
| [CF 1389A](https://codeforces.com/problemset/problem/1389/A) | LCM in range    |
| [CF 1399C](https://codeforces.com/problemset/problem/1399/C) | Minimum window  |
| [CF 1430D](https://codeforces.com/problemset/problem/1430/D) | String 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

```cpp theme={null}
// 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;
```

<Warning>
  **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.
</Warning>

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

```cpp theme={null}
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

| Problem                                                      | Key Insight    |
| ------------------------------------------------------------ | -------------- |
| [CF 1520D](https://codeforces.com/problemset/problem/1520/D) | Binary search  |
| [CF 1486C](https://codeforces.com/problemset/problem/1486/C) | Ternary search |
| [CF 1451D](https://codeforces.com/problemset/problem/1451/D) | Circle game    |

***

## Type 9: Ad-Hoc / Observation

### What It Is

Problems that require a clever observation rather than standard algorithms.

### How to Approach

<Steps>
  <Step title="Try Small Cases">
    Work through n=1, 2, 3, 4 by hand.
  </Step>

  <Step title="Look for Patterns">
    Does a formula emerge? Parity? Special structure?
  </Step>

  <Step title="Simplify the Problem">
    What's the simplest version of this problem?
  </Step>

  <Step title="Think About Necessary Conditions">
    What must be true for a solution to exist?
  </Step>
</Steps>

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

| Problem                                                      | Key Insight     |
| ------------------------------------------------------------ | --------------- |
| [CF 1474A](https://codeforces.com/problemset/problem/1474/A) | Parity puzzle   |
| [CF 1454B](https://codeforces.com/problemset/problem/1454/B) | Unique elements |
| [CF 1426A](https://codeforces.com/problemset/problem/1426/A) | Floor division  |

***

## Quick Recognition Guide

| See This                    | Think This                 |
| --------------------------- | -------------------------- |
| "Construct array..."        | Construction problem       |
| Binary string, 0s and 1s    | Binary string manipulation |
| MEX, mex, minimum excludant | MEX 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 flush      | Interactive                |
| Nothing standard applies    | Ad-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

<CardGroup cols={2}>
  <Card title="8-Week Roadmap" icon="calendar" href="/courses/competitive-programming/01a-8-week-roadmap">
    Follow a structured practice plan.
  </Card>

  <Card title="CF Survival Guide" icon="shield" href="/courses/competitive-programming/01b-cf-guide">
    Learn the Codeforces platform basics.
  </Card>
</CardGroup>

***

## Interview Deep-Dive

<AccordionGroup>
  <Accordion title="Construct an array of n positive integers with sum S where no two adjacent elements are equal, or report impossible. Walk through your approach and complexity.">
    **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.
  </Accordion>

  <Accordion title="Explain the MEX operation and how you would maintain it efficiently under dynamic insertions and deletions.">
    **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.
  </Accordion>

  <Accordion title="Alice and Bob play a game removing elements from an array. How do you determine the winner in general, and what is your systematic framework?">
    **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.
  </Accordion>
</AccordionGroup>