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— exponential2ⁿand factorials might live.n ≤ 400— cubicO(n³)is often fine.n ≤ 2·10³— quadraticO(n²)is the default guess.n ≤ 2·10⁵— linearithmicO(n log n)or linearO(n).n ≤ 10⁶and tight time — you want strictly linear, orn log nwith a small constant.n ≤ 10¹⁸— you cannot loop ton. 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