A. Primary Task

Approach

The string is invalid in the following cases:

• Length ≤ 2.
• Does not start with "10".
• The substring after "10" converts to an integer less than 2, or has leading zeros.

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
    string s;
    cin >> s;
    if (s.size() <= 2) {
        cout << "NO\n";
        return;
    }
    string tail = s.substr(2);
    if (s.substr(0,2) == "10" && stoi(tail) >= 2 && to_string(stoi(tail)) == tail)
        cout << "YES\n";
    else
        cout << "NO\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

B. Seating in a Bus

Approach

Maintain a set of occupied seats. After placing the first passenger, each new passenger must sit either in the seat immediately to the left of the current minimum or to the right of the currrent maximum.

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
    int n; cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    set<int> s;
    s.insert(a[0]);
    for (int i = 1; i < n; ++i) {
        if (a[i] == *s.rbegin() + 1 || a[i] == *s.begin() - 1) {
            s.insert(a[i]);
        } else {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

C. Numeric String Templtae

Approach

Group positions of equal numbers in the array and equal characters in the string. If the grouping patterns match exactly for all groups, the string is valid.

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
    int n; cin >> n;
    vector<int> a(n);
    map<int, int> first;
    vector<vector<int>> groups;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (!first.count(a[i])) {
            first[a[i]] = groups.size();
            groups.push_back({i});
        } else {
            groups[first[a[i]]].push_back(i);
        }
    }
    int m; cin >> m;
    while (m--) {
        string s; cin >> s;
        if (s.size() != n) {
            cout << "NO\n";
            continue;
        }
        map<char, int> firstC;
        vector<vector<int>> groupsC;
        for (int i = 0; i < n; ++i) {
            if (!firstC.count(s[i])) {
                firstC[s[i]] = groupsC.size();
                groupsC.push_back({i});
            } else {
                groupsC[firstC[s[i]]].push_back(i);
            }
        }
        cout << (groups == groupsC ? "YES\n" : "NO\n");
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

D. Right Left Wrong

Approach

To maximise the sum, pair each 'L' with the furthest possible 'R' to its right. Collect positions of 'L' from left to right and 'R' from right to left. Use prefix sums to compute the sum of segments.

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
    int n; cin >> n;
    vector<i64> a(n+1), pref(n+1,0);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        pref[i] = pref[i-1] + a[i];
    }
    string s; cin >> s;
    s = " " + s;
    vector<int> left, right;
    for (int i = n; i >= 1; --i) if (s[i] == 'R') right.push_back(i);
    for (int i = 1; i <= n; ++i) if (s[i] == 'L') left.push_back(i);
    if (left.empty() || right.empty()) {
        cout << 0 << '\n';
        return;
    }
    i64 ans = 0;
    int idx = 0;
    for (int l : left) {
        if (idx >= (int)right.size() || right[idx] < l) break;
        ans += pref[right[idx]] - pref[l-1];
        idx++;
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

E. Photoshoot for Gorillas

Approach

The number of times each cell is covered by a K×K sub-square can be computed using 2D difference arrays. Sort these cover counts descending and multiply with the sorted heights to maximise the total.

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
    i64 n, m, k, w;
    cin >> n >> m >> k >> w;
    vector<i64> a(w);
    for (auto &x : a) cin >> x;
    sort(a.begin(), a.end(), greater<>());
    vector<vector<int>> diff(n+2, vector<int>(m+2,0));
    for (int i = 1; i + k <= n+1; ++i)
        for (int j = 1; j + k <= m+1; ++j) {
            diff[i][j]++;
            diff[i][j+k]--;
            diff[i+k][j]--;
            diff[i+k][j+k]++;
        }
    vector<i64> cnt;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1];
            cnt.push_back(diff[i][j]);
        }
    }
    sort(cnt.begin(), cnt.end(), greater<>());
    i64 ans = 0;
    for (int i = 0; i < w; ++i) ans += cnt[i] * a[i];
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

F. Color Rows and Columns

Approach

For a rectangle of size a×b, the possible scores are all integers from 0 to a+b except a+b-1. Compute the cost to achieve each score usinng a greedy strategy. Then run a bounded knapsack (at least k points) to find minimal cost. The DP array size should be at least k+100 to avoid missing optimal over-k solutions.

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
    int n, k; cin >> n >> k;
    const int MAX = 114;
    const int M = MAX - 10;
    vector<vector<array<i64,2>>> rect(n+1);
    for (int i = 1; i <= n; ++i) {
        int a, b; cin >> a >> b;
        int x = a, y = b;
        vector<array<i64,2>> cur;
        int sum = 0;
        for (int pts = 1; pts <= a+b; ++pts) {
            if (pts == a+b-1) continue;
            if (pts == a+b) {
                cur.push_back({pts, (i64)a*b});
            } else {
                sum += min(x,y);
                if (x > y) x--; else y--;
                cur.push_back({pts, sum});
            }
        }
        rect[i] = cur;
    }
    vector<i64> dp(MAX, 1e18);
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = M; j >= 0; --j) {
            for (auto [cost, val] : rect[i]) {
                if (j < cost) continue;
                dp[j] = min(dp[j], dp[j-cost] + val);
            }
        }
    }
    i64 ans = -1;
    for (int i = k; i <= M; ++i) {
        if (dp[i] < 1e18) {
            if (ans == -1) ans = dp[i];
            else ans = min(ans, dp[i]);
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

G. Call During the Journey

Approach

Binary search the latest departure time. Use Dijkstra where each edge has walking time l2 and biking time l1. If the current time overlaps with the call interval [t1, t2), either walk or wait until t2 then bike. Otherwise take the faster option.

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

struct Dijkstra {
    vector<i64> dist;
    vector<vector<array<i64,3>>> g;
    int n;
    Dijkstra(int n_) : n(n_) { g.resize(n+1); }
    void add(int u, int v, int l1, int l2) {
        g[u].push_back({v, l1, l2});
    }
    void run(int s, i64 start, i64 t1, i64 t2) {
        dist.assign(n+1, 1e18);
        priority_queue<pair<i64,int>> pq;
        dist[s] = start;
        pq.push({-start, s});
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            d = -d;
            if (d > dist[u]) continue;
            for (auto [v, l1, l2] : g[u]) {
                i64 now = d + l2;
                if (max(d, t1) < min(d + l1, t2)) {
                    // overlap: walk or wait
                    now = min(now, t2 + l1);
                } else {
                    now = min(now, d + l1);
                }
                if (dist[v] > now) {
                    dist[v] = now;
                    pq.push({-now, v});
                }
            }
        }
    }
};

void solve() {
    int n, m, t0, t1, t2;
    cin >> n >> m >> t0 >> t1 >> t2;
    Dijkstra dij(n);
    for (int i = 0; i < m; ++i) {
        int u, v, l1, l2;
        cin >> u >> v >> l1 >> l2;
        dij.add(u, v, l1, l2);
        dij.add(v, u, l1, l2);
    }
    i64 L = 0, R = t0, ans = -1;
    while (L <= R) {
        i64 mid = (L+R)/2;
        dij.run(1, mid, t1, t2);
        if (dij.dist[n] <= t0) {
            ans = mid;
            L = mid+1;
        } else {
            R = mid-1;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

H. Ksyusha and the Loaded Set

Approach

We need the first position where the gap before the next element is at least k. Maintain a segment tree over a binary array (1 if present in set). The segment tree stores the longest consecutive zero run, prefix zero length, suffix zero length. To answer query k, binary search: if left child's max ≥ k go left; else if left child's suffix + right child's prefix ≥ k return the starting index; else go right. Use a std::set to remember present numbers. After each test case, reset the segment tree by toggling all previously inserted positions.

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

struct Node {
    int l, r;
    int pre, suf, mx;
};

struct SegTree {
    int n;
    vector<Node> tr;
    SegTree(int n_) : n(n_) {
        tr.resize(4 * n + 5);
        build(1, 1, n);
    }
    void build(int u, int l, int r) {
        tr[u] = {l, r, 1, 1, 1};
        if (l == r) return;
        int m = (l+r)/2;
        build(u*2, l, m);
        build(u*2+1, m+1, r);
        pull(u);
    }
    void pull(int u) {
        Node &L = tr[u*2], &R = tr[u*2+1];
        tr[u].l = L.l; tr[u].r = R.r;
        tr[u].pre = (L.pre == L.r - L.l + 1) ? L.pre + R.pre : L.pre;
        tr[u].suf = (R.suf == R.r - R.l + 1) ? L.suf + R.suf : R.suf;
        tr[u].mx = max({L.mx, R.mx, L.suf + R.pre});
    }
    void toggle(int u, int pos) {
        if (tr[u].l == tr[u].r) {
            tr[u].mx ^= 1;
            tr[u].pre = tr[u].suf = tr[u].mx;
            return;
        }
        int m = (tr[u].l+tr[u].r)/2;
        if (pos <= m) toggle(u*2, pos);
        else toggle(u*2+1, pos);
        pull(u);
    }
    int query(int u, int k) {
        if (tr[u].l == tr[u].r) return tr[u].l;
        if (tr[u*2].mx >= k) return query(u*2, k);
        if (tr[u*2].suf + tr[u*2+1].pre >= k)
            return tr[u*2].r - tr[u*2].suf + 1;
        return query(u*2+1, k);
    }
};

const int MAXN = 2000000 + 10;
SegTree seg(MAXN);

void solve() {
    set<int> s;
    int n; cin >> n;
    for (int i = 0; i < n; ++i) {
        int x; cin >> x;
        s.insert(x);
        seg.toggle(1, x);
    }
    int m; cin >> m;
    while (m--) {
        char op; int x; cin >> op >> x;
        if (op == '+') {
            s.insert(x);
            seg.toggle(1, x);
        } else if (op == '-') {
            s.erase(x);
            seg.toggle(1, x);
        } else {
            if (x > seg.tr[1].mx) {
                cout << MAXN - 10 - seg.tr[1].suf + 1 << ' ';
            } else {
                cout << seg.query(1, x) << ' ';
            }
        }
    }
    cout << '\n';
    for (int x : s) seg.toggle(1, x);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}