When I started solving problems on Codeforces, I read the story, thought about the logic, and only glanced at the numbers at the bottom of the statement. That is backwards. The constraints are often the biggest hint the problem setter gives you, because they tell you how fast your solution has to be, and that usually narrows down which technique you need.
This post is the habit I wish I had built on day one: read the limits first, estimate the operation count, and let that steer your idea.
The 108 rule of thumb
A typical judge machine runs roughly 108 simple operations per second in C or C++. It is not exact. Cache-friendly loops can do several times more, while heavy operations like map lookups or modulo do less. But it is close enough to decide between ideas. With a 1 second time limit, plan for at most a few times 108 basic steps.
Now plug the input size into the complexity you have in mind. If n = 2 × 105 and your idea is O(n2), that is 4 × 1010 steps, hundreds of times too slow. You know it will get Time Limit Exceeded before writing a single line.
A cheat sheet from n to complexity
| Largest n | Complexity that usually fits | Typical techniques |
|---|---|---|
| ≤ 10 | O(n!), O(n6) | Try every permutation |
| ≤ 20 | O(2n · n) | Bitmask brute force, subset enumeration |
| ≤ 500 | O(n3) | Floyd–Warshall, interval DP |
| ≤ 5 000 | O(n2) | Double loops, 2D DP |
| ≤ 105 to 106 | O(n log n) or O(n) | Sorting, binary search, prefix sums, two pointers, BFS/DFS, DSU |
| ≤ 109 or more | O(log n), O(√n) or O(1) | Math formula, binary exponentiation, binary search on the answer |
The table is a starting point, not a law. A problem with n ≤ 2 × 105 almost never wants O(n2), but it might want O(n√n) or O(n log2 n).
Worked example: the same task at three sizes
Suppose you must answer q questions of the form “what is the sum of the array between positions l and r?”
- n, q ≤ 100: just loop from l to r for each question. At most 104 steps.
- n, q ≤ 5 000: the same loop is 2.5 × 107 steps. Still fine.
- n, q ≤ 2 × 105: the loop could need 4 × 1010 steps. You need O(1) per question, which points straight at prefix sums.
Same story, three different intended solutions. The only thing that changed was the constraints.
Small limits are hints too
When a limit is surprisingly small, ask why. If n ≤ 20 in a problem about choosing items, the setter is telling you that trying all 220 ≈ 106 subsets is allowed. If values are at most 100 while n is large, maybe you should count how often each value appears instead of sorting. If k ≤ 10 while everything else is large, the solution probably has a factor of k or 2k in it.
Watch the value limits as well
Constraints do not only describe time. They also tell you which types to use:
- A 32-bit
intholds up to about 2.1 × 109. If you add up 105 values of size 109, the sum can reach 1014, so uselong long. - Multiplying two numbers below 109 + 7 gives up to about 1018, which fits in
long long(limit about 9.2 × 1018) but not inint. - Memory limits matter too. An array of 108
ints is 400 MB, which is more than most problems allow.
Theatre Square (1A) is the classic example: the logic is one line, but the answer can be 1018, and using int is the most common reason for Wrong Answer.
A routine to use on every problem
- Read the input limits and the time limit before the story.
- Write down the largest n and look it up in the table above.
- Think of the simplest correct solution and estimate its operation count.
- If it fits, write it. If not, you now know how much faster the real idea must be.
- Check the value limits and pick
intorlong longaccordingly.
It takes thirty seconds and saves a lot of wasted submissions. If you are still deciding whether contests are worth your time at all, I wrote about why competitive programming is worth it.
