SyntaxPilot
Courses/Competitive Programming/Lesson 1
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 1 of 90

What competitive programming is: contests, judges, verdicts, ratings

queued

These are the notes for Competitive Programming episode 1. You will learn what a programming contest is, how to read a problem statement, how an online judge checks your code, every verdict it can give (AC, WA, TLE, MLE, RE, CE), how contests are scored, and how ratings move. On the way you solve an original contest problem, Chai Batches, and hit two wrong answers before getting it accepted. Every C++ example below was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command the SyntaxPilot compiler uses) and run with the input shown.

The problem: checking 300 answers by hand

A college coding club runs its first contest: 300 students, the same five problems, two hours. Every student sends in code, and one organiser has to run each program, type in some inputs, read the output and decide "right" or "wrong". Results come out three days later, and two students with the same answer got different marks because the organiser was tired.

Checking by hand is slow and unfair. We need a machine that checks every program the same way, in seconds. By the end of these notes you will have invented it: the online judge.

What a contest is

Part What it means
Problem set A list of problems named A, B, C ..., usually from easiest to hardest
Fixed time Usually 2 to 3 hours (some contests are shorter)
Submission You send your source code for one problem
Judge A program that compiles and runs your code on secret tests and returns a verdict in seconds
Ranking First by problems solved (or points), then by time and penalties

The key rule: your code must be correct and fast enough on inputs you never see.

How to read a problem statement

Every statement has the same parts. Here is the problem from the video (written for this course, in the style of a real round):

Problem A · Chai Batches. A chai stall has n customers; customer i wants a[i] cups. The kettle makes at most k cups per batch. What is the minimum number of batches needed to serve everyone?

Input: the first line has n and k. The second line has a[1] ... a[n]. Output: one integer, the minimum number of batches. Constraints: 1 ≤ n ≤ 200000, 1 ≤ a[i], k ≤ 10^9. Limits: 1 second, 256 MB.

Sample input 3 4 2 5 3 Sample output 3

  • Story: what is happening, in words.
  • Input format / output format: exactly what you read and exactly what you print.
  • Constraints: the limits on every value. They tell you which types you need and which algorithms are fast enough. Read them first.
  • Sample: a small example input with its correct output. It is usually test 1.
  • Time and memory limits: per test.

Solving Problem A live

Attempt 1: divide (Wrong Answer on the sample)

#include <iostream>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        sum += a;
    }
    cout << sum / k << endl;
    return 0;
}

Input 3 4 / 2 5 3 prints 2. Expected 3. Wrong Answer on test 1.

Why: integer division rounds down. 10 people with 4-seat autos: 10 / 4 = 2, but the last 2 people still need a third auto. We need to round up (the ceiling).

The ceiling trick

For positive integers, ceil(s / k) == (s + k - 1) / k.

  • 10 cups, k = 4: (10 + 3) / 4 = 13 / 4 = 3.
  • 8 cups, k = 4: (8 + 3) / 4 = 11 / 4 = 2 (no remainder, so the extra k - 1 never adds a whole batch).

Attempt 2: round up (passes the sample, WA on a hidden test)

Change the last line to cout << (sum + k - 1) / k << endl;. The sample now prints 3.

A hidden test the contestants never see:

3 1
1000000000 1000000000 1000000000

The correct answer is 3000000000. The program prints:

-1294967296

Wrong Answer on test 2.

Why: integer overflow

Type Size Largest value
int 32 bits 2,147,483,647 (about 2.1 · 10^9)
long long 64 bits 9,223,372,036,854,775,807 (about 9.2 · 10^18)

sum reached 3,000,000,000, which does not fit in an int. It wrapped around: 3,000,000,000 − 2^32 = −1,294,967,296. A value too big for its type is called integer overflow. (In C++, signed overflow is formally undefined behaviour; in practice on g++ it usually wraps like this, but you must never rely on it.)

The constraints told us before we wrote a line: at most 200000 customers × 10^9 cups = 2 · 10^14. That never fits in an int.

Attempt 3: long long (Accepted)

#include <iostream>
using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        long long a;
        cin >> a;
        sum += a;
    }
    cout << (sum + k - 1) / k << endl;
    return 0;
}
Input Output
3 4 / 2 5 3 3
3 1 / 1000000000 1000000000 1000000000 3000000000

Both pass. On a judge this gets Accepted (AC).

Brute force vs optimal for Chai Batches

The "subtract k until nothing is left" idea is correct but slow:

long long batches = 0;
while (sum > 0) {
    sum -= k;
    batches++;
}
cout << batches << endl;

With 40 customers wanting 10^9 cups each and k = 1, the loop runs 4 · 10^10 times. In the SyntaxPilot compiler (which stops programs after 8 seconds) it gives Time Limit Exceeded; a judge stops it after 1 or 2 seconds.

Approach Time Memory Verdict on max tests
Subtract k in a loop O(sum / k), up to 2 · 10^14 steps O(1) TLE
(sum + k - 1) / k O(n) to read, O(1) to answer O(1) AC

The accepted solution in C++, Java and Python

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        long long a;
        cin >> a;
        sum += a;
    }
    cout << (sum + k - 1) / k << '\n';
    return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        long k = Long.parseLong(st.nextToken());
        st = new StringTokenizer(br.readLine());
        long sum = 0;
        for (int i = 0; i < n; i++) sum += Long.parseLong(st.nextToken());
        System.out.println((sum + k - 1) / k);
    }
}

Python

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, k = int(data[0]), int(data[1])
    total = sum(map(int, data[2:2 + n]))
    print((total + k - 1) // k)

main()

Python integers never overflow, so the overflow trap does not exist there, but Python is slower, so on tight time limits C++ is safer.

Inventing the online judge

The tired organiser The online judge
Types whatever inputs he thinks of, different for each student Hidden tests: the same fixed secret test files for everyone (often 20 to 100)
Eyeballs the output: "looks about right" Exact compare: your output against the correct output (usually ignoring trailing spaces and the final newline)
Waits as long as a program takes Time limit and memory limit per test

What happens when you click Submit:

Compile ──► Test 1 (run + compare) ──► Test 2 ──► ... ──► Verdict
                     │ first failure stops everything
                     ▼
            "Wrong answer on test 7" = tests 1-6 passed

During a contest you usually see only the verdict and the test number, not the test itself.

Some problems have more than one correct answer (for example "print any valid arrangement"). Those use a checker, a small program that verifies your output instead of comparing it character by character. You will meet them in the constructive-problems episode.

Every verdict

Verdict Means Typical causes
AC Accepted Every test passed —
WA Wrong Answer Some output did not match overflow, wrong rounding, wrong format, missed edge case
TLE Time Limit Exceeded Too slow on some test algorithm too slow for the constraints, infinite loop, slow I/O
MLE Memory Limit Exceeded Used too much memory huge arrays, n × n tables
RE Runtime Error The program crashed index out of range, division by zero, too-deep recursion
CE Compilation Error It did not compile typo, missing semicolon, missing header

The verdicts seen live in the video:

Compilation Error: remove the semicolon after long long sum = 0:

main.cpp: In function 'int main()':
main.cpp:8:5: error: expected ',' or ';' before 'for'
    8 |     for (int i = 0; i < n; i++) {
      |     ^~~
main.cpp:8:21: error: 'i' was not declared in this scope

g++ points at line 8, the line after the mistake, because that is where it noticed. On most judges a compilation error costs no penalty, but it costs minutes.

Time Limit Exceeded: the subtract loop on 40 × 10^9 cups with k = 1.

Wrong Answer from extra text: cout << "Answer: " << ans prints Answer: 3, but the expected output is 3. Print exactly what the output format asks for.

How contests are scored

  • ICPC style (the big university contest and many online rounds): most problems solved wins. Ties are broken by penalty time: for each solved problem, the minutes from the start until it was accepted, plus 20 minutes for every rejected attempt before that. Wrong attempts on problems you never solve cost nothing.
  • Score style: each problem is worth points. On some sites a problem's points shrink as time passes, so solving early is worth more, and wrong attempts cost points or penalty minutes.
  • Each site (Codeforces, AtCoder, CodeChef and others) publishes the exact rules of each round. Read them once.

The practical lesson: run every sample before you submit. A wrong answer is never free.

How ratings work

A rating is one number that estimates your skill, like a chess rating. Before a rated contest, your rating predicts roughly where you should finish.

  • Finish higher than predicted (for example by beating people rated above you): your rating goes up. A bigger surprise means a bigger jump.
  • Finish lower than predicted: it goes down a little.
  • Each contest is a small correction; after 10 to 20 contests the number is quite accurate.

Don't chase the number. It follows your practice. The real measure of progress is how many new problems you can solve.

Common mistakes (and the real messages)

Mistake What you see Why Fix
int sum; when the sum can reach 2 · 10^14 A wrong, often negative, answer (no error) int overflows above about 2.1 · 10^9 long long sum;
cout << "Answer: " << ans; Wrong answer on test 1 The judge compares exactly cout << ans << '\n';
cout << sum / k; for "how many batches" Wrong answer on test 1 Integer division rounds down (sum + k - 1) / k
Missing semicolon error: expected ',' or ';' before 'for' g++ reports where it noticed Look at the line before the reported one
Subtracting in a loop instead of dividing Time limit exceeded 10^14 loop steps Use arithmetic
Submitting without running the sample WA + 20 penalty minutes Every wrong try costs Run every sample first

Mini project: your own tiny judge

You can do by hand exactly what a judge does. Save the sample as in1.txt and its answer as ans1.txt, then:

g++ -O2 -std=c++17 main.cpp -o main
./main < in1.txt > out1.txt
diff -w out1.txt ans1.txt && echo "Test 1: OK" || echo "Test 1: WRONG ANSWER"

Add in2.txt / ans2.txt with the overflow test and you have a two-test judge. In episode 5 you will turn this into a full stress tester.

Practice

  1. Bus seats. n students and buses with k seats each. How many buses? (1 ≤ n, k ≤ 10^18)

    Solution `(n + k - 1) / k` with `long long`. Careful: `n + k - 1` can reach about 2 · 10^18, which still fits in `long long` (max ≈ 9.2 · 10^18). An overflow-proof alternative is `n / k + (n % k != 0)`.

  2. Total cups. Print the total number of cups in Chai Batches. Which type do you need?

    Solution Up to 2 · 10^5 × 10^9 = 2 · 10^14, so `long long`.

  3. Which verdict? A program reads n and allocates vector<int> v(n * n) with n = 100000. What happens?

    Solution `n * n` is computed in `int` and overflows first; even with `(long long)n * n` it would need 10^10 ints = 40 GB. A judge reports MLE or RE.

  4. Round up without the trick. Show that (s + k - 1) / k equals s / k when k divides s, and s / k + 1 otherwise.

    Solution Write `s = q·k + r` with `0 ≤ r < k`. Then `s + k - 1 = q·k + (r + k - 1)`. If `r = 0`, `r + k - 1 = k - 1 < k`, so the result is `q`. If `r ≥ 1`, `k ≤ r + k - 1 < 2k`, so the result is `q + 1`.

Quick quiz

int a = 2000000000, b = 2000000000;
long long c = a + b;
cout << c << endl;

A) 4000000000 B) -294967296 C) 2000000000 D) Compile error

Answer

B, -294967296. a + b is computed in int first and overflows; only then is the broken result stored in the long long. Fix: long long c = (long long)a + b;.

Interview questions

  1. What is the difference between Wrong Answer and Time Limit Exceeded? (WA: an output didn't match. TLE: the program didn't finish within the time limit, even if it would have been right.)
  2. Why do judges use hidden tests instead of showing them? (So solutions must be correct in general, not tuned to known inputs.)
  3. When does int overflow, and how do you prevent it? (Above 2,147,483,647; use long long whenever max values multiplied or summed exceed about 2 · 10^9.)
  4. How do you compute the ceiling of a / b for positive integers without floating point? ((a + b - 1) / b.)
  5. What is penalty time in ICPC-style scoring? (Sum of solve times plus 20 minutes per rejected attempt on solved problems.)

Glossary

Term Meaning Example
Competitive programming Solving well-defined coding problems under time limits, checked automatically A 2-hour round with problems A to F
Contest / round A timed event with a problem set A Div. 3 round
Problem set The list of problems in a contest A, B, C, D, E
Online judge A program that compiles your code, runs it on hidden tests with limits, and gives a verdict The grader on a contest site
Submission Code you send for one problem main.cpp for problem A
Test case One input file (and its correct output) 3 1 / 10^9 10^9 10^9
Sample test A small example shown in the statement, usually test 1 3 4 / 2 5 3 → 3
Hidden test A test you never see during the contest the overflow test
Constraints The limits on input values 1 ≤ n ≤ 2·10^5
Time limit Max running time per test 1 second
Memory limit Max memory per test 256 MB
Verdict The judge's result AC, WA, TLE, MLE, RE, CE
Integer overflow A value too big for its type, which wraps or breaks int holding 3 · 10^9
long long 64-bit integer type, up to about 9.2 · 10^18 long long sum = 0;
Ceiling Rounding up to the next whole number ceil(10 / 4) = 3
Checker A program that verifies outputs when many answers are valid "print any valid order" problems
Penalty time Tie-breaker: solve times plus minutes per wrong try +20 min per rejected attempt (ICPC)
Rating A number estimating skill, updated after each rated contest 1200 → 1290
Edge case An input at the extreme of the rules all values at 10^9

Summary

  • A contest is a problem set, a fixed time and a judge.
  • Read the statement in this order: constraints, input/output format, samples.
  • The judge runs hidden tests, compares output exactly, and enforces time and memory limits. The first failing test decides the verdict.
  • Verdicts: AC, WA, TLE, MLE, RE, CE.
  • Round up with (s + k - 1) / k. Anything that can exceed about 2 · 10^9 needs long long.
  • Penalties punish wrong submissions, so always run the samples first.
  • Ratings move by how you perform against the prediction.

Next episode: your C++ contest template: bits/stdc++.h, multiple test cases, and fast input/output.