Reading limits: n, time, memory

Why this matters when you build with AI

When you ask an AI tool for a solution, it will usually return code that looks right for a small example. The risk is the size of the real input. A solution that loops over all pairs is fine for 1,000 numbers and far too slow for 200,000. An AI tool does not know your judge's limits unless you tell it, and it often writes the simplest correct method, not the method that fits the limits.

Reading the limits first is a short step that prevents this. Before you look at code, you write down how many operations the input size allows and how much memory the data needs. Then you check the AI's answer against those two numbers. This lesson teaches the method, with one worked problem and a list of constraint sets for practice.

Two terms first. A limit is a maximum size given in the statement, such as "n is at most 200000". An operation here means one simple step on the computer, such as an addition, a comparison, or reading one array cell.

The idea: the limits tell you the budget

Every judge has a time limit, often one or two seconds per test case. In that time a fast program can do a fixed number of simple operations. Multiply the time by the rate and you get a budget. Compare the budget with the cost of your method, which is written as a formula in n, the input size. That formula is the complexity. For example, a method that checks every pair of n numbers does about n times n divided by 2 pair checks, which we write as O(n^2). The "O" notation hides the constant factor and keeps the growth rate.

About 10^8 simple operations per second

A common planning rule is that a fast program on a typical judge machine does about 10^8 simple operations per second. This is a rough guide, not a promise. A loop that reads memory in a random order runs much slower than one that reads in order, and a machine can be faster or slower than the judge.

To check the rule on the machine where you work, we wrote a timing program. It runs 10^8 steps of a simple bit-mixing loop, the xorshift generator. Each step is three lines, each with one shift and one exclusive-or, so each step has about six simple operations.

#include <bits/stdc++.h>
using namespace std;
int main() {
    const long long N = 100000000LL;
    unsigned int x = 2463534242u;
    auto start = chrono::steady_clock::now();
    for (long long i = 0; i < N; i++) {
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
    }
    auto end = chrono::steady_clock::now();
    long long ms = chrono::duration_cast<chrono::milliseconds>(end - start).count();
    cout << "checksum " << x << "\n";
    cout << "10^8 xorshift steps took about " << ms << " ms\n";
}

We compiled it with g++ -std=c++17 -O2 -Wall -Wextra on GCC 15.2.0, on an AMD Ryzen 7 260 machine under WSL2. The output was:

checksum 961751815
10^8 xorshift steps took about 133 ms

The checksum is the same on every machine, because the arithmetic is fixed. The time is not. On your machine the number will differ, so run the program once and write down your own figure. Our figure means that 10^8 steps, about 6 times 10^8 simple operations, took a little over a tenth of a second. This loop uses only registers and no memory reads, so typical code is slower, and the planning rule of 10^8 per second is a safe guess.

Python is much slower for the same loop. In CPython, the usual Python interpreter, the same loop of 10^7 steps took about 2.7 seconds on this machine. The same 10^7 steps in C++ would take about 13 milliseconds. Python is therefore fine for small limits, but large loops need C++ or a faster method.

Turning n into a complexity target

The table below shows the rule of thumb in practice. Read a row as: "if n is at most this, a method that costs about this many operations is within the budget". All counts use round numbers.

Two things make this table useful. The first is the jump between n equal to 5,000 and n equal to 200,000. An O(n^2) method at 200,000 costs 4 times 10^10 operations, which is about 400 times the planning budget. No amount of fast reading makes that fit, so the method must change. The second is that the table gives you a target, not a guarantee. A method at the edge of the budget may pass or fail depending on memory access and constant factors, so leave room for a safety margin of a factor of about 5 when the numbers are close.

log n in the table means the base 2 logarithm of n, roughly how many times you can halve n. For n equal to 200,000, that is about 18.

Memory: how big is the data

Memory is the second limit. The statement names a memory limit, often a few hundred megabytes, and the program must stay below it. The estimate is simple. Multiply the number of stored values by the size of each value in bytes.

We checked these sizes with a short program. On the same machine, sizeof(int) was 4, sizeof(long long) was 8, and sizeof(vector<int>) was 24. The 24 bytes are the vector's own bookkeeping, a pointer and two counters, and they do not include the data. The data sits on the heap and takes count times size bytes.

We also measured real memory use. The program below allocates a vector<int> of one million values and reads the resident memory before and after, using the VmRSS line from /proc/self/status. Resident memory is the part of memory the process actually holds.

#include <bits/stdc++.h>
using namespace std;
long long rss_kb() {
    ifstream f("/proc/self/status");
    string line;
    while (getline(f, line))
        if (line.rfind("VmRSS:", 0) == 0) return stoll(line.substr(6));
    return -1;
}
int main() {
    cout << "sizeof(int)=" << sizeof(int) << " sizeof(long long)=" << sizeof(long long)
         << " sizeof(vector<int>)=" << sizeof(vector<int>) << "\n";
    long long before = rss_kb();
    vector<int> a(1000000, 1);
    long long after = rss_kb();
    cout << "vector<int> of 10^6 values: resident memory grew by about " << (after - before) << " KB\n";
    cout << "elements " << a.size() << " bytes of data " << a.size() * sizeof(int) << "\n";
}

Our output was:

sizeof(int)=4 sizeof(long long)=8 sizeof(vector<int>)=24
vector<int> of 10^6 values: resident memory grew by about 3972 KB
elements 1000000 bytes of data 4000000

The data is 4,000,000 bytes, which is 3,906 KiB, where KiB is 1024 bytes. The measured 3,972 KB includes some extra bookkeeping by the system, so the estimate is close but not exact. Your figure will differ slightly.

Memory limits are often given in megabytes. In this lesson, MB means 10^6 bytes, and MiB means 2^20 bytes. The two differ by about 5 percent. When an estimate is close to the limit, use the unit the statement uses.

A two-dimensional array needs the product of its two sizes. A table of 3000 by 3000 int values takes 3000 times 3000 times 4, which is 36,000,000 bytes, about 36 MB. A vector<vector<int>> also has one 24-byte outer entry per row, plus the rows' own data, so a table of many small rows costs more than the same count of values in one flat array. Prefer one flat vector of size n times m when you can.

Worked example: pairs with sum at most T

Here is an original problem written for this lesson.

You get t test cases. Each case has n, a number T, then n integers a_1 to a_n. Count the pairs of positions i less than j where a_i + a_j is at most T. The limits are n at most 200,000, each a_i between 0 and 10^9, and T between 0 and 2 times 10^9. The sum of n over all cases is at most 200,000.

Step one is the budget. A time limit of about one second gives about 10^8 operations as the planning budget.

Step two is the cost of the obvious method. Check every pair. That is n times (n minus 1) divided by 2 pairs, which for n equal to 200,000 is 19,999,900,000 pairs. That is about 2 times 10^10, far above the budget. The obvious method is wrong for this limit, even though it is right for small inputs.

Step three is a better method. Sort the numbers, which costs O(n log n). Then use two pointers, a left index l at the smallest value and a right index r at the largest value.

• If a[l] + a[r] is at most T, then every pair (l, k) with k between l + 1 and r also has a sum at most T, because those a[k] are no larger than a[r]. That is r - l pairs at once, so add them and move l right.
• If a[l] + a[r] is more than T, then a[r] is too large to pair with l or any value still in the range. Move r left.

Each step moves one pointer, so the loop costs O(n). The total cost is O(n log n) for the sort plus O(n) for the loop, about 3.6 million operations for the largest n, well inside the budget.

Step four is memory. The array of 200,000 values stored as long long takes 200,000 times 8 bytes, which is 1.6 MB. The answer can be as large as 19,999,900,000 when every pair counts, which does not fit in a 32-bit int, so the counter must be long long.

The solution in C++17:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
void solve() {
    int n;
    ll T;
    cin >> n >> T;
    vector<ll> a(n);
    for (auto& x : a) cin >> x;
    sort(a.begin(), a.end());
    ll count = 0;
    int l = 0, r = n - 1;
    while (l < r) {
        if (a[l] + a[r] <= T) {
            count += r - l;
            l++;
        } else {
            r--;
        }
    }
    cout << count << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

The brute force, which checks every pair, is used only to test the solution on small inputs:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        ll T;
        cin >> n >> T;
        vector<ll> a(n);
        for (auto& x : a) cin >> x;
        ll count = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (a[i] + a[j] <= T) count++;
        cout << count << '\n';
    }
}

A random generator makes small cases with negative numbers and small values, so that many pairs tie at the boundary. We wrote it in Python and ran it with python3 -I:

import random, sys
seed = int(sys.argv[1])
rng = random.Random(seed)
t = 200
print(t)
for _ in range(t):
    n = rng.randint(1, 8)
    T = rng.randint(-3, 20)
    print(n, T)
    print(*[rng.randint(-5, 10) for _ in range(n)])

We ran the sample input first. It has three cases: 4 5 with 1 2 3 4, 3 0 with 0 0 0, and 2 10 with 9 9. The output was:

4
3
0

By hand: the first case has the pairs (1,2), (1,3), (1,4) and (2,3) with sums 3, 4, 5 and 5, so 4 pairs. The second case has three pairs, each with sum 0. The third case has one pair with sum 18, which is above 10, so 0.

We then ran both programs on five seeds, 200 cases each, which is 1,000 small cases in total. All 1,000 outputs matched. The solution also ran on a maximum-size input of 200,000 random values, which took 0.018 seconds with output 10011548693, and on 200,000 zeros with T equal to 0, which gave 19999900000, the value we expected for n times (n minus 1) divided by 2.

The int mistake shows up on that all-zeros input. We made a copy of the solution with count declared as int, compiled it with -fsanitize=undefined -fno-sanitize-recover=all, and ran it:

fast_intcount.cpp:16:19: runtime error: signed integer overflow: 188957 + 2147431597 cannot be represented in type 'int'

Without the sanitizer, the same copy printed -1474936480 with no message. The value-size check from the table, applied to a counter, catches this before you run anything.

Complexity. Time is O(n log n) per test case, dominated by the sort. Memory is O(n), about 8 bytes per value for the sorted array.

Hands-on exercise

Take the six constraint sets below. For each one, write down the complexity you need, the rough operation count at the largest size, and the memory of the main data in bytes. Use the rule of about 10^8 operations per second. Each set is written as the largest size and the data it holds.

1. n at most 18. You must consider every subset of the n items, and each subset costs n work to evaluate. Items are long long values. Stored: one best value per subset, so a table with one long long per subset.
2. n at most 3000. You need a table dp of int values with one entry for every pair of positions. Each entry takes constant work.
3. n at most 200,000. Values are between 0 and 10^9. You need the sorted order of the values, then a count over pairs. Stored: the array of values as long long.
4. n at most 1,000,000. You need prefix sums of a list of long long values. Each prefix sum costs constant work.
5. n at most 400. You need every triple of positions i less than j less than k and a check on each triple. Stored: the array of int values.
6. A single number n up to 10^9, with a time limit of about one second. You need the number of divisors of n. Trial division by every number up to n would cost about 10^9 operations. Stored: a few variables.

Show the answer

1. Exponential. The method is 2^n times n, which is 2^18 times 18 = 4,718,592 operations, inside the budget. The table has 2^18 entries of 8 bytes, which is 2,097,152 bytes, about 2.1 MB.
2. O(n^2). The method is 3000 times 3000 = 9,000,000 operations, comfortably inside the budget. The table is 3000 times 3000 times 4 bytes = 36,000,000 bytes, about 36 MB. If only the previous row is needed, store one row instead, about 12 KB.
3. O(n log n). The sort costs about 200,000 times 18 = 3,600,000 operations, and the pair count is linear after the sort. The array is 200,000 times 8 bytes = 1,600,000 bytes, about 1.6 MB.
4. O(n). One pass builds the prefix sums, 1,000,000 operations. The array of prefix sums is 1,000,000 times 8 bytes = 8,000,000 bytes, about 8 MB.
5. O(n^3). The method is 400^3 = 64,000,000 operations, under the budget, though the margin is small. The data is 400 times 4 bytes = 1,600 bytes, which is negligible.
6. O(sqrt n). The loop runs up to the square root of n, which is about 31,623 steps, and the memory is a few bytes. Trial division by every number up to n would cost 10^9 steps, above the budget.

Common mistakes

Trusting a small sample. The sample input in a statement is often tiny, so an O(n^2) solution passes it. Check the largest n in the limits before you test the method. Write one large random input and time your program on it.

Forgetting that the limit applies to the sum over all cases. A statement may say "the sum of n over all test cases is at most 200,000". Then the budget covers all cases together, not each case alone. Per-case counts of 200,000 with 100 cases would break the limit by a factor of 100.

Using int for a count that can grow. The number of pairs for n equal to 200,000 is about 2 times 10^10, which overflows a 32-bit int. The overflow with the all-zeros input above gave a wrong count, and the sanitizer reported the first error. Use long long for any count or sum that can exceed about 2 times 10^9.

Estimating memory with the wrong unit. A 2000 by 2000 table of long long is 2000 times 2000 times 8 = 32,000,000 bytes, about 32 MB. Forgetting the 8 and using 4 gives half the real value. Write the unit next to every estimate.

Trusting the 10^8 rule as a measurement. The planning rule is a guess. On the machine in this lesson, the simple loop ran faster than the rule, but a loop with random memory reads may run slower. Judge the method by measuring it on a large input of the real size.

Ignoring the cost of the sort. Sorting costs O(n log n), not O(n). For n at most 10^7, the sort alone can exceed the budget, so use a linear method when the statement allows one.

Checklist

• Write down the largest n and the time limit before you read the method.
• Multiply the time limit by about 10^8 to get the budget, and divide by a safety margin of about 5 when the numbers are close.
• Compare the budget with the complexity from the table, not with the sample.
• Estimate memory as count times bytes for each array, and add the vector bookkeeping of 24 bytes per vector.
• Check the memory limit's unit, MB or MiB.
• Use long long for any sum or count that can exceed about 2 times 10^9.
• Check whether the limit applies to all test cases together or to each one.
• Time the method on one input of the largest size before you submit.

Summary

Before you write code, the limits give you two numbers: an operation budget from the time limit, and a memory estimate from the data size. The table of n against complexity tells you which method fits. Sorting and two pointers solved the worked problem in O(n log n), where the obvious pair check needed about 2 times 10^10 operations. Check the chosen method against a brute force on small random inputs, then time it on a large one.

Practice

These problems use only the limits and the method from this lesson. Work out each budget and memory estimate before you look at the answer.

1. Range sums. n and q are both at most 100,000. The array holds values up to 10^9. Each query asks for the sum of values from position l to position r. Name the complexity of the obvious method, the complexity of a better one, and the memory of the better one's main array.

   Show the answer

   The obvious method adds up each range on every query, which is O(n q) in the worst case, that is 10^10 operations, far above the budget. Build prefix sums once in O(n), so that each query is answered as the difference of two prefix values in O(1). The total is O(n + q), about 200,000 operations. The prefix array holds 100,001 long long values, which is 800,008 bytes, about 0.8 MB.

2. Best subset with a larger n. n is at most 25. You want the subset whose sum is closest to a target. Trying every subset costs 2^25 times 25 operations. Is that inside the budget? If not, describe a method that fits, and estimate its cost.

   Show the answer

   The plain method costs 2^25 times 25 = 838,860,800 operations, about 8 times the planning budget, so it does not fit. Split the items into two halves of about 12 and 13 items. Each half has at most 2^13 = 8192 subsets. Generate the sums of each half, sort them, and find the closest pair with two pointers, which costs about 8192 times 13 operations per half. The total is around 200,000 operations. Memory is 8192 values of long long per half, about 65 KB. This is called meet in the middle.

3. Grid search. A grid has 1000 rows and 1000 columns of int values. You need the shortest number of steps from the top-left cell to every other cell, moving up, down, left or right, using a breadth-first search (BFS), which visits cells in order of distance. Estimate the time and the memory.

   Show the answer

   BFS visits each cell once and looks at 4 neighbours, so the cost is about 4 times 10^6 operations, inside the budget. The grid of int values is 1000 times 1000 times 4 = 4,000,000 bytes, about 4 MB. The distance array is the same size, 4 MB. The queue holds at most 10^6 cells. If each cell is stored as a pair of two int values, which is 8 bytes on typical 64-bit GCC, the queue needs about 8 MB. Total is about 16 MB. Check sizeof(pair<int,int>) on your machine to confirm the 8 bytes.

4. Counting out-of-order pairs. n is at most 100,000. You need the number of pairs i less than j with a_i greater than a_j. Name the cost of the obvious method, a method that fits, and the memory of its array.

   Show the answer

   The obvious method checks every pair, which is n times (n minus 1) divided by 2, about 5 times 10^9 pair checks. That is about 50 times the budget. A method in O(n log n) fits, for example merge sort, which counts the out-of-order pairs while it merges, or a Fenwick tree, a structure that counts values seen so far in O(log n) per value. The array of values as long long takes 100,000 times 8 = 800,000 bytes. The answer can reach about 5 times 10^9, so use long long for the counter.

5. Memory for a graph. A graph has n at most 10^7 nodes. Estimate the memory for an array of one int per node, and for an adjacency list stored as vector<vector<int>> with no edges yet.

   Show the answer

   The array of one int per node is 10^7 times 4 = 40,000,000 bytes, about 40 MB. The vector<vector<int>> has one 24-byte outer vector per node, which is 10^7 times 24 = 240,000,000 bytes, about 240 MB, before any edges are stored. Each edge adds more. With a 256 MB limit, that leaves little room for the edges. A flat structure, such as an array of edge starts and one array of edge targets, avoids the 24 bytes per node.