Summary

Time Allocation

Nothing much to say; I sat through the entire contest, with some random submissions in between, essentially playing the IOI format.

Exam Reflection

Although the problems in this contest were quite challenging and had low discrimination, there were still some points I failed to secure. For example, the $O(qn)$ DP or greedy approach for T3, and the brute-force search for T1 (which I didn't write because it seemed too detailed and troublesome). During the exam, one must try every possible way to get partial scores on difficult problems.

Editorial

T1

Given the constraints, bitmask DP is the natural choice. A straightforward DP transition would be: let dp[mask] represent the minimum time required to reach the final state from the current mask, and then each new operation transitions. However, this approach has two drawbacks. First, it has aftereffects because you don't know whether the new mask after adding an operation is larger than the original mask, meaning you can't fix an enumeration order for transitions. This problem can be easily solved by adding more dimensions whenever aftereffects occur. Second, when adding operations later, all previous operations need to be extended by one second, which is very difficult to handle. However, the solution to this problem is quite ingenious.

Consider two operation sequences: 1) starting from the 1st second, operate on nodes 1, 2, and 3 in the next three seconds respectively; 2) no operation at the 1st second, but from the 2nd second onwards, operate on nodes 1, 2, and 3 in the next three seconds respectively. It's easy to see that the final states of these two sequences are identical. This means we can transform adding operations to the end into adding them to the beginning, so we only need to consider the state of the new operation after a few seconds.

Thus, the final DP is: let dp[i][mask] indicate whether it's possible to reach state mask after the i-th second. We preprocess w[i][j], which represents the state of the tree after j seconds of operating on node i. The DP transition formula becomes straightforward. See the code below for details.

Core Code:

for (int i = 1; i <= n; i++) { // Preprocess w array
    int k = i;
    for (int j = 1; j <= n; j++) {
        if (k) w[i][j] = w[i][j-1] + (1 << (k-1));
        else w[i][j] = w[i][j-1];
        k = f[k];
    }
}
dp[0][0] = 1;
for (int i = 0; i <= n; i++) {
    if (dp[i][ed]) return printf("%d\n", i), 0; // Output if target state is reachable at second i
    for (int j = 0; j < (1 << n); j++) {
        if (!dp[i][j]) continue;
        dp[i+1][j] = 1; // No operation added at the start
        for (int k = 1; k <= n; k++) { // Enumerate which node to operate on at the beginning
            dp[i+1][j ^ w[k][i+1]] = 1;
        }
    }
}

T2

This problem is truely tricky...

The first intuition is implicit graph construction. But how? Given that each person has a final state (learned, not learned, or indifferent), which acts as a constraint, we start from the constraints. Let maxT[i] be the earliest time person i must learn the algorithm. Formally, if t[i] is the time person i learns the algorithm, then maxT[i] ≤ t[i]. Obviously, for those who never learn (their state w[i] = -1), maxT[i] = +∞. Now consider: what if a person with w[i] ≠ -1 and a person with w[j] = -1 must have a meal in [L[k], R[k]]? The constraints can be visualized as follows:

If maxT[i] is in position ①, it means person i learns before the meal, which would cause person j to learn the algorithm regardless of the meal date, which is invalid. However, if maxT[i] is in position ②, we can schedule the meal in [L[k], maxT[i]-1], keeping both in valid states. Thus, person j imposes the constraint maxT[i] ≥ L+1. Similarly, if person i has meals with two w=-1 persons in intervals [L[k1], R[k]] and [L[k2], R[k]], then maxT[i] ≥ max(L[k1]+1, L[k2]+1).

Through this analysis, we see that w=-1 persons can constrain w≠-1 persons. Can w≠-1 persons constrain each other? Yes, but only under certain conditions. Consider the following:

If maxT[i] is in position ③, scheduling a meal between maxT[i] and R[k] allows both i and j to be valid. But if maxT[i] is in position ④, person i cannot learn during this meal, so we schedule it at L, and it imposes maxT[j] = L+1. Hence, a constraint from i to j is only meaningful when maxT[i] > R+1. Furthermore, if maxT[j] is already constrained by someone else (position ②), the current i does not impose an additional constraint. In summary, a transfer is meaningful only when maxT[j] ≤ L ≤ R < maxT[i].

This resembles Dijkstra: we repeatedly pop the largest maxT from a heap (which is already final) and use it to update others.

After this process, if maxT[1] > 0, then node 1 is constrained to learn after time 0, which conflicts with the requirement that node 1 starts learning at time 0, so we output "Impossible".

Next, we need to handle persons with w=1. They need to learn as early as possible. Let d[i] be the earliest time person i can learn. Initially, d[1] = 0, others are infinity. When i transfers to j, the constraints are:

d[j] must be at least max(d[i], L[k], maxT[j]) and at most R[k]. If maxx = max(d[i], L[k], maxT[j]) satisfies maxx ≤ R[k] and maxx < d[j], then update d[j] = maxx. If any w=1 person has d[i] = +∞, output "Impossible".

Finally, consider persons with w=0. They don't need to be checked for impossibility, but they can transmit constraints. For example, if a w=1 and a w=-1 person both have a meal with a w=0 person, the w=0 person passes the constraint from the -1 to the 1. No special treatment is needed for w=0; they are processed normally.

Core Code:

for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    if (a[i] == -1) maxT[i] = INF, q1.push({i, maxT[i]});
}
while (!q1.empty()) {
    auto [loc, val] = q1.top(); q1.pop();
    if (vis[loc]) continue;
    vis[loc] = 1;
    for (auto [v, L, R] : to[loc]) {
        if (a[v] != -1) {
            if (maxT[v] < L && R < maxT[loc]) {
                maxT[v] = L + 1;
                q1.push({v, maxT[v]});
            }
        }
    }
}
if (maxT[1] > 0) { puts("Impossible"); return 0; }
memset(d, 0x3f, sizeof d); memset(vis, 0, sizeof vis);
d[1] = 0; q2.push({1, 0});
while (!q2.empty()) {
    auto [loc, val] = q2.top(); q2.pop();
    if (vis[loc]) continue;
    vis[loc] = 1;
    for (auto [v, L, R] : to[loc]) {
        int maxx = max({d[loc], L, maxT[v]});
        if (maxx <= R && maxx < d[v]) {
            d[v] = maxx;
            q2.push({v, d[v]});
        }
    }
}
for (int i = 1; i <= n; i++) {
    if (a[i] == 1 && d[i] == INF) { puts("Impossible"); return 0; }
}
puts("JJXSM");

T3

First, consider the $\Theta(Qn)$ solution. The query must be answered in $O(len)$ time, which suggests a 1D DP or greedy. Since greedy is less extensible, we design a DP. Let dp[i][0/1] represent the minimum number of operations needed to make the prefix up to i consist of all 0s (state 0) or end with a block of consecutive 1s (state 1). The transitions are straightforward.

Core Code:

if (s[x] == '0') f[x][0] = 0, f[x][1] = 1;
else f[x][1] = 0, f[x][0] = 1;
for (int j = x + 1; j <= y; j++) {
    if (s[j] == '0') {
        f[j][0] = min(f[j-1][1] + 2, f[j-1][0]);
        f[j][1] = min(f[j-1][1] + 1, f[j-1][0] + 1);
    } else {
        f[j][0] = min(f[j-1][0] + 1, f[j-1][1] + 2);
        f[j][1] = min(f[j-1][0], f[j-1][1]);
    }
}
printf("%d\n", min(f[y][0], f[y][1] + 2));

Now, to optimize. Notice that each transition depends only on the previous index, and when s[i] is fixed, the coefficients added between states 0 and 1 are the same. Therefore, we can use a segment tree to maintain a matrix-like transition. Building and modifying are simple, but querying requires some care: we cannot directly query the matrix for [l, r]; we need to consider the value at l and combine it with the matrix for [l+1, r].

Code:

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

const int maxn = 3e5 + 10;
int n, Q;
char s[maxn];
struct Matrix {
    int mt[2][2];
    Matrix() { memset(mt, 0x3f, sizeof mt); }
    friend Matrix operator * (Matrix a, Matrix b) {
        Matrix c;
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                for (int k = 0; k < 2; k++)
                    c.mt[i][j] = min(c.mt[i][j], a.mt[i][k] + b.mt[k][j]);
        return c;
    }
};
struct Segment {
    int l, r;
    Matrix dat;
} tree[maxn << 2];
void update(int p) { tree[p].dat = tree[p<<1].dat * tree[p<<1|1].dat; }
void build(int p, int l, int r) {
    tree[p].l = l, tree[p].r = r;
    if (l == r) {
        if (s[l] == '0') {
            tree[p].dat.mt[0][0] = 0; tree[p].dat.mt[1][0] = 2;
            tree[p].dat.mt[0][1] = tree[p].dat.mt[1][1] = 1;
        } else {
            tree[p].dat.mt[0][0] = 1; tree[p].dat.mt[1][0] = 2;
            tree[p].dat.mt[0][1] = tree[p].dat.mt[1][1] = 0;
        }
        return;
    }
    int mid = (l + r) >> 1;
    build(p<<1, l, mid); build(p<<1|1, mid+1, r);
    update(p);
}
void modify(int p, int x, int val) {
    if (tree[p].l == tree[p].r) {
        if (val == 0) {
            tree[p].dat.mt[0][0] = 0; tree[p].dat.mt[1][0] = 2;
            tree[p].dat.mt[0][1] = tree[p].dat.mt[1][1] = 1;
        } else {
            tree[p].dat.mt[0][0] = 1; tree[p].dat.mt[1][0] = 2;
            tree[p].dat.mt[0][1] = tree[p].dat.mt[1][1] = 0;
        }
        return;
    }
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (x <= mid) modify(p<<1, x, val);
    else modify(p<<1|1, x, val);
    update(p);
}
Matrix query(int p, int l, int r) {
    if (l <= tree[p].l && tree[p].r <= r) return tree[p].dat;
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (r <= mid) return query(p<<1, l, r);
    if (l > mid) return query(p<<1|1, l, r);
    return query(p<<1, l, r) * query(p<<1|1, l, r);
}
int solve(int l, int r) {
    Matrix res;
    if (s[l] == '0') { res.mt[0][0] = 0; res.mt[0][1] = 1; }
    else { res.mt[0][0] = 1; res.mt[0][1] = 0; }
    if (l == r) return res.mt[0][0];
    res = res * query(1, l+1, r);
    return res.mt[0][0];
}
int main() {
    scanf("%d%s%d", &n, s+1, &Q);
    build(1, 1, n);
    for (int i = 1, opt, x, y; i <= Q; i++) {
        scanf("%d%d%d", &opt, &x, &y);
        if (opt == 1) printf("%d\n", solve(x, y));
        else { modify(1, x, y); s[x] = y + '0'; }
    }
    return 0;
}