Problem List

• [AGC034E] Complete Compress
• New Year and Original Order
• [AGC024F] Simple Subsequence Problem
• The Story of a Certain Songstress
• [POI2015] MYJ
• Periodni
• [AGC026D] Histogram Coloring
• [JOI Open 2016] Skyscraper
• [USACO19DEC] Tree Depth P
• [BZOJ3864] Hero Meet Devil
• LOJ 6274 - Numbers
• Yet Another Minimization Problem
• [USACO19FEB] Mowing Mischief P
• Modest Substrings
• [AGC022E] Median Replace

[AGC034E] Complete Compress

Since all pieces must eventually converge to a single point, we can enumerate this target point as the root and calculate the minimum operations required.

Key observation: Moving two pieces within the same subtree closer together is futile. We must always select two pieces from different subtrees and move them toward the root. Formally, select two pieces (x, y) from different subtrees, reducing their depths (dep_x, dep_y) by one. This transforms the problem into a game of piles: we have son_x piles (subtree count), and in one move, we pick two stones from two different piles. The goal is to clear all stones or report impossibility. Here, the size of the i-th pile is the sum of depths of all pieces in that subtree, denoted as dist_i.

Let f_x be the maximum number of pairs we can remove from subtree x. If dist_root % 2 == 1, it's impossible. Otherwise, two cases arise:

1. If total - max_pile >= max_pile, we can clear everything: f_x = total / 2.
2. If total - max_pile < max_pile, the largest pile must consume the others. The result is min(f_child, (2 * max_pile - total) / 2), where f_child corresponds to the subtree of the max pile.

Check for impossibility by comparing f_x with dist_x / 2.

New Year and Original Order

Direct calculation is difficult; instead, consider the contribution of each digit. The sum is ∑ (i * cnt(i)) where cnt(i) counts occurrences of digit i weighted by 10^x. Using the identity E(x) = ∑ P(x ≥ i), we simplify to: ans = ∑ ∑ cnt(j) for j from i to 9.

We perform digit DP for each digit d. Define dp[i][j][tight]: first i digits, j digits are greater than or equal to d, and tight indicates if we are matching the upper bound. Transitions involve enumerating the next digit. Since cnt(i) involves powers of 10, multiply the result by ∑ 10^i for the relevant range.

[AGC024F] Simple Subsequence Problem

Define dp[i][A][B] as the maximum number of strings in set S that are subsequences of a string of length i where matched prefix is A and available characters are B. Transitions extend B with '0' or '1'. Since storing S and T separately is heavy, concatenate them. To handle leading zeros, prepend a sentinel '1'. Proceed with standard DP transitions.

The Story of a Certain Songstress

With large n, discretization is necessary. Each constraint sets an upper limit on values within an interval. Valid positions are those where the limit equals h_i. Process DP for each distinct h_i and combine results. A useful property: if a smaller interval is contained within a larger one, the smaller can be ignored under valid conditions.

Define dp[i][j]: satisfied first i constraints, last position equal to h_i is j. Handle intersecting and non-intersecting adjacent constraints separately.

dp[0][0] = 1;
for(int i = 1, sum, res; i <= tz; i ++) {
    sum = 0, res = 1;
    for(int j = L[i - 1]; j <= R[i - 1]; j ++) sum = (sum + dp[i - 1][j]) % mod;
    gl[R[i] + 1] = 1;
    for(int j = R[i]; j >= L[i]; j --) gl[j] = (1LL * gl[j + 1] * quick_pow(x - 1, len[P[j]])) % mod;
    if(L[i] > R[i - 1]) {
        for(int j = L[i]; j <= R[i]; j ++) {
            dp[i][j] = (1LL * ((quick_pow(x, len[P[j]]) - quick_pow(x - 1, len[P[j]]) + mod) % mod * sum % mod * res) % mod * gl[j + 1]) % mod;
            res = (1LL * res * quick_pow(x, len[P[j]])) % mod;
        }
    } else {
        for(int j = L[i]; j <= R[i - 1]; j ++) dp[i][j] = (1LL * dp[i - 1][j] * gl[R[i - 1] + 1]) % mod;
        for(int j = R[i - 1] + 1; j <= R[i]; j ++) {
            dp[i][j] = (1LL * ((quick_pow(x, len[P[j]]) - quick_pow(x - 1, len[P[j]]) + mod) % mod * sum % mod * res) % mod * gl[j + 1]) % mod;
            res = (1LL * res * quick_pow(x, len[P[j]])) % mod;				
        }
    }
}
int cnt = 0;
for(int j = L[tz]; j <= R[tz]; j ++) cnt = (cnt + dp[tz][j]) % mod;
for(int i = 1; i <= tp; i ++) cnt = (1LL * cnt * (!vis[i] ? quick_pow(x, len[P[i]]) : 1LL)) % mod;
return cnt;

[POI2015] MYJ

A classic Cartesian Tree + Interval DP problem. Since a customer always goes to the cheapest wash station in their interval, add a dimension for the minimum value in the interval DP state.

Define dp[l][r][k]: maximum profit for interval [l, r] with minimum price k. Preprocess cnt[pos][val] to count how many people wash at posiiton pos if price is val. Perform standard interval DP. To reconstruct the solution, record the optimal decision point during transitions.

for(int k = 1; k <= m; k ++) {
    if(l <= a[k].a && a[k].b <= r) {
        for(int h = a[k].a; h <= a[k].b; h ++) {
            cnt[h][a[k].c] ++;
        }
    }
}
for(int k = l; k <= r; k ++)
    for(int h = lx - 1; h; h --)
        cnt[k][h] += cnt[k][h + 1];
for(int k = lx; k; k --) {
    dp[l][r][k] = dp[l][r][k + 1], Min[l][r][k] = Min[l][r][k + 1], opt[l][r][k] = opt[l][r][k + 1];
    for(int h = l; h <= r; h ++) {
        int val = dp[l][h - 1][k] + dp[h + 1][r][k] + xs[k - 1] * cnt[h][k];
        if(val >= dp[l][r][k]) dp[l][r][k] = val, opt[l][r][k] = h, Min[l][r][k] = k;
    }
}

Periodni

Another Cartesian Tree DP. Build a min-heap Cartesian tree and perform tree DP. Subtrees without ancestor relationships are independent. After building the tree, perform a tree knapsack DP.

void dfs(int node, int parent) {
    if(left[node]) dfs(left[node], node);
    if(right[node]) dfs(right[node], node);
    size[node] = size[left[node]] + size[right[node]] + 1;
    for(int i = 0; i <= size[left[node]]; i ++)
        for(int j = 0; j <= size[right[node]]; j ++)
            temp[node][i + j] = (temp[node][i + j] + (1LL * dp[left[node]][i] * dp[right[node]][j]) % mod) % mod;
    for(int i = 0; i <= size[node]; i ++)
        for(int j = 0; j <= i; j ++)
            dp[node][i] = (dp[node][i] + (1LL * (1LL * (1LL * C(size[node] - j, i - j) * C(height[node] - height[parent], i - j)) % mod * fact[i - j]) % mod * temp[node][j]) % mod) % mod;
}

[AGC026D] Histogram Coloring

Similar to the previous problem. Note: if the current row is strictly alternating (checkerboard), the next row can either invert colors or copy. Otherwise, it must invert. Record an extra state 0/1 indicating if the row is alternating.

inline LL encode(int l, int r, int opt, int d) {
    return d + 1LL * n * opt + 2LL * n * r + 2LL * n * n * l;
}

int dfs(int l, int r, int opt, int d) {
    if(l > r) return 1;
    LL state = encode(l, r, opt, d);
    if(l == r) return memo[state] = opt ? 0 : quick_pow(2, h[l] - d);
    if(memo[state]) return memo[state];
    int pivot = min_col[l][r];
    if(!opt) return memo[state] = (1LL * (1LL * dfs(l, pivot - 1, 0, h[pivot]) * dfs(pivot + 1, r, 0, h[pivot])) % mod * quick_pow(2, h[pivot] - d)) % mod;
    if(pivot == l) return memo[state] = (2LL * (dfs(l + 1, r, 0, h[pivot]) + dfs(l + 1, r, 1, h[pivot])) % mod) % mod;
    if(pivot == r) return memo[state] = (2LL * (dfs(l, r - 1, 0, h[pivot]) + dfs(l, r - 1, 1, h[pivot])) % mod) % mod;
    int res1 = (6LL * (1LL * dfs(l, pivot - 1, 0, h[pivot]) * dfs(pivot + 1, r, 0, h[pivot])) % mod) % mod;
    int res2 = (4LL * (1LL * dfs(l, pivot - 1, 0, h[pivot]) * dfs(pivot + 1, r, 1, h[pivot])) % mod) % mod;
    int res3 = (4LL * (1LL * dfs(l, pivot - 1, 1, h[pivot]) * dfs(pivot + 1, r, 0, h[pivot])) % mod) % mod;
    int res4 = (2LL * (1LL * dfs(l, pivot - 1, 1, h[pivot]) * dfs(pivot + 1, r, 1, h[pivot])) % mod) % mod;
    return memo[state] = (((res1 + res2) % mod + res3) % mod + res4) % mod;
}

[JOI Open 2016] Skyscraper

Refer to "Insertion DP" summaries.

[USACO19DEC] Tree Depth P

First, ignore depth sum and find the number of permutations of length n with exactly K inversions. Define dp[i][j]: first i numbers with j inversions. When inserting the i-th number, it creates [0, i-1] new inversions. Use prefix sums for O(n^3) optimization.

For depth sum, we count ancestors. Enumerate (u, v) where v is an ancestor of u. The contribution for a specific pair is constant. Compute the base DP array, then enumerate u-v pairs and perform a "backpack undo" operation in O(k) time. Note the order: if v comes before u, it creates 0 inversions; otherwise, v-u inversions.

void add_element(int x) {
    for(int i = 1; i <= n * (n - 1) / 2; i ++) dp[i] = (dp[i] + dp[i - 1]) % mod;
    for(int i = n * (n - 1) / 2; i > x; i --) dp[i] = (dp[i] - dp[i - x - 1] + mod) % mod;
}

void remove_element(int x) {
    for(int i = x + 1; i <= n * (n - 1) / 2; i ++) dp[i] = (dp[i] + dp[i - x - 1]) % mod;
    for(int i = n * (n - 1) / 2; i; i --) dp[i] = (dp[i] - dp[i - 1] + mod) % mod;
}

// main logic
dp[0] = 1;
for(int i = 1; i < n; i ++) add_element(i);
for(int i = 1; i < n; i ++) {
    remove_element(i);
    for(int j = i + 1; j <= n; j ++) {
        ans[j] = (ans[j] + dp[K]) % mod;
        ans[n - j + 1] = (ans[n - j + 1] + dp[n * (n - 1) / 2 - K]) % mod;
    }
    add_element(i);
}
for(int i = 1; i <= n; i ++) printf("%d ", (ans[i] + dp[K]) % mod);

[BZOJ3864] Hero Meet Devil

A classic "DP on DP" problem. First, precompute f[state][j]: given an LCS state state, what is the new state after appending character j? This runs a standard LCS calculation. Then define dp[len][state]: number of strings of length len resulting in LCS state state.

int transition(int state, int ch) {
    for(int i = 1; i <= n; i ++) aux[i] = aux[i - 1] + ((state >> (i - 1)) & 1);
    memset(cur, 0, sizeof cur);
    for(int i = 1; i <= n; i ++) {
        cur[i] = max(cur[i - 1], aux[i]);
        if(get_char(s[i]) == ch) cur[i] = max(cur[i], aux[i - 1] + 1);
    }
    int mask = 0;
    for(int i = 1; i <= n; i ++) mask += (cur[i] - cur[i - 1]) * (1 << (i - 1));
    return mask;
}

// main logic
dp[0][0] = 1;
for(int i = 0; i < m; i ++) {
    for(int j = 0; j < (1 << n); j ++) {
        for(int k = 0; k < 4; k ++) {
            dp[i + 1][f[j][k]] = (dp[i + 1][f[j][k]] + dp[i][j]) % mod;
        }
    }
}
for(int i = 0; i < (1 << n); i ++) ans[count_bits[i]] = (ans[count_bits[i]] + dp[m][i]) % mod;

LOJ 6274 - Numbers

Can be solved with "DP on DP", but a direct approach works. Define dp[pos][tx][ty][lx][ly]: at bit position pos, flags for X lower/upper bound and Y lower/upper bound. When transferring, if i & j == 0, there are three possibilities: (1,0), (1,1), (0,0). The conclusion is to take the maximum of these valid paths.

LL search(int pos, int ox1, int ox2, int oy1, int oy2) {
    if(pos < 0) return 1;
    if(f[pos][ox1][ox2][oy1][oy2] != -1) return f[pos][ox1][ox2][oy1][oy2];
    int low_x = ((Lx >> pos) & 1), low_y = ((Ly >> pos) & 1);
    int high_x = ((Rx >> pos) & 1), high_y = ((Ry >> pos) & 1);
    int target = ((T >> pos) & 1);
    LL max_val = 0, sum = 0;
    for(int i = 0; i < 2; i ++) {
        for(int j = 0; j < 2; j ++) {
            if(ox1 && i < low_x) continue;
            if(ox2 && i > high_x) continue;
            if(oy1 && j < low_y) continue;
            if(oy2 && j > high_y) continue;
            if((i | j) != target) continue;
            int nx1 = (ox1 & (i == low_x)), nx2 = (ox2 & (i == high_x));
            int ny1 = (oy1 & (j == low_y)), ny2 = (oy2 & (j == high_y));
            if(i & j) sum += search(pos - 1, nx1, nx2, ny1, ny2);
            else max_val = max(max_val, search(pos - 1, nx1, nx2, ny1, ny2));
        }
    }
    return f[pos][ox1][ox2][oy1][oy2] = sum + max_val;
}

Yet Another Minimization Problem

A standard application of Quadrilateral Inequality optimization. Use a divide-and-conquer approach combined with Mo's algorithm for the cost function.

[USACO19FEB] Mowing Mischief P

Step 1: Compute 2D LIS. Sort points by x, then find LIS on y using a Fenwick Tree (O(n log T)). Step 2: Minimize coverage area based on LIS layers. Points in the same layer have increasing x and decreasing y. Use DP with layers.

Define dp[i]: min area covering up to point i. Transition: dp[i] = min(dp[j] + (x_i - x_j) * (y_i - y_j)) where x_i >= x_j, y_i >= y_j, and lis_i = lis_j + 1. Optimize with reverse monotone decision property using a segment tree.

void optimize(int x, int l, int r, int ql, int qr, int k) {
    if(l > r || ql > qr) return;
    int mid = (l + r) >> 1, best_pos; LL best_val = LLONG_MAX;
    for(int i = ql; i <= qr; i ++) {
        LL val = dp[indices[k][i]] + 1LL * (pts[seq(x)[mid]].x - pts[indices[k][i]].x) * (pts[seq(x)[mid]].y - pts[indices[k][i]].y);
        if(val < best_val) best_val = val, best_pos = i;
    }
    dp[seq(x)[mid]] = min(dp[seq(x)[mid]], best_val);
    optimize(x, l, mid - 1, best_pos, qr, k);
    optimize(x, mid + 1, r, ql, best_pos, k);
}

Modest Substrings

Brute force would insert all strings in [L, R] into an AC automaton, but this is inefficient. Note that if we are at prefix "11_", further digits don't need to be in the automaton as the number is already valid. Build the automaton based on this logic. Precompute g[i][j]: max weight achievable from node i after j steps. Use prefix sums for DP optimization. To output the solution, backtrack the DP states.

[AGC022E] Median Replace

Without '?', determine if a 01-string can become '1'. Maintain a stack: if '0' and top has two '0's, merge to one '0'. If '1' and top is '0', remove the pair. Otherwise, push. The final stack is 1-2 '1's followed by 0-2 '0's. If there are 3 '0's (11100), they can merge to '1'. Thus, compress counts to 0-2 for both digits. The stack is valid if ones > zeros.

DP state: dp[i][ones][zeros] for first i chars. For fixed chars, transfer based on stack rules; for '?', try both 0 and 1.