SyntaxPilot
Courses/Competitive Programming/Lesson 3
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 3 of 90

Reading constraints: from n to the complexity you need

queued

These are the notes for Competitive Programming episode 3. A solution that is correct but too slow gets Time Limit Exceeded, which is just as wrong as a wrong answer. Here you learn to count operations, the rule of thumb of about 10^8 simple steps per second, Big-O in plain words, and the constraints table that tells you which algorithm can pass before you write any code. The running example is an original problem, Ticket Pairs, solved first by brute force (timed live until it times out) and then in O(n log n). Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler). Timings are from the recording machine and vary per run; the growth pattern does not.

The problem: Ticket Pairs

Problem C · Ticket Pairs (written for this course). A college fest raffle has n tickets with numbers a[1..n], and a lucky sum S. Count the pairs i < j with a[i] + a[j] = S.

Constraints: 1 ≤ n ≤ 2·10^5, 1 ≤ a[i], S ≤ 10^9. Time limit: 1 second.

Sample input Sample output
5 7
1 6 3 4 3
3

The pairs are 1+6, 3+4 and 4+3 (the two 3s are different tickets, so both count).

Brute force: try every pair

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll S;
    cin >> n >> S;
    vector<ll> a(n);
    for (auto &x : a) cin >> x;
    ll pairs = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] + a[j] == S) pairs++;
    cout << pairs << '\n';
    return 0;
}

Sample: prints 3. Correct. But is it fast enough for n = 200,000?

Timing it

The video's timing version generates n random tickets itself (with the random generator mt19937, seeded with 42 so every run makes the same tickets) and times only the double loop:

    int n;
    cin >> n;
    mt19937 rng(42);
    vector<ll> a(n);
    for (auto &x : a) x = rng() % 1000000 + 1;
    ll S = 1000000;
    auto start = chrono::steady_clock::now();
    ll pairs = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] + a[j] == S) pairs++;
    auto end = chrono::steady_clock::now();
    cout << "pairs = " << pairs << '\n';
    cout << "time: " << (end - start) / 1ms << " ms\n";
n Output (one run)
50,000 pairs = 1293, time: 895 ms
100,000 pairs = 5152, time: 3561 ms (2× n → about 4× time)
200,000 Time Limit Exceeded (the SyntaxPilot compiler stops at 8 s; a judge at 1 s)

Counting operations

The double loop checks n(n−1)/2 pairs. For n = 2·10^5 that is about 2·10^10 checks.

Rule of thumb: a judge does roughly 10^8 simple operations per second. Very simple, cache-friendly loops can reach ~10^9 (the compiler can even use vector instructions, as in our timing), but plan with 10^8 and you will rarely be surprised.

2·10^10 / 10^8 = 200 seconds, against a limit of 1 second. Nothing rescues that: not fast I/O, not -O2, not clever micro-optimisation.

Big-O in plain words

Big-O describes how the amount of work grows as n grows, ignoring constant factors.

Real life Big-O Double n → work
Everyone at a party shakes hands with everyone (10 guests: 45; 1000 guests: ~500,000) O(n²) × 4
Everyone signs the guest register once O(n) × 2
Finding a name in a sorted guest list by halving O(log n) + 1 step
Sorting the guest list O(n log n) a bit more than × 2

The constraints table (time limit about 1 second)

Max n Complexity that fits Typical technique
≤ 10–11 O(n!) try every order (permutations)
≤ 20–25 O(2^n · n) try every subset (bitmasks)
≤ 100 O(n^4) four nested loops
≤ 500 O(n^3) triple loop, Floyd–Warshall
≤ 5000 O(n^2) double loop, 2D DP
≤ 2·10^5 (up to ~10^6) O(n log n) or O(n √n) sorting, map/set, binary search, segment tree
≤ 10^7 – 10^8 O(n) one pass, prefix sums, two pointers
≤ 10^18 O(log n) or O(1) maths, binary search on the answer, fast power

Problem setters choose n on purpose to let exactly one of these through. The constraint is a hint about the intended solution.

Inventing the fast solution: the register

n ≤ 2·10^5 means we need about O(n log n). Turn the question around: when ticket x arrives, its partner must be exactly S − x. So keep a register (like a cloakroom book) of how many tickets with each number we have already seen:

  1. Ticket x arrives. Look up how many S − x tickets have been seen. Add that many pairs.
  2. Record x in the register.

In C++ the register is a map, which stores key → value pairs in sorted order; each lookup or update takes about log n steps. One pass, one lookup per ticket: O(n log n).

    map<ll, ll> seen;
    ll pairs = 0;
    for (ll x : a) {
        if (seen.count(S - x)) pairs += seen[S - x];
        seen[x]++;
    }
n Brute force Register (map)
50,000 pairs = 1293, ~0.9 s pairs = 1293, ~40 ms
200,000 Time Limit Exceeded pairs = 20171, ~0.2 s

Both give the same count on the same tickets, which is a quick check that the fast version is right.

Why record x after the lookup? So a ticket never pairs with itself (for example x = 5, S = 10).

The accepted solution and edge cases

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll S;
    cin >> n >> S;
    map<ll, ll> seen;
    ll pairs = 0;
    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        if (seen.count(S - x)) pairs += seen[S - x];
        seen[x]++;
    }
    cout << pairs << '\n';
    return 0;
}
Input Output Why
5 7 / 1 6 3 4 3 3 the sample
4 10 / 5 5 5 5 6 all equal: every ticket pairs with every other, 4·3/2 = 6

Edge case: an input at the extreme of the rules. With 200,000 equal tickets, the answer is n(n−1)/2 ≈ 2·10^10, which does not fit in an int. So pairs must be long long, even though every ticket number fits in an int.

Brute force vs optimal

Approach Time Extra memory n = 2·10^5
Every pair O(n²) ≈ 2·10^10 O(1) TLE
Register with map O(n log n) O(n) AC (~0.2 s)
Register with unordered_map O(n) average O(n) AC (can be attacked by anti-hash tests on some judges)
Sort + two pointers O(n log n) O(1) beyond the array AC

Solution in Java and Python

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 S = Long.parseLong(st.nextToken());
        st = new StringTokenizer(br.readLine());
        HashMap<Long, Long> seen = new HashMap<>();
        long pairs = 0;
        for (int i = 0; i < n; i++) {
            long x = Long.parseLong(st.nextToken());
            pairs += seen.getOrDefault(S - x, 0L);
            seen.merge(x, 1L, Long::sum);
        }
        System.out.println(pairs);
    }
}

Python

import sys
from collections import defaultdict

def main():
    data = sys.stdin.buffer.read().split()
    n, S = int(data[0]), int(data[1])
    seen = defaultdict(int)
    pairs = 0
    for tok in data[2:2 + n]:
        x = int(tok)
        pairs += seen[S - x]
        seen[x] += 1
    print(pairs)

main()

Read ALL the constraints

  1. Max n → the complexity (the table above).
  2. Max values → int or long long, for sums, products and even counts.
  3. Sum of n over all tests → the total work (episode 2).
  4. Memory limit → 256 MB ≈ 6·10^7 ints ≈ 3·10^7 long longs.
  5. Strangely small limits (n ≤ 20, k ≤ 5) → a hint that the solution uses them (bitmasks, small loops).

Common mistakes

Mistake What you see Why Fix
Double loop when n ≤ 2·10^5 Time limit exceeded on test 9 2·10^10 steps ≫ 10^8 per second Find an O(n log n) idea
int pairs; Wrong answer (negative count) The answer can reach 2·10^10 long long pairs;
Recording x before looking up S − x Wrong answer when 2x = S A ticket pairs with itself Look up first, then record
Only testing the sample WA/TLE on hidden tests Samples are tiny Test max n and all-equal values
Fancy algorithm when n ≤ 100 (no error) wasted time, more bugs Brute force fits Simplest thing that fits

Mini project: a complexity stopwatch

Take the timing program and run the brute force for n = 10^4, 2·10^4, 4·10^4 and 8·10^4. Write the times in a table and check that each doubling multiplies the time by about 4. Then do the same for the map version and check it roughly doubles.

Practice

  1. n ≤ 18. What complexity do you expect?

    Solution O(2^n · n): about 4.7·10^6, so trying every subset is intended.

  2. n ≤ 3000, time limit 1 s. Is O(n²) fine? O(n² log n)?

    Solution n² = 9·10^6: fine. n² log n ≈ 10^8: borderline but usually fine in C++.

  3. Solve Ticket Pairs with sorting and two pointers.

    Solution Sort `a`. Put `l = 0`, `r = n − 1`. While `l < r`: if `a[l] + a[r] < S`, `l++`; if greater, `r--`; if equal and `a[l] == a[r]`, add `(r − l + 1)(r − l)/2` and stop; otherwise count the run of equal values at `l` (`cl`) and at `r` (`cr`), add `cl · cr`, and move both pointers past their runs.

  4. Count pairs with a[i] + a[j] = S and i < j where n ≤ 2000. Which approach do you write in a contest?

    Solution The double loop: 2·10^6 checks, simplest to get right.

Quick quiz

n ≤ 10^5, time limit 1 s. Which complexity passes?

A) O(n²) B) O(n·√n) C) O(2^n) D) O(n³)

Answer

B. n·√n ≈ 3.2·10^7 steps, well under 10^8. n² = 10^10 is a hundred times too slow; 2^n and n³ are hopeless.

Interview questions

  1. What does O(n log n) mean in plain words? (Doubling n slightly more than doubles the work; sorting is the classic example.)
  2. Why is the rule "10^8 operations per second" only approximate? (It depends on the operation's cost, memory access patterns, the language and the judge machine.)
  3. How would you find all pairs summing to S faster than O(n²)? (Hash map of seen values, or sort + two pointers.)
  4. Why can the count of pairs overflow even if every element fits in an int? (The count can reach n(n−1)/2.)

Glossary

Term Meaning Example
Constraints Limits on the input values n ≤ 2·10^5
Operation (step) One simple action: a comparison, an addition, an array access a[i] + a[j] == S
Time complexity How the number of steps grows with input size O(n²)
Big-O Notation for growth, ignoring constant factors O(n log n)
Brute force Trying every possibility directly every pair (i, j)
Time Limit Exceeded (TLE) The program ran longer than allowed the double loop at n = 2·10^5
mt19937 C++'s Mersenne Twister random number generator mt19937 rng(42);
Seed The starting value of a random generator; same seed, same numbers 42
map A sorted key → value container with O(log n) operations map<ll, ll> seen;
unordered_map A hash-based key → value container, O(1) on average unordered_map<ll, ll>
Edge case An input at the extreme of the rules all tickets equal
Space complexity How much memory the algorithm needs as n grows O(n) for the map
Two pointers Two indices moving through sorted data l and r

Summary

  • Correct is not enough: the solution must fit the time limit on the largest test.
  • Count steps and compare with about 10^8 per second.
  • Big-O is how the work grows; O(n²) means 2× n → 4× time.
  • Memorise the table: 10 → n!, 20 → 2^n, 500 → n³, 5000 → n², 2·10^5 → n log n, 10^7 → n, 10^18 → log n.
  • Turning "check every partner" into "look up the one partner you need" removed the inner loop.
  • Check whether the answer needs long long, and test the extremes.

Next episode: every verdict (WA, TLE, MLE, RE) and how to debug each.