Problem A

Given an n×m matrix of 0s and 1s, you can flip any submatrix. Find the minimum number of operations to create a path from the top-left corner to the bottom-right corner that only moves down or right and traverses only 0s.

(n,m\le 1000).

This is a straightforward dynamic programming problem.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
const int INF = 1 << 25;

int readInt() {
    int x = 0, w = 1;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') w = -1;
        c = getchar();
    }
    while (isdigit(c)) {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x * w;
}

bool grid[MAXN][MAXN];
int dp[MAXN][MAXN];

int main() {
    int n, m;
    n = readInt();
    m = readInt();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            grid[i][j] = readInt();

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1) {
                dp[i][j] = grid[i][j];
                continue;
            }
            int fromTop = (i > 1) ? dp[i-1][j] : INF;
            int fromLeft = (j > 1) ? dp[i][j-1] : INF;
            
            if (!grid[i][j]) {
                dp[i][j] = min(fromTop, fromLeft);
            } else {
                int costTop = (i > 1) ? dp[i-1][j] + (!grid[i-1][j]) : INF;
                int costLeft = (j > 1) ? dp[i][j-1] + (!grid[i][j-1]) : INF;
                dp[i][j] = min(costTop, costLeft);
            }
        }
    }
    printf("%d\n", dp[n][m]);
    return 0;
}

Problem B

AGC010C - Cleaning

Given a tree where each node has a value. You can repeatedly select two leaf nodes and decrease the value of every node on the path between them by 1. An operation is invalid if any node on the path has value 0. Determine if you can reduce all node values to 0.

(n\le 10^5), (0\le a_i\le 10^9).

First, handle the special case where (n=2). Then select a node with degree greater than 1 as the root.

Let (f_u) represent the number of paths that can extend upward from node (u). For leaf nodes, we have (f_u = a_u).

Let (s_u = \sum_{v \in \text{son}(u)} f_v) denote the total number of paths coming from chidlren.

Paths can either merge together or continue upward. The merged paths number (\frac{s_u - f_u}{2}), while the continuing paths number (f_u).

Since each merge consumes two paths to clear one stone, and each upward path clears one stone:

[a_u = \frac{s_u - f_u}{2} + f_u = \frac{s_u + f_u}{2}]\n This gives us:

[f_u = 2a_u - s_u]

Feasibility conditions:

• (f_u \ge 0) and (s_u \ge 0)
• (f_u \le a_u) (paths through (u) cannot exceed (a_u))
• (\frac{s_u - f_u}{2} \le s_u - \max_{v \in \text{son}(u)} f_v) — the remaining paths from children must be pairable

When (u) is the root, we additionally require (f_u = 0).

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

int readInt() {
    int x = 0, w = 1;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') w = -1;
        c = getchar();
    }
    while (isdigit(c)) {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x * w;
}

const int MAXN = 100010;
int n, degree[MAXN], root;
int head[MAXN], to[MAXN << 1], nextEdge[MAXN << 1], edgeCnt;

void addEdge(int u, int v) {
    nextEdge[++edgeCnt] = head[u];
    to[edgeCnt] = v;
    head[u] = edgeCnt;
}

ll val[MAXN], up[MAXN], childSum[MAXN], maxChild[MAXN];

void dfs(int u, int parent) {
    if (degree[u] == 1) {
        up[u] = val[u];
        childSum[parent] += up[u];
        maxChild[parent] = max(maxChild[parent], up[u]);
        return;
    }
    for (int i = head[u]; i; i = nextEdge[i]) {
        int v = to[i];
        if (v != parent) dfs(v, u);
    }
    up[u] = 2 * val[u] - childSum[u];
    childSum[parent] += up[u];
    maxChild[parent] = max(maxChild[parent], up[u]);
}

int main() {
    n = readInt();
    for (int i = 1; i <= n; i++) val[i] = readInt();
    
    for (int i = 1; i < n; i++) {
        int u = readInt(), v = readInt();
        addEdge(u, v);
        addEdge(v, u);
        degree[u]++;
        degree[v]++;
    }
    
    if (n == 2) {
        printf(val[1] == val[2] ? "YES\n" : "NO\n");
        return 0;
    }
    
    for (int i = 1; i <= n; i++)
        if (degree[i] != 1) { root = i; break; }
    
    dfs(root, 0);
    
    bool possible = true;
    for (int u = 1; u <= n; u++) {
        if (up[u] < 0 || childSum[u] < 0 || up[u] > val[u] || 
            childSum[u] - up[u] > (childSum[u] - maxChild[u]) * 2) {
            possible = false;
            break;
        }
    }
    
    if (up[root] != 0) possible = false;
    printf(possible ? "YES\n" : "NO\n");
    return 0;
}

Problem C

ARC092F - Two Faced Edges

For each directed edge in a directed graph, determine whether reversing its direction changes the number of strongly connected components.

(n\le 1000), (m\le 2\times 10^5).

Case 1: Vertices (u) and (v) are in the same SCC.

The SCC count cannot increase. The SCC might be destroyed. Reversing the edge leaves the SCC count unchanged if and only if there exists a (u \to v) path that does not use this edge.

Case 2: Vertices (u) and (v) are in different SCCs.

If there exists a (u \to v) path not containing this edge, reversing it increases the SCC count by one.

Define (f(u,v)) = 1 if (u,v) are in the same SCC, and (g(u,v)) = 1 if there exists a (u \to v) path not containing edge (u \to v).

An edge (u \to v) changes the SCC count if and only if (f(u,v) = 1) or (g(u,v) = 1).

The value (f(u,v)) can be determined by checking if a (v \to u) path exists, which can be computed with O(nm) DFS.

For (g(u,v)): For each source (u), we want to compute all (g(u,v)).

Run DFS from (u) with edge list in normal order, then run another DFS with the edge list reversed. If vertex (v) has depth exactly 1 in both DFS trees, then (g(u,v) = 0); otherwise (g(u,v) = 1).

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

int readInt() {
    int x = 0, w = 1;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') w = -1;
        c = getchar();
    }
    while (isdigit(c)) {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x * w;
}

const int MAXN = 1010;
const int MAXM = 200010;
int n, m;
int from[MAXM], to[MAXM];
vector<int> adj[MAXN];
bool inSameSCC[MAXN][MAXN], hasAltPath[MAXN][MAXN], visited[MAXN];

void forwardDFS(int u) {
    visited[u] = true;
    for (int v : adj[u])
        if (!visited[v]) forwardDFS(v);
}

void backwardDFS(int u, int root) {
    visited[u] = true;
    for (int i = adj[u].size() - 1; i >= 0; i--) {
        int v = adj[u][i];
        if (visited[v] && u == root) hasAltPath[root][v] = true;
        if (!visited[v]) backwardDFS(v, root);
    }
}

void directDFS(int u, int root) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (visited[v] && u == root) hasAltPath[root][v] = true;
        if (!visited[v]) directDFS(v, root);
    }
}

int main() {
    n = readInt();
    m = readInt();
    for (int i = 1; i <= m; i++) {
        from[i] = readInt();
        to[i] = readInt();
        adj[from[i]].push_back(to[i]);
    }
    
    for (int s = 1; s <= n; s++) {
        fill(visited, visited + MAXN, false);
        forwardDFS(s);
        for (int v = 1; v <= n; v++)
            inSameSCC[v][s] = visited[v];
        
        fill(visited, visited + MAXN, false);
        directDFS(s, s);
        fill(visited, visited + MAXN, false);
        backwardDFS(s, s);
    }
    
    for (int i = 1; i <= m; i++) {
        bool changes = (inSameSCC[from[i]][to[i]] + hasAltPath[from[i]][to[i]]) & 1;
        printf(changes ? "diff\n" : "same\n");
    }
    return 0;
}

Problem D

ARC089F - Coloring Balls

Initially there are (n) white balls. An operation sequence consists of:

• (r): choose a contiguous segment and color it red
• (b): choose a contiguous segment of red balls and color it blue

Balls may be left uncolored. Count the total number of possible final color sequences.

(n, k \le 70).

Determining if a Color Sequence is Feasible

Define the minimal operation sequence (P) for a color sequence (C) as a sequence that can produce (C) but whose no subsequence can.

Ignoring white balls and treating maximal identical color blocks as single units, red (R) and blue (B) alternate.

If there are (k) blue blocks, the minimal sequence requires exactly (k+1) operations.

For the optimal approach to perform (a) blue operations: execute one red, then (a-1) blues, color a large blue block, then apply the remaining reds on this block.

The necessary and sufficient conditions for a minimal sequence are: length (k+1), first operation is (r), second is (b), rest are unrestricted.

Now consider multiple colored intervals separated by white segments.

Excluding pure red segments, let there be (c) mixed segments. We need to select (c) disjoint subsequences from the operation sequence.

First, select (c) subsequences ({r,b}) as starting points. For each minimal sequence with (s_i) additional characters, let (t_i) be the remaining unchosen characters after the starting point.

A greedy strategy works: sort by (t_i) descending (or by starting position ascending) and take characters as far left as possible.

The feasibility condition is:

[\forall i : t_i \ge \sum_{j=i}^{c} s_j]

Note that sorting (s) in descending order is optimal.

For (a) pure red segments, take the (a) leftmost (r) operations.

DP Counting

Part 1: Counting given (a) and (c)

First, determine (t_{1\sim c}) based on (a) and (c).

The arrangement of colored segments: the number of ways to interleave (a) pure red and (c) mixed segments is (\binom{a+c}{a,c}).

For the internal ordering of mixed segments, let (c_i = \sum_j [s_j = i]). The count is (\frac{(\sum_i c_i)!}{\prod_i c_i!}).

Now consider placing balls into segments. For mixed segment (i) with (s_i):

• Total characters: (s_i + 2)
• Blue segments: (s_i + 1)
• Creates (2s_i + 1) non-empty colored segments, plus 2 empty red-capable segments at ends

Pure red segments create (a) non-empty red segments. White segments create (a+c-1) non-empty white segments, plus 2 empty white-capable segments at ends.

Total non-empty boxes: (2\sum s_i + c + 2a - 1) Total empty boxes: (2c + 2) Total balls: (n)

Answer can be computed using binomial coefficients.

Part 2: Enumerating (s) values

Let (dp_{i,j,k}) represent the number of ways to fill (s_{i\sim c}) where (\sum s = j) and (s_i = k).

The transition:

[dp_{i,j,k}=\sum_{p\ge 1}\binom{c-i+1}{p}\sum_{g<k}dp_{i+p,j-pk,g}]\n The binomial coefficient handles permutations when merging (p) copies of (k) into the current (s).

The feasibility condition (t_i \ge \sum_{j=i}^{c} s_j) translates to: (j \le t_i) and for all (p' \in [1,p]), (j - p'k \le t_{i+p'}).

The answer is (\sum dp_{1,j,k}).

This DP has complexity (O(n^4 \log n)), reducible to (O(n^3 \log n)) with prefix sum optimization.

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

int n, m, answer;
char operations[75];
int remaining[75], freq[75], whiteRem[75];
int binom[205][205];
int dp[75][45][45];
bool selected[75];

void addMod(int &x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
}

int computeWays(int mixedCount, int pureRedCount) {
    if (mixedCount == 0 && pureRedCount == 0) return 1;
    
    int processed = 0, result = 0;
    remaining[0] = 0;
    memset(selected, 0, sizeof(selected));
    memset(dp, 0, sizeof(dp));
    
    for (int i = 1; i <= m; i++) {
        if (operations[i] == 'b') continue;
        if (processed < mixedCount) {
            int pos = 0;
            processed++;
            for (int j = i + 1; j <= m; j++) {
                if (operations[j] == 'b' && !selected[j]) {
                    pos = j;
                    break;
                }
            }
            if (!pos) return 0;
            selected[i] = selected[pos] = true;
            remaining[++remaining[0]] = pos;
        } else if (processed < mixedCount + pureRedCount) {
            processed++;
            selected[i] = true;
        }
    }
    
    if (processed < mixedCount + pureRedCount) return 0;
    
    for (int i = m; i >= 1; i--)
        freq[i] = freq[i + 1] + (!selected[i]);
    
    for (int i = 1; i <= remaining[0]; i++)
        whiteRem[i] = freq[remaining[remaining[0] - i + 1]] + i;
    
    dp[0][0][0] = 1;
    
    for (int i = 0; i < remaining[0]; i++) {
        for (int j = 0; j <= whiteRem[i] && (j + pureRedCount) * 2 - 1 <= n; j++) {
            for (int k = 1; k <= j + pureRedCount; k++) {
                int base = dp[i][j][0];
                for (int l = 1; i + l <= remaining[0] && j + k * l <= whiteRem[i + l] && 
                     (j + k * l + pureRedCount) * 2 - 1 <= n; l++) {
                    addMod(dp[i + l][j + k * l][k], 
                           1LL * base * binom[i + l][l] % MOD);
                }
                addMod(base, dp[i][j][k]);
            }
        }
    }
    
    for (int i = 0; i <= whiteRem[remaining[0]] && (i + pureRedCount) * 2 - 1 <= n; i++) {
        int sum = 0;
        int nonEmpty = (i + pureRedCount) * 2 - 1;
        int empty = mixedCount * 2 + 2;
        for (int k = 0; k <= i; k++)
            addMod(sum, dp[remaining[0]][i][k]);
        addMod(result, 1LL * sum * binom[n + empty - 1][nonEmpty + empty - 1] % MOD);
    }
    
    result = 1LL * result * binom[mixedCount + pureRedCount][mixedCount] % MOD;
    return result;
}

int main() {
    scanf("%d %d %s", &n, &m, operations + 1);
    
    binom[0][0] = 1;
    for (int i = 1; i < 205; i++) {
        binom[i][0] = binom[i][i] = 1;
        for (int j = 1; j < i; j++)
            binom[i][j] = (binom[i-1][j-1] + binom[i-1][j]) % MOD;
    }
    
    answer = 0;
    for (int c = 0; c * 2 <= m; c++) {
        for (int a = 0; c * 2 + a <= m; a++)
            addMod(answer, computeWays(c, a));
    }
    
    printf("%d\n", answer);
    return 0;
}

Final score: 100 + 0 + 40 + 0 = 140 points. Problem A fully solved.