Debugging Under a Clock

The first sample passed. Test 2 is Wrong Answer. The clock is running. The worst move is to delete a correct idea and rewrite from scratch.

Test 2 on Codeforces is often the first hidden case: t > 1, n = 1, a maximum a_i, or a second test that reuses your global arrays. AtCoder's Sample 1 can still pass while Sample 2 is the real layout. USACO's first hidden file is where file I/O and N = 1 live. Same skill: classify the failure before you touch the algorithm.

The classic WA-on-test-2: t > 1, visited never clearedcpp

int used[200005]; // values assumed in 1..n; zeroed once, not per test

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int x : a) {
    if (used[x]) { cout << "NO\n"; return; }
    used[x] = 1;
  }
  cout << "YES\n";
}

int main() {
  int t;
  cin >> t;
  while (t--) solve(); // test 2 sees test 1's marks
}

Fix pattern: clear what you used, in O(n) work you already paid for. Push the marked indices onto a vector and zero them at the end of the test, or fill(used+1, used+n+1, 0) if values are bounded by n. memset of a 2·10⁵ array per test is only legal if t is tiny or you have a sum-of-n guarantee and you memset only the prefix you need.

Off-by-one is the sibling. Statements are 1-based; your arrays are 0-based. for (int i = 1; i < n; i++) drops index n on a 1-based a[1..n]. pref[r] - pref[l] instead of pref[l-1] is a silent shift of one. Binary search that sets hi = mid vs hi = mid - 1 without an invariant will pass samples of length 5 and fail a length-2 hidden test.

Overflow that samples will not catch (a_i, b_i ≤ 1e9, n ≤ 2e5)cpp

int n;
cin >> n;
vector<int> a(n), b(n);
// ...
long long ans = 0;
for (int i = 0; i < n; i++) {
  ans += a[i] * b[i];           // int * int overflows, then promotes
  // ans += 1LL * a[i] * b[i];  // the 1LL has to land before the multiply
}

CHECK

C++. a[i] and b[i] are int, up to 1e9. You write ans += 1LL * a[i] * b[i] with ans a long long. Is the multiply safe?

Under a clock you do not stare at 120 lines. You make a minirepro: the smallest input that should fail if your bug hypothesis is right. Process:

1. Re-read Output and the loop over t. Print a wrong number of lines? That is test 2 on a multi-test problem almost every time. 2. Hand the samples with `t` duplicated. Concatenate the sample with itself. If test 1 of that file passes and test 2 fails, you have leftover state. 3. Force the edges. n = 1, n = 2, all a_i equal, a_i = 1e9, already-sorted, reverse-sorted, k = 0 if k exists. 4. Print what you think you computed, to stderr locally (cerr), never to stdout on the judge. One cerr << n << ' ' << ans << '\n' on a failed local case beats a rewrite. 5. If the idea is still plausible after a minirepro that your code gets wrong, then debug the idea. If you cannot find a minirepro in a few minutes, skip — that is the next lesson.

Minirepro file: same sample twice — leftover used[] fails heretext

TRACE

WA on test 2. Walk a 90-second diagnosis, not a rewrite.

Judge message

Test 1: OK (sample). Test 2: WA, time 15 ms, input size small. Not TLE, not RTE. So not complexity and probably not an out-of-bounds crash. The algorithm might still be right.

fast WA → logic or state, not speed

1 / 4

CHECK

Your CF submission is WA on test 2. Samples passed. The problem has t test cases and a global vis[MAXN]. First debugging step?

CHECK

1-based statement, C++ vector a(n) filled with a[0]..a[n-1]. You need the sum of the prefix of length k (first k elements in the statement). Which expression is correct?

Checks 0/3

Next lesson