Complexity & Constraints¶

In one sentence

Read the limits before you think about a solution: the size of $N$ tells you how fast the algorithm must be, and a computer does roughly $10^8$ simple steps per second.

1. What problem does it solve?¶

Example — 1927C · Choose the Different Ones! (2-custom_sorting · C, rating 1000)

You get an array $a$ of length $n$, an array $b$ of length $m$, and an even $k$. Choose exactly $k/2$ elements from $a$ and exactly $k/2$ from $b$ so that the chosen ones contain every number $1, 2, \dots, k$. Print YES or NO.

Limits: $t \le 10^4$; $n, m \le 2 \cdot 10^5$; $k \le 2 \min(n, m)$; $a_i, b_j \le 10^6$; the sums of $n$ and of $m$ over all tests are at most $4\cdot10^5$.

Input                Output
6
6 5 6
2 3 8 5 6 5
1 3 4 10 5           YES
6 5 6
2 3 4 5 6 5
1 3 8 10 3           NO
3 3 4
1 3 5
2 4 6                YES
2 5 4
1 4
7 3 4 4 2            YES
1 4 2
2
6 4 4 2              NO
1 5 2
3
2 2 1 4 3            NO

Two ways to read the limits.

Looking only at one test: $t = 10^4$ tests, each with $n = 2\cdot10^5$, would be $2 \cdot 10^9$ numbers. Nothing could even read that in time.
Looking at the sum constraint: all tests together have at most $4\cdot10^5$ numbers. So an $O(n + m + k)$ solution per test is $O(8 \cdot 10^5)$ for the whole input.

The idea for this problem is simple once we are sure $O(n + m + k)$ per test is allowed. For each value $v \le k$ record whether it is in $a$ and whether it is in $b$:

only in $a$: must come from $a$; only in $b$: must come from $b$; in neither: impossible.
Answer YES iff no value is missing, $\#\text{only } a \le k/2$ and $\#\text{only } b \le k/2$ (values in both can fill whichever side is short).

2. The math¶

2.1 What Big-O measures¶

$O(f(N))$ means "the number of steps grows at most like $f(N)$ once $N$ is large", ignoring constant factors. Doubling $N$ doubles an $O(N)$ loop, quadruples an $O(N^2)$ one, and adds just one step to an $O(\log N)$ one.

$N$	$\log_2 N$	$N \log_2 N$	$N^2$	$2^N$
$10$	$3.3$	$33$	$100$	$1024$
$20$	$4.3$	$86$	$400$	$10^6$
$10^3$	$10$	$10^4$	$10^6$	—
$10^5$	$17$	$1.7\cdot10^6$	$10^{10}$	—
$2\cdot10^5$	$18$	$3.5\cdot10^6$	$4\cdot10^{10}$	—

2.2 From limits to algorithm¶

With about $10^8$ simple steps per second, find the largest complexity whose value at the maximum $N$ stays under the budget. For $N = 2\cdot10^5$ the table above rules out $N^2$ and allows $N \log N$.

2.3 Counting steps for the example¶

Per test: read $a$ ($n$ steps), read $b$ ($m$), fill two flag arrays of size $k+1$, then scan $1..k$. Total $O(n + m + k)$, and since $k \le 2\min(n,m)$ this is $O(n + m)$. Summed over all tests: $O(4\cdot10^5 + 4\cdot10^5)$. A fresh vector<int>(k + 1) in every test is fine for the same reason.

The trap: allocating an array of size $10^6$ (the largest $a_i$) inside every test costs $10^4 \cdot 10^6 = 10^{10}$ steps, even though each test is small. Size per-test arrays by the test, not by the global maximum.

3. Notes from our lessons¶

From the 8 February recap:

We will dive deeper into Time Complexity in the next class. $$ O(1) < O(\log n) < O(\sqrt{n}) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n) $$

From 18 March:

Time complexity order: $$ \log N < \sqrt{N} < N < N \log N < N^2 < N^3 < N^k < 2^N < \cdots $$

Rough rule of thumb for a 1s time limit:

Time Complexity Approximate Maximum N

$O(\log N)$ $10^{18}$ or larger

$O(\sqrt{N})$ around $10^{14}$

$O(N)$ around $10^8$

$O(N \log N)$ around $10^6$

$O(N^2)$ around $10^4$

$O(N^3)$ around $500$

$O(2^N)$ around $20$ to $25$

These are only rough estimates, but they are very useful when choosing an approach during a contest.

From 22 March (Sum Constraints):

When a problem has multiple test cases, the limits on one test case are not always the full story.

For example:

$T$ may be large.

Each test case may also have large $N$ or $Q$.

But the statement may guarantee that $\sum N \le C$ or $\sum Q \le C$ over all test cases.

This means the total amount of work is still bounded, even if one single test case looks large. So when analyzing time complexity, always check whether the problem gives a sum constraint.

4. Worked solution — Choose the Different Ones!¶

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    // ina[v] / inb[v]: does v (1 <= v <= k) appear in a / in b
    vector<int> ina(k + 1, 0), inb(k + 1, 0);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x <= k) {
            ina[x] = 1;
        }
    }
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        if (x <= k) {
            inb[x] = 1;
        }
    }

    int onlya = 0, onlyb = 0;
    for (int v = 1; v <= k; v++) {
        if (!ina[v] && !inb[v]) {
            cout << "NO\n";
            return;
        }
        if (ina[v] && !inb[v]) {
            onlya++;
        }
        if (!ina[v] && inb[v]) {
            onlyb++;
        }
    }

    if (onlya <= k / 2 && onlyb <= k / 2) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T = 1;
    cin >> T;
    for (int i = 0; i < T; i++) {
        solve();
    }
    return 0;
}

Why the last check is enough: the $k$ values split into only a, only b and both. Take all only a values from $a$ ($\le k/2$ of them) and all only b values from $b$; the both values can go to whichever side still has room, and the two sides have exactly $k/2 + k/2 = k$ slots in total.

5. Reading limits: a checklist¶

Find the largest $N$ (and $Q$, and the value range).
Look for "the sum of $N$ over all test cases does not exceed …".
Pick the complexity from the table in §3; if $N \le 20$, think about bitmask brute force.
Check the largest values too: do sums or products need long long? See Integer Types & Overflow.
Size arrays per test by that test's $N$, not by the global maximum.

6. Common mistakes¶

Resetting a huge global array in every test

fill(cnt.begin(), cnt.end(), 0) on a size-$10^6$ array in each of $10^4$ tests is $10^{10}$ steps. Reset only what you touched, or allocate per test.

Ignoring the subtask limits

In AIO, the subtask limits tell you which slower solutions still score. AIO 2026 · Discount Destinations gives points to $O(NK)$ before asking for $O(N)$.

endl in a loop with $10^5$ lines

endl flushes the output every time. Print "\n" instead.

7. Practice¶

Problem	Set	Rating	What the limits say
1927C · Choose the Different Ones!	2-custom_sorting · C	1000	sum constraint allows $O(n+m)$ per test (this page)
1851B · Parity Sort	2-custom_sorting · B	800	$O(n \log n)$ with sum of $n \le 2\cdot10^5$
1097B · Petr and a Combination Lock	4-quick_power · C	1200	$n \le 15$: try all $2^{15}$ choices
1873F · Money Trees	5-BinarySearch · I	1300	$O(n^2)$ is too slow, $O(n)$ or $O(n \log n)$

Credits & licenses

The three quoted notes in §3 are from our lessons on 8 February, 18 March and 22 March, unchanged.
Example, growth table, step counting, worked solution and checklist are ours.

\(N\)	\(\log_2 N\)	\(N \log_2 N\)	\(N^2\)	\(2^N\)
\(10\)	\(3.3\)	\(33\)	\(100\)	\(1024\)
\(20\)	\(4.3\)	\(86\)	\(400\)	\(10^6\)
\(10^3\)	\(10\)	\(10^4\)	\(10^6\)	—
\(10^5\)	\(17\)	\(1.7\cdot10^6\)	\(10^{10}\)	—
\(2\cdot10^5\)	\(18\)	\(3.5\cdot10^6\)	\(4\cdot10^{10}\)	—

Time Complexity	Approximate Maximum `N`
\(O(\log N)\)	\(10^{18}\) or larger
\(O(\sqrt{N})\)	around \(10^{14}\)
\(O(N)\)	around \(10^8\)
\(O(N \log N)\)	around \(10^6\)
\(O(N^2)\)	around \(10^4\)
\(O(N^3)\)	around \(500\)
\(O(2^N)\)	around \(20\) to \(25\)