Debugging Strategies for CP

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Count pairs (i < j) such that (a[i] + a[j]) % k == 0
5
// Brute-force: O(n^2)
6
long long brute_pairs(const vector<int>& a, int k) {
7
    long long ans = 0;
8
    int n = (int)a.size();
9
    for (int i = 0; i < n; ++i) {
10
        for (int j = i + 1; j < n; ++j) {
11
            int s = a[i] + a[j];
12
            int r = ((s % k) + k) % k; // normalize to non-negative
13
            if (r == 0) ans++;
14
        }
15
    }
16
    return ans;
17
}
18
19
// Fast: O(n + k) using remainder counts
20
long long fast_pairs(const vector<int>& a, int k) {
21
    vector<long long> cnt(k, 0);
22
    for (int x : a) {
23
        int r = ((x % k) + k) % k; // normalize
24
        cnt[r]++;
25
    }
26
    long long ans = 0;
27
    // r = 0 pairs among themselves
28
    ans += cnt[0] * (cnt[0] - 1) / 2;
29
    // pair r with k-r
30
    for (int r = 1; r <= (k - 1) / 2; ++r) {
31
        ans += cnt[r] * cnt[k - r];
32
    }
33
    // if k even, r = k/2 pairs among themselves
34
    if (k % 2 == 0) {
35
        ans += cnt[k / 2] * (cnt[k / 2] - 1) / 2;
36
    }
37
    return ans;
38
}
39
40
int main() {
41
    ios::sync_with_stdio(false);
42
    cin.tie(nullptr);
43
44
    // Randomized stress test
45
    std::mt19937 rng(123456); // fixed seed for reproducibility
46
    std::uniform_int_distribution<int> n_dist(0, 20);
47
    std::uniform_int_distribution<int> k_dist(1, 10);
48
    std::uniform_int_distribution<int> val_dist(-20, 20);
49
50
    for (int it = 1; it <= 50000; ++it) {
51
        int n = n_dist(rng);
52
        int k = k_dist(rng);
53
        vector<int> a(n);
54
        for (int i = 0; i < n; ++i) a[i] = val_dist(rng);
55
        long long b = brute_pairs(a, k);
56
        long long f = fast_pairs(a, k);
57
        if (b != f) {
58
            cerr << "Mismatch at iteration " << it << "\n";
59
            cerr << "n=" << n << " k=" << k << "\n";
60
            cerr << "a:";
61
            for (int x : a) cerr << ' ' << x;
62
            cerr << "\n";
63
            cerr << "brute=" << b << " fast=" << f << "\n";
64
            return 0; // stop at first failure
65
        }
66
        if (it % 5000 == 0) {
67
            cerr << "OK up to iteration " << it << "\n"; // progress log
68
        }
69
    }
70
    cerr << "All tests passed!\n";
71
    return 0;
72
}
73

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Enable -DLOCAL when compiling locally to turn on debug logs
5
#ifdef LOCAL
6
#define DBG(x) cerr << #x << " = " << (x) << "\n"
7
#else
8
#define DBG(x)
9
#endif
10
11
int main() {
12
    ios::sync_with_stdio(false);
13
    cin.tie(nullptr);
14
15
    int n, q;
16
    if (!(cin >> n >> q)) return 0; // robust input
17
18
    vector<long long> a(max(n, 0));
19
    for (int i = 0; i < n; ++i) cin >> a[i];
20
21
    // Build 1-based prefix sums to avoid off-by-one errors: pref[0] = 0
22
    vector<long long> pref(n + 1, 0);
23
    for (int i = 1; i <= n; ++i) {
24
        pref[i] = pref[i - 1] + a[i - 1]; // a is 0-based; pref is 1-based
25
        if (i <= 5) DBG(pref[i]); // sample debug
26
    }
27
28
    // Process queries of the form: sum of [l, r], 1 <= l <= r <= n
29
    while (q--) {
30
        int l, r; cin >> l >> r;
31
        // Defensive checks (use assertions locally; remove for submission if needed)
32
        if (!(1 <= l && l <= r && r <= n)) {
33
            // For submissions, you would assume inputs are valid per statement.
34
            // This path helps catch invalid tests locally.
35
            cerr << "Invalid query: l=" << l << " r=" << r << "\n";
36
            cout << 0 << "\n";
37
            continue;
38
        }
39
        long long ans = pref[r] - pref[l - 1];
40
        cout << ans << '\n';
41
    }
42
    return 0;
43
}
44

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Demonstrates overflow pitfalls and safe patterns.
5
int main() {
6
    ios::sync_with_stdio(false);
7
    cin.tie(nullptr);
8
9
    int n; cin >> n;
10
    vector<long long> a(n);
11
    for (int i = 0; i < n; ++i) cin >> a[i]; // read as long long to be safe
12
13
    // Example 1: Sum safely in 64-bit
14
    long long sum = 0;
15
    for (long long x : a) {
16
        sum += x; // safe if |sum| fits in 64-bit
17
    }
18
19
    // Example 2: Weighted sum: sum of a[i] * (i+1)
20
    // Cast before multiplication to avoid 32-bit overflow if a was int.
21
    long long wsum = 0;
22
    for (int i = 0; i < n; ++i) {
23
        wsum += (long long)(i + 1) * a[i]; // promote before multiply
24
    }
25
26
    // Example 3: Use __int128 as an internal guard when values approach 1e18
27
    __int128 guard_sum = 0;
28
    for (int i = 0; i < n; ++i) {
29
        guard_sum += (__int128)a[i] * (i + 1);
30
    }
31
    // Clamp or check range before converting back
32
    const long long LLIM = LLONG_MAX;
33
    bool ok = (-(__int128)LLIM <= guard_sum && guard_sum <= (__int128)LLIM);
34
    long long safe_wsum = ok ? (long long)guard_sum : (guard_sum > 0 ? LLIM : -LLIM);
35
36
    cout << sum << '\n' << wsum << '\n' << safe_wsum << '\n';
37
    return 0;
38
}
39