Memory, limits, and many test cases
Count peak live storage and total work across cases before choosing an algorithm.
Count what is alive together
Auxiliary space counts working storage beyond the supplied input under a stated convention. A sum helper uses a counter and total: O(1) extra space. Storing its n input values is O(n) input storage. Creating an independent length-n copy adds O(n) auxiliary storage.
Repeated pair checks can use O(n²) time while reusing a few counters and needing O(1) auxiliary space. Twenty sequential temporary copies do not imply twenty copies exist together. If those copies are kept, the peak storage changes.
Capacity and bytes matter too
int a[1000]{} allocates and initializes 1000 elements even if the active n is three. With capacity C, the allocation is O(C); a literal fixed capacity is constant with respect to active n. Describing a scalable array algorithm as O(n) storage assumes capacity grows with the needed size.
On a machine with four-byte int, one million elements occupy 4,000,000 bytes before overhead. A decimal MB is 10⁶ bytes; a MiB is 2²⁰ bytes. Actual type sizes and runtime overhead must fit the judge’s environment and memory limit.
Sum the cases the statement actually allows
Linear work on case sizes n₁ through nₜ gives O(t + Σnᵢ). If Σnᵢ ≤ 200000, do not assign 200000 elements independently to every case. Use local state inside solve() so each call starts fresh and old counts do not leak.
Quadratic work gives Σnᵢ², which can be as large as S² when total size is S. If each case also satisfies nᵢ ≤ B, then Σnᵢ² ≤ BS. Resetting a capacity-C array every case adds O(tC), even for mostly empty cases.
Use the maximum size as a plausibility check
At n = 100000, n² is ten billion while n⌈log₂ n⌉ is about 1.7 million. Those are growth-term estimates, not exact processor instructions. Hardware, operation costs, allocation, input/output, and compiler settings all affect elapsed time.
Prefer reducing obviously excessive work before benchmarking. A formula such as n(n + 1)/2 can replace a linear summation loop under a safe numeric bound, but a fast expression with an overflowing intermediate is still incorrect.
Growth explorer
Idealized operation counts show growth. Actual runtime also depends on the implementation and machine.
O(1)1O(log n)7O(n)100O(n log n)665O(n²)10,000Bar lengths use a logarithmic scale. Logarithms use base 2.
Guided simulation · Change the inputs to test your understanding.
At most 1000 cases have a combined length of at most 200000. Each case is scanned once. What best describes total work?
Turn the idea into code
Implement solve() for one case: read 0 ≤ n ≤ 100000 scores in [0, 100], count scores ≥ 50, and print the count. main reads t and calls solve t times. The total score count is at most 100000. Avoid storing scores you never revisit.
Give me a hint
Keep a local passed counter inside solve. Process each score as it arrives.
Show the explained solution
A local counter resets for each case. Streaming uses O(1) extra storage and O(t + Σnᵢ) total time. Test an empty case immediately after a case containing several passing scores.
// Complete C++23 program. Input: t, then n and n scores for each case.
#include <iostream>
bool isPassing(int score) { return score >= 50; }
void solve() {
int n = 0, passed = 0;
std::cin >> n;
for (int i = 0; i < n; ++i) {
int score = 0;
std::cin >> score;
if (isPassing(score)) ++passed;
}
std::cout << passed << '\n';
}
int main() {
int t = 0;
std::cin >> t;
for (int test = 0; test < t; ++test) solve();
}Your notes
Mark complete when you can explain it yourself.