Skip to main content

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

1

Find Necessary Conditions

What must be true for a solution to exist?
2

Check Impossibility

If conditions fail, print -1 or NO.
3

Construct Greedily

Build the simplest valid answer.

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.
// MEX examples:
// MEX({0, 1, 2}) = 3
// MEX({0, 2, 3}) = 1
// MEX({1, 2, 3}) = 0
// MEX({}) = 0

Computing MEX

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 array
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;
}

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

// Sum of permutation = n*(n+1)/2
// XOR depends on n

// Finding missing element
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
vector<bool> visited(n + 1, false);
for (int i = 1; i <= n; i++) {
    if (!visited[i]) {
        int j = i;
        while (!visited[j]) {
            visited[j] = true;
            j = p[j];
        }
    }
}

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?

Key Patterns

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

// Parity trick
// If total moves is odd, first player wins
// If even, second player wins

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

Classic Insights

  1. Nim: XOR of pile sizes
  2. Sprague-Grundy: Every game position has a Grundy number
  3. Parity: Count total moves
  4. Symmetry: Copy opponent’s moves

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;

// Factorial and inverse
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;
    inv_fact[N-1] = power(fact[N-1], MOD - 2);
    for (int i = N-2; i >= 0; i--)
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
}

// nCr = n! / (r! * (n-r)!)
long long C(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD;
}

// Power function
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;
}

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!
cout << "? " << query << endl;  // endl flushes

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

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

// Submit final answer
cout << "! " << answer << endl;

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