Problem Classification Patterns

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Problem: Given weights of packages and D days, find the minimal ship capacity
5
// so that all packages are shipped in order within D days.
6
// Pattern: "Minimize maximum" -> Binary search on answer over capacity.
7
8
bool feasibleCapacity(const vector<int>& w, int D, long long cap) {
9
    long long curr = 0; // current load for the day
10
    int days = 1;       // start with day 1
11
    for (int x : w) {
12
        if (x > cap) return false; // capacity too small to carry single item
13
        if (curr + x <= cap) {
14
            curr += x;
15
        } else {
16
            days++;
17
            curr = x;
18
            if (days > D) return false; // too many days needed
19
        }
20
    }
21
    return true;
22
}
23
24
long long minCapacityToShip(const vector<int>& w, int D) {
25
    long long lo = 0, hi = 0;
26
    for (int x : w) {
27
        lo = max<long long>(lo, x); // lower bound: at least the max item
28
        hi += x;                    // upper bound: sum of all items
29
    }
30
    // Invariant: answer in [lo, hi]
31
    while (lo < hi) {
32
        long long mid = lo + (hi - lo) / 2; // candidate capacity
33
        if (feasibleCapacity(w, D, mid)) {
34
            hi = mid; // try to minimize further
35
        } else {
36
            lo = mid + 1; // need more capacity
37
        }
38
    }
39
    return lo;
40
}
41
42
int main() {
43
    ios::sync_with_stdio(false);
44
    cin.tie(nullptr);
45
46
    int n, D;
47
    // Example input:
48
    // 5 3
49
    // 1 2 3 4 5
50
    if (!(cin >> n >> D)) {
51
        // Fallback demo
52
        vector<int> w = {1,2,3,4,5};
53
        cout << minCapacityToShip(w, 3) << "\n"; // Expected 6
54
        return 0;
55
    }
56
    vector<int> w(n);
57
    for (int i = 0; i < n; ++i) cin >> w[i];
58
    cout << minCapacityToShip(w, D) << "\n";
59
    return 0;
60
}
61

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Count subarrays with sum <= S when all numbers are non-negative.
5
// Pattern: "Count subarrays with property" + non-negative -> two pointers.
6
7
long long countAtMostSum(const vector<long long>& a, long long S) {
8
    int n = (int)a.size();
9
    long long ans = 0, sum = 0;
10
    int L = 0;
11
    for (int R = 0; R < n; ++R) {
12
        sum += a[R];
13
        // Shrink from left until invariant holds
14
        while (L <= R && sum > S) {
15
            sum -= a[L++];
16
        }
17
        // All subarrays ending at R and starting in [L..R] are valid
18
        ans += (R - L + 1);
19
    }
20
    return ans;
21
}
22
23
// If you need exactly sum == K on non-negative arrays, you can count
24
// at_most(K) - at_most(K-1). For general integers, use prefix sums + hashmap.
25
26
int main() {
27
    ios::sync_with_stdio(false);
28
    cin.tie(nullptr);
29
30
    int n; long long S;
31
    // Example input:
32
    // 5 7
33
    // 2 1 3 2 4
34
    if (!(cin >> n >> S)) {
35
        vector<long long> a = {2,1,3,2,4};
36
        cout << countAtMostSum(a, 7) << "\n"; // Expected 9
37
        return 0;
38
    }
39
    vector<long long> a(n);
40
    for (int i = 0; i < n; ++i) cin >> a[i];
41
    cout << countAtMostSum(a, S) << "\n";
42
    return 0;
43
}
44

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Edge { int to; long long w; };
5
6
vector<long long> bfs_unweighted(const vector<vector<int>>& g, int s) {
7
    int n = (int)g.size();
8
    const long long INF = (1LL<<60);
9
    vector<long long> dist(n, INF);
10
    queue<int> q;
11
    dist[s] = 0; q.push(s);
12
    while (!q.empty()) {
13
        int u = q.front(); q.pop();
14
        for (int v : g[u]) {
15
            if (dist[v] == INF) {
16
                dist[v] = dist[u] + 1;
17
                q.push(v);
18
            }
19
        }
20
    }
21
    return dist;
22
}
23
24
vector<long long> dijkstra(const vector<vector<Edge>>& g, int s) {
25
    int n = (int)g.size();
26
    const long long INF = (1LL<<60);
27
    vector<long long> dist(n, INF);
28
    using P = pair<long long,int>; // (dist, node)
29
    priority_queue<P, vector<P>, greater<P>> pq;
30
    dist[s] = 0; pq.push({0, s});
31
    while (!pq.empty()) {
32
        auto [d, u] = pq.top(); pq.pop();
33
        if (d != dist[u]) continue; // lazy deletion
34
        for (auto e : g[u]) {
35
            if (dist[e.to] > d + e.w) {
36
                dist[e.to] = d + e.w;
37
                pq.push({dist[e.to], e.to});
38
            }
39
        }
40
    }
41
    return dist;
42
}
43
44
int main() {
45
    ios::sync_with_stdio(false);
46
    cin.tie(nullptr);
47
48
    int n, m; int s;
49
    // Input format:
50
    // n m s
51
    // m lines: u v w (0-indexed). If all w == 1, BFS used; else Dijkstra.
52
    if (!(cin >> n >> m >> s)) {
53
        // Fallback demo: unweighted triangle
54
        vector<vector<int>> gU(3);
55
        gU[0] = {1,2}; gU[1] = {2}; gU[2] = {};
56
        auto d = bfs_unweighted(gU, 0);
57
        for (auto x : d) cout << (x >= (1LL<<50) ? -1 : x) << ' '; cout << '\n';
58
        return 0;
59
    }
60
    bool allOne = true;
61
    vector<tuple<int,int,long long>> edges;
62
    edges.reserve(m);
63
    for (int i = 0; i < m; ++i) {
64
        int u, v; long long w; cin >> u >> v >> w;
65
        edges.emplace_back(u, v, w);
66
        if (w != 1) allOne = false;
67
    }
68
69
    if (allOne) {
70
        vector<vector<int>> g(n);
71
        for (auto [u,v,w] : edges) g[u].push_back(v);
72
        auto dist = bfs_unweighted(g, s);
73
        for (int i = 0; i < n; ++i) cout << (dist[i] >= (1LL<<50) ? -1 : dist[i]) << (i+1==n?'\n':' ');
74
    } else {
75
        // Ensure no negative weights for Dijkstra
76
        for (auto [u,v,w] : edges) if (w < 0) { cerr << "Negative edge detected. Use Bellman-Ford.\n"; return 0; }
77
        vector<vector<Edge>> g(n);
78
        for (auto [u,v,w] : edges) g[u].push_back({v, w});
79
        auto dist = dijkstra(g, s);
80
        for (int i = 0; i < n; ++i) cout << (dist[i] >= (1LL<<50) ? -1 : dist[i]) << (i+1==n?'\n':' ');
81
    }
82
    return 0;
83
}
84