Problem L: Optimal Random Process

Problem Statement:
Start with a random $t \in [1, n]$. Each second, either decrement $t$ by 1 or reset $t$ to a new random value in $[1, n]$. Find the minimum expected time to reach 0.

Solution:
Let $E$ be the expected time. Based on the problem constraints and linearity of expectation, we derive the formula. There exists a threshold $v$ such that for $i \le v$, we choose to decrement, and for $i > v$, we choose to reset.

The resulting expectation is $E(v) = \frac{v-1}{2} + \frac{n}{v}$. This function is convex. We find the optimal $v$ around $\sqrt{2n}$. We check integers near $\lfloor \sqrt{2n} \rfloor$ and $\lceil \sqrt{2n} \rceil$ to find the minimum.

#include 
#include 

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    long long n;
    std::cin >> n;
    long long v1 = std::sqrt(2.0 * n);
    long long v2 = v1 + 1;

    auto calc = [&](long long v) -> std::pair {
        // E = (v-1)/2 + n/v = (v^2 - v + 2n) / (2v)
        long long num = v * v - v + 2 * n;
        long long den = 2 * v;
        long long g = gcd(num, den);
        return {num / g, den / g};
    };

    auto p1 = calc(v1);
    auto p2 = calc(v2);

    // Compare p1 and p2
    // p1 < p2 iff p1.first * p2.second < p2.first * p1.second
    if ((__int128)p1.first * p2.second < (__int128)p2.first * p1.second) {
        std::cout << p1.first << " " << p1.second << "\n";
    } else {
        std::cout << p2.first << " " << p2.second << "\n";
    }
    return 0;
}

Problem G: Chip Game Probability

Problem Statement:
Two players have x and y chips. Each round has probabilities $p_0$ (Alice wins), $p_1$ (Bob wins), and $1-p_0-p_1$ (draw). Draw repeats. Winner takes loser's chips. Find probability Alice wins.

Solution:
The game can be modeled recursively. Since draws just repeat the state, effective probabilities are $P(A) = p_0 / (p_0+p_1)$ and $P(B) = p_1 / (p_0+p_1)$.

Let $f(x, y)$ be the probability Alice wins. The recursion follows the Euclidean algorithm logic:

1. If $x=y$, Alice wins with probability $P(A)$.
2. If $x
3. If $x>y$, Bob needs to win $k = \lceil (x-y)/y \rceil$ times in a row for Alice to lose. Alice wins if Bob doesn't achieve this streak.

#include 

long long power(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    for(; b; b>>=1, a=a*a%mod) if(b&1) res=res*a%mod;
    return res;
}

long long mod_inv(long long x, long long mod) {
    return power(x, mod-2, mod);
}

const int MOD = 998244353;
long long p0, p1; // Normalized probabilities

long long solve(long long x, long long y) {
    if (x == y) return p0; // Normalized p_win
    if (x < y) {
        long long k = (y - x + x - 1) / x; // ceil((y-x)/x)
        long long prob_streak = power(p0, k, MOD);
        return prob_streak * solve(x, y - k*x) % MOD;
    } else {
        long long k = (x - y + y - 1) / y; // ceil((x-y)/y)
        long long prob_streak_lose = power(p1, k, MOD);
        // Alice wins if Bob doesn't win k times, OR if Bob wins k times but eventually Alice wins?
        // The editorial says: 
        // prob Alice wins = current_prob * (1 - p1^k) + current_prob * p1^k * solve(x-ky, y)
        // Wait, if Bob wins k times, Alice loses (x-k*y chips). Game continues with Alice having x-k*y.
        long long term_lose_streak = (1 - prob_streak_lose + MOD) % MOD;
        long long term_continue = prob_streak_lose * solve(x - k*y, y) % MOD;
        return (term_lose_streak + term_continue) % MOD;
    }
}

int main() {
    long long x, y, a0, a1, b;
    std::cin >> x >> y >> a0 >> a1 >> b;
    p0 = a0 * mod_inv(a0 + a1, MOD) % MOD;
    p1 = a1 * mod_inv(a0 + a1, MOD) % MOD;
    std::cout << solve(x, y) << "\n";
    return 0;
}

Problem E: Robot Chase on Graph

Problem Statement:
Find the shortest path for a player to reach node N from node 1 on a graph while avoiding robots. Robots start at specified nodes and move randomly. The player and robots move simultaneously. If a robot can occupy the same node at the same time, the player loses.

Solution:
The problem reduces to a shortest path on a layered graph (time parity). Since robots move exactly 1 step per turn, a robot can reach node $u$ at time $t$ if and only if there's a path of length $t$ from a start node to $u$.

We use Multi-source BFS to compute $dist_{robot}[u][p]$, the minimum time for a robot to reach $u$ with parity $p$ (odd/even). If a robot starts at $u$, $dist[u][0]=0$.

Then, BFS for the player. State is $(u, p)$, meaning the player is at $u$ at a step with parity $p$. A move is valid if the new state's time ($step+1$) is strictly less than the robot's arrival time at that node with the new parity.

#include 
#include 
#include 
#include 

const int INF = 1e9;

int main() {
    int n, m, d;
    std::cin >> n >> m >> d;
    std::vector> adj(n + 1);
    for(int i=0; i> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    std::vector> robot_dist(n + 1, {INF, INF});
    std::queue> q;
    
    int k;
    std::cin >> k;
    for(int i=0; i> s;
        robot_dist[s][0] = 0;
        q.push({s, 0});
    }

    // Multi-source BFS for robots
    while(!q.empty()) {
        auto [u, p] = q.front(); q.pop();
        if(robot_dist[u][p] >= d) continue; // robots stop after d steps? No, robots move at most d steps?
        // Problem says: robots move at most d steps. Actually, "move range is d".
        // Editorial says "range d". So robots occupy nodes with dist <= d.
        // Wait, editorial says "robots move length at most d".
        for(int v : adj[u]) {
            if(robot_dist[v][p^1] == INF) {
                robot_dist[v][p^1] = robot_dist[u][p] + 1;
                q.push({v, p^1});
            }
        }
    }

    // Player BFS
    std::vector> player_dist(n + 1, {INF, INF});
    std::vector> parent(n + 1, {-1, -1});
    
    player_dist[1][0] = 0;
    q.push({1, 0});
    
    int final_parity = -1;

    while(!q.empty()) {
        auto [u, p] = q.front(); q.pop();
        if(u == n) {
            final_parity = p;
            break; 
        }
        for(int v : adj[u]) {
            if(player_dist[v][p^1] == INF) {
                int arrival_time = player_dist[u][p] + 1;
                // Safe if player arrives before robot
                // Robot has parity p^1 at this time.
                if(arrival_time < robot_dist[v][p^1]) {
                    player_dist[v][p^1] = arrival_time;
                    parent[v][p^1] = u;
                    q.push({v, p^1});
                }
            }
        }
    }
    
    if(final_parity == -1) {
        std::cout << -1 << "\n";
    } else {
        std::vector path;
        int curr = n, p = final_parity;
        while(curr != -1) {
            path.push_back(curr);
            int prev = parent[curr][p];
            p ^= 1;
            curr = prev;
        }
        std::reverse(path.begin(), path.end());
        std::cout << path.size() - 1 << "\n";
        for(int node : path) std::cout << node << " ";
        std::cout << "\n";
    }
    return 0;
}

Problem C: Dynamic Z-Function Sum

Problem Statement:
Given a sequence of operations appending character $s_i$ and values $a_i, b_i$, compute $\sum_{i=1}^n \sum_{j=i}^{i+z_i-1} a_j b_i$ dynamically.

Solution:
This problem requires a dynamic Z-function. The Z-function can be updated using properties similar to the KMP automaton. For each new character $s_i$, we maintain the Z-values for prefixes that "live" up to $i$. When a mismatch occurs (transition fails), the corresponding Z-value is finalized. We maintain a list of "failure" states to efficiently track active Z-function windows. The sum is updated based on the contribution of active $b_i$ values. A prefix sum array helps calculate the range sums quickly.

Problem K: Bipartite Matching with XOR Constraint

Problem Statement:
Count matchings of size $x$ in a bipartite graph where edge $(u, v)$ exists iff $a_u \oplus b_v \ge k$.

Solution:
Use divide and conquer on bits. For the current bit position, split nodes into two sets based on their bit value (0 or 1). The constraint $A \oplus B \ge k$ splits into cases based on the current bit of $k$.

• If $k$'s bit is 1: We must have $A \oplus B = 1$. Recurse on $(A_0, B_1)$ and $(A_1, B_0)$.
• If $k$'s bit is 0: $A \oplus B = 0$ cases require recursion ($(A_0, B_0)$, $(A_1, B_1)$) while $A \oplus B = 1$ cases are always valid edges (since higher bits decide $\ge k$). We combine these using DP and convolution to count matches.

Problem H: Subset Sum Queries on Random Points

Problem Statement:
Given random points on a plane, determine if a subset $T$ exists within a prefix rectangle $[1, a] \times [1, b]$ such that $\sum w_i \equiv c \pmod n$.

Solution:
A standard DP approach would track the minimum y-coordinate to achieve a certain modulo sum. However, with random data, the convex hull of valid subsets grows predictably. We optimize by only processing points that update the "frontier" of achievable states. Since data is random, the expected number of updates is low, leading to a complexity of $O(n \log n \log n)$.