Skip to content
Tutorials Center
My learning

Topics

Lesson 2 of 63 ยท Getting Started with Contests

Reading a Problem Statement

Learn to read competitive programming statements: input and output format, constraints as hints, mapping n to the needed complexity, samples, and hidden traps.

Most wrong submissions in the first months of contests do not come from weak algorithms. They come from misreading the problem: a missed word, an ignored constraint, a sample that was never traced by hand. Reading is a skill, and it is the cheapest one to improve. A careful two-minute read often saves twenty minutes of debugging.

This lesson takes a statement apart piece by piece, shows how the constraints tell you which algorithm is allowed, and gives you a small helper that maps input sizes to complexity classes. After the introduction to contests, this is the first real tool.

The anatomy of a statement

Almost every statement has the same parts, in roughly this order.

  1. Legend. A short story (cows, trains, a king with coins). It is decoration; strip it away and restate the task in abstract terms: "given an array, find ...".
  2. Task. The precise question. Underline the verb: count, find any, minimise, print "YES" or "NO".
  3. Input format. How many tests, what each line contains, the order of the numbers.
  4. Output format. What to print and in what shape. Often "print any valid answer" or "print the answer modulo 1 000 000 007".
  5. Constraints. Ranges of every variable, such as 1 <= n <= 200000 and |a_i| <= 10^9.
  6. Samples and notes. Small example inputs and outputs, sometimes with an explanation of the first one.
flowchart TD
    S["Statement"] --> L["Legend: strip the story"]
    S --> T["Task: count, find, minimise, decide?"]
    S --> I["Input and output format"]
    S --> C["Constraints"]
    S --> X["Samples"]
    C --> A["Choose the complexity budget"]
    T --> A
    A --> P["Plan an algorithm"]
    X --> V["Trace by hand to confirm understanding"]

Read all parts; the constraints and the task together decide which algorithm you may use.

Restate the problem

Before thinking about solutions, write the problem in one sentence of your own, using variables. A tiny example:

"Alice has n coins with values a_1, ..., a_n. She wants to split them into two piles so that the difference of the sums is as small as possible. Print that difference."

Restated: given an array, partition it into two subsets, minimise |sum(A) - sum(B)|. Now it is recognisable as a known problem. The restatement step also exposes what you do not understand: if you cannot restate it, reread.

Constraints are hints

The limits on the input are not formalities. They tell you the intended complexity, because the problem setters chose them so that the intended solution passes and slower ones do not.

A rough rule for a judge running compiled code: about 10^8 simple operations per second. Python is much slower, often 10^6 to 10^7 simple operations per second, so you aim for smaller exponents or use built-in functions that run in C. The table below gives the classic mapping for the maximum n and the complexity the setters probably intended.

Largest n Probable intended complexity Typical idea
up to about 10 O(n!) try all permutations
up to about 20 to 25 O(2^n) or O(2^n * n) subsets, bitmask
up to about 40 O(2^(n/2)) meet in the middle
up to about 500 O(n^3) triple loops, Floyd-Warshall
up to about 5,000 O(n^2) double loops, 2D DP
up to about 10^5 to 10^6 O(n log n) sorting, heaps, binary search, segment tree
up to about 10^7 O(n) one pass, sieve
up to 10^18 O(log n) or O(sqrt n) with care math, binary search, fast exponentiation

Read it like a detective. If n <= 200000 and the obvious solution compares all pairs (O(n^2) is 4 * 10^10), then the obvious solution is wrong by design: look for sorting, a hash map, two pointers or a prefix sum. If n <= 18, the setters want exponential work, so brute force over subsets is the plan, not a mistake. Other hints: a small k (say 20) next to a large n often means O(n * k) or a bit trick; a modulus such as 10^9+7 means the answer is huge and needs modular arithmetic.

Do the arithmetic before you code. This helper turns a maximum n into the largest complexity classes that fit a budget of operations.

Python From constraints to complexity

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For n = 200,000 the classes that fit are O(log n), O(sqrt n), O(n) and O(n log n), which agrees with the table. The second loop shows why Python demands more care: with a budget of only five million operations, n = 5000 already fails for O(n^2). We study this in Estimating Time and Memory.

Input and output formats

Parse the format exactly.

  • Multiple tests. Many problems start with t, the number of test cases, and then repeat the whole input shape t times. Constraints may also bound the sum of n over all tests (for example "the sum of n does not exceed 2 * 10^5"). That sum bound is what you use for the complexity estimate.
  • Order matters. "n and m, then n numbers, then m queries" is a different layout from "n, then n pairs".
  • Indexing. Vertices or positions may be 1-based while Python lists are 0-based. Decide at once how you will convert.
  • Output shape. Print YES/NO in the exact case the statement shows. Print each answer on its own line unless told otherwise. If "any valid answer" is accepted, the sample output is only one of many, so a correct program may differ from the sample and still pass.
  • Modulus. "Print the result modulo m" means print the remainder, which in Python is always non-negative for a positive m.

Samples are tests, not proofs

Always run the samples, but do it by hand first on at least one of them. Trace the first sample through your understanding of the task: does the expected output come out? If not, you misread something. Passing every sample is necessary and nowhere near sufficient; hidden tests contain tiny edge cases, maximum cases and adversarial structure.

Statements often hide special behaviour in a single word:

  • strictly greater versus greater or equal;
  • distinct versus any values;
  • subarray (contiguous) versus subsequence (not necessarily contiguous) versus subset;
  • at most versus exactly;
  • whether the answer should be computed before or after some operation;
  • whether the array may be empty or n may be 1.

The next demo shows how much a single misread word changes the answer. Both functions count pairs (i, j) with i < j and a[i] + a[j] hitting a target, but one reads "distinct values" and the other does not.

Python One word changes the answer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Counting positions gives 7 pairs (one 1+7 and six 5+3); counting distinct value pairs gives 2 (1+7 and 3+5). Same data, same target, a different reading, and one of them is wrong for the problem at hand.

A reading checklist

Before you write code, answer these quickly:

  1. What exactly is asked: a number, a yes/no, any valid object, or a count modulo something?
  2. What are the largest values of every variable? Which complexity do they allow?
  3. How many test cases, and is there a bound on the total size?
  4. Can the input be minimal or degenerate (n = 1, all equal, empty)?
  5. Do the samples agree with my restatement?

If you can answer all five, you can plan. If one answer is "not sure", reread that part of the statement.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A problem has n up to 200,000 and asks about all pairs of elements. What should you suspect?

    200,000 squared is 4 * 10^10, far too many operations. Setters pick limits so that the intended solution passes, so you should look for a faster idea.
  2. 2. A statement says n <= 20. What does that usually suggest?

    2^20 is about a million, so enumerating all subsets is affordable. A tiny n is often a deliberate invitation to brute-force the structure.
  3. 3. A problem allows several valid outputs and your output differs from the sample but follows all the rules. What is likely?

    When the statement says 'print any valid answer', judges use a special checker. Only the rules matter, not matching the sample.
  4. 4. Why trace a sample by hand before coding?

    If your mental model does not produce the sample output, the model is wrong. Finding that out before coding is much cheaper than after.

Summary

  • Every statement has a legend, a task, input and output formats, constraints and samples. Strip the legend and restate the task in your own variables.
  • Constraints reveal the intended complexity: n near 10^5 to 10^6 suggests O(n log n), n near 5,000 allows O(n^2), n up to about 20 allows 2^n.
  • Python needs a smaller operation budget than compiled languages, so aim for tighter complexity.
  • Check multi-test layouts, 1-based indexing, exact output wording and modulus requirements.
  • Watch for words like strictly, distinct, subarray, subsequence, at most and exactly.
  • Samples catch misreadings but never prove correctness.

Next: Python for Contests