Competitive programming is not 'write any correct program.' It is 'write a program that is correct and finishes under the time and memory limits.' The input size is a clue, not decoration.
Most platforms give you about 10⁸ simple operations per second as a rough mental model. If n is 2·10⁵ and the limit is 2 seconds, an O(n²) double loop is already dead. You do not discover this after coding. You read it in the first twenty seconds.
A working cheat sheet, assuming ~10⁸ ops/s and a 1–2 second limit:
- n ≤ 20 — exponential 2ⁿ and factorials might live.
- n ≤ 400 — cubic O(n³) is often fine.
- n ≤ 2·10³ — quadratic O(n²) is the default guess.
- n ≤ 2·10⁵ — linearithmic O(n log n) or linear O(n).
- n ≤ 10⁶ and tight time — you want strictly linear, or n log n with a small constant.
- n ≤ 10¹⁸ — you cannot loop to n. You need math, binary search on the answer, or a closed form.
time limit per test: 2 seconds
memory limit per test: 256 megabytes
Input
The first line contains a single integer n (1 ≤ n ≤ 2·10^5).
The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ 10^9).When you finish this lesson, play Complexity Clash. It is the same muscle: look at a loop nest or a bound, name the complexity, and refuse algorithms that cannot exist.
Checks 0/2