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

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.

Classic CF Problems


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

Example

Problem: Minimum operations to make binary string alternating.

Classic CF Problems


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.

Computing MEX

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


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:

Classic CF Problems


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

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


Type 6: Counting / Combinatorics

What It Is

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

Key Formulas

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


Type 7: Interval / Range Problems

What It Is

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

Key Techniques

Classic CF Problems


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

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

Classic CF Problems


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


Quick Recognition Guide


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.