Invariant Maintenance

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Find the first index i such that a[i] >= target.
5
// Invariant: f(l) == false and f(r) == true, where f(x) := (a[x] >= target).
6
// We maintain a closed interval [l, r] with this property until r = l + 1.
7
8
int lower_bound_invariant(const vector<int>& a, int target) {
9
    int n = (int)a.size();
10
    // Establish initialization for invariant: choose l and r sentinels.
11
    int l = -1;          // f(l) is conceptually false (treat a[-1] = -inf)
12
    int r = n;           // f(r) is conceptually true  (treat a[n] = +inf)
13
14
    auto f = [&](int idx) { return a[idx] >= target; };
15
16
    // Main loop: invariant must hold at the start of each iteration
17
    while (r - l > 1) {
18
        int m = l + (r - l) / 2; // avoid overflow
19
        // Since -1 < m < n, m is a valid index
20
        if (f(m)) {
21
            // Maintain f(r) == true by moving r down to m
22
            r = m;
23
        } else {
24
            // Maintain f(l) == false by moving l up to m
25
            l = m;
26
        }
27
    }
28
    // Termination: r = l + 1, with f(l)==false and f(r)==true => r is first true
29
    return r; // returns n if all elements < target
30
}
31
32
int main() {
33
    ios::sync_with_stdio(false);
34
    cin.tie(nullptr);
35
36
    int n; cin >> n;
37
    vector<int> a(n);
38
    for (int i = 0; i < n; ++i) cin >> a[i];
39
    sort(a.begin(), a.end()); // prerequisite for monotone predicate
40
41
    int q; cin >> q;
42
    while (q--) {
43
        int target; cin >> target;
44
        int idx = lower_bound_invariant(a, target);
45
        cout << idx << "\n";
46
    }
47
    return 0;
48
}
49

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct DSU {
5
    int n;
6
    vector<int> parent; // parent[x] points toward root; parent[root] == root
7
    vector<int> sz;     // sz[root] is the component size; undefined elsewhere
8
9
    DSU(int n): n(n), parent(n), sz(n, 1) {
10
        iota(parent.begin(), parent.end(), 0);
11
    }
12
13
    int find(int x) {
14
        // Path compression preserves the invariant that all nodes point to the root
15
        if (parent[x] == x) return x;
16
        return parent[x] = find(parent[x]);
17
    }
18
19
    bool unite(int a, int b) {
20
        a = find(a); b = find(b);
21
        if (a == b) return false;
22
        // Union by size: attach smaller under larger to keep trees shallow
23
        if (sz[a] < sz[b]) swap(a, b);
24
        parent[b] = a;
25
        sz[a] += sz[b];
26
        return true;
27
    }
28
29
    // Optional O(n) verifier for debugging: checks key invariants
30
    bool verify() const {
31
        int N = n;
32
        vector<int> root(N);
33
        // Recompute roots without mutation (slow check via naive climbing)
34
        for (int i = 0; i < N; ++i) {
35
            int x = i;
36
            while (parent[x] != x) x = parent[x];
37
            root[i] = x;
38
        }
39
        // Check parent[root] == root and accumulate sizes
40
        vector<int> count(N, 0);
41
        for (int i = 0; i < N; ++i) {
42
            if (parent[root[i]] != root[i]) return false; // roots point to themselves
43
            count[root[i]]++;
44
        }
45
        for (int r = 0; r < N; ++r) {
46
            if (parent[r] == r) {
47
                if (count[r] != sz[r]) return false; // size matches component cardinality
48
            }
49
        }
50
        return true;
51
    }
52
};
53
54
int main() {
55
    ios::sync_with_stdio(false);
56
    cin.tie(nullptr);
57
58
    int n, m; cin >> n >> m;
59
    DSU dsu(n);
60
    while (m--) {
61
        int t, u, v; cin >> t >> u >> v;
62
        if (t == 1) {
63
            dsu.unite(u, v);
64
        } else {
65
            cout << (dsu.find(u) == dsu.find(v) ? "YES" : "NO") << '\n';
66
        }
67
    }
68
69
    // Optional debug check (don’t do this in tight loops):
70
    // cerr << (dsu.verify() ? "OK" : "BROKEN") << '\n';
71
72
    return 0;
73
}
74

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Longest subarray with sum <= S using two pointers.
5
// Invariant: at the start of each outer iteration, the window [l, r) satisfies sum <= S.
6
7
long long longest_bounded_sum(const vector<int>& a, long long S) {
8
    int n = (int)a.size();
9
    int l = 0; long long sum = 0; int best = 0;
10
    for (int r = 0; r < n; ++r) {
11
        sum += a[r];
12
        // Restore invariant by shrinking from the left while violated
13
        while (sum > S && l <= r) {
14
            sum -= a[l++];
15
        }
16
        // Now invariant holds: sum <= S for window [l, r]
17
        best = max(best, r - l + 1);
18
    }
19
    return best;
20
}
21
22
int main() {
23
    ios::sync_with_stdio(false);
24
    cin.tie(nullptr);
25
26
    int n; long long S; cin >> n >> S;
27
    vector<int> a(n);
28
    for (int i = 0; i < n; ++i) cin >> a[i];
29
    cout << longest_bounded_sum(a, S) << "\n";
30
    return 0;
31
}
32