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
ncustomers; customeriwantsa[i]cups. The kettle makes at mostkcups per batch. What is the minimum number of batches needed to serve everyone?Input: the first line has
nandk. The second line hasa[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 3Sample output3
- 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 - 1never 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
-
Bus seats.
nstudents and buses withkseats 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)`. -
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`. -
Which verdict? A program reads
nand allocatesvector<int> v(n * n)withn = 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. -
Round up without the trick. Show that
(s + k - 1) / kequalss / kwhenkdividess, ands / k + 1otherwise.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
- 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.)
- Why do judges use hidden tests instead of showing them? (So solutions must be correct in general, not tuned to known inputs.)
- When does
intoverflow, and how do you prevent it? (Above 2,147,483,647; uselong longwhenever max values multiplied or summed exceed about 2 · 10^9.) - How do you compute the ceiling of
a / bfor positive integers without floating point? ((a + b - 1) / b.) - 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 needslong 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.