Jury Compromise

Define dp[i][j][k] as whether it's feasible to consider the i-th candidate with a total defense score of j and prosecution score of k.

Transition: dp[i][j][k] = dp[i][j][k] OR dp[i-1][j-defense[i]][k-prosecution[i]].

After DP, enumerate absolute differences to check feasibility.

Space optimization: Let dp[j][k] represent the maximum total score (defense + prosecution) when selecting j people with a score difference of k.

Transition: dp[j][k] = max(dp[j][k], dp[j-1][k-(defense[i]-prosecution[i])] + defense[i] + prosecution[i]).

Initialize dp[0][0] = 0, others as negative infinity. Iterate j in reverse order.

To reconstruct the solution, maintain prev[j][k] tracking which candidate contributed to each state.

Handle negative k by adding an offset base.

Coins

Naptime G

Convert the circular schedule to linear. Since the first hour of sleep contributes no value, perform DP twice: once ignoring the first hour's contribution, once forcing sleep at the start.

The Least Round Way

Only factors of 2 and 5 contribute trailing zeros. Compute for each cell the count of factors of 2 and 5.

Define dp2[i][j] as minimum factor-2 count to reach cell (i,j), and dp5[i][j] similarly for factor-5.

Transition: dp2[i][j] = min(dp2[i-1][j], dp2[i][j-1]) + factor2[i][j].

Answer is min(dp2[n][n], dp5[n][n]).

If a cell contains 0, answer is at most 1 (by passing through that cell).

Reconstruct path by backtracking from the optimal dp table.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
int n, zeroRow;
int two[MAXN][MAXN], five[MAXN][MAXN];
int dp[2][MAXN][MAXN];
bool hasZero[MAXN][MAXN];

int countFactors(int x, int factor) {
    int cnt = 0;
    while (x % factor == 0) {
        cnt++;
        x /= factor;
    }
    return cnt;
}

void reconstruct(int factorType, int i, int j) {
    if (i == 1 && j == 1) return;
    if (i == 1) {
        reconstruct(factorType, i, j-1);
        cout << "R";
    } else if (j == 1) {
        reconstruct(factorType, i-1, j);
        cout << "D";
    } else if (dp[factorType][i][j] == dp[factorType][i-1][j] + (factorType == 0 ? two[i][j] : five[i][j])) {
        reconstruct(factorType, i-1, j);
        cout << "D";
    } else {
        reconstruct(factorType, i, j-1);
        cout << "R";
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int val;
            cin >> val;
            if (val == 0) {
                hasZero[i][j] = true;
                zeroRow = i;
                two[i][j] = five[i][j] = 1;
            } else {
                two[i][j] = countFactors(val, 2);
                five[i][j] = countFactors(val, 5);
            }
        }
    }
    
    for (int t = 0; t < 2; t++) {
        for (int i = 0; i <= n; i++) dp[t][i][0] = dp[t][0][i] = 1e9;
        dp[t][1][1] = (t == 0 ? two[1][1] : five[1][1]);
        for (int i = 1; i <= n; i++) {
            for (int j = (i == 1 ? 2 : 1); j <= n; j++) {
                dp[t][i][j] = min(dp[t][i-1][j], dp[t][i][j-1]) + (t == 0 ? two[i][j] : five[i][j]);
            }
        }
    }
    
    int answer = min(dp[0][n][n], dp[1][n][n]);
    if (hasZero[zeroRow][1] && answer > 1) {
        cout << "1\n";
        for (int i = 1; i < zeroRow; i++) cout << "D";
        for (int i = 1; i < n; i++) cout << "R";
        for (int i = zeroRow; i < n; i++) cout << "D";
        return 0;
    }
    
    cout << answer << "\n";
    int bestType = (dp[0][n][n] < dp[1][n][n]) ? 0 : 1;
    reconstruct(bestType, n, n);
    return 0;
}

Modular Sequence

Each number can be expressed as x/y + k*y for integer k. The sequence forms arithmetic progressions after the first element.

Compute total count of k values, then preprocess shortest sequence lengths for sums 1 to s using DP: minLen[sum] = min(minLen[sum], minLen[sum - triangular(j)] + j + 1) where triangular(j) = j*(j+1)/2.

Finally, enumerate possible starting arithmetic sequences and check if remaining sum can be formed with available length.

Time complexity: O(n√s).

A Decorative Fence

Process boards one by one. Since C can be large, use combinatorial counting with DP.

Define count[i][j][type] as number of fences with i boards where the leftmost board is the j-th smallest, and type indicates if it's higher (1) or lower (0) than the next.

Transitions:

• count[i][j][0] = Σ from p=j to i-1 of count[i-1][p][1]
• count[i][j][1] = Σ from p=1 to j-1 of count[i-1][p][0]

To find the C-th permutation, subtract counts while constructing the sequence.

Preprocessing O(n³), construction O(n²).

Windy Numbers

Digit DP with memoization:

int memo[20][20][2][2];
int digits[20];

int dfs(int pos, int last, bool tight, bool leadingZero) {
    if (pos == 0) return 1;
    if (memo[pos][last][tight][leadingZero] != -1) return memo[pos][last][tight][leadingZero];
    int limit = tight ? digits[pos] : 9;
    int total = 0;
    for (int d = 0; d <= limit; d++) {
        if (!leadingZero && abs(d - last) < 2) continue;
        total += dfs(pos-1, d, tight && (d == limit), leadingZero && (d == 0));
    }
    return memo[pos][last][tight][leadingZero] = total;
}

Tree Coloring

Convert edge contributions to overall sum. For each edge, contribution depends on number of black nodes in its subtrees.

Define dp[u][j] as maximum sum for subtree rooted at u with j black nodes.

Transition: dp[u][i] = max(dp[u][i], dp[u][i-j] + contribution + dp[v][j]) where contribution = (j*(k-j) + (size[v]-j)*(n-k-(size[v]-j))) * weight.

Time complexity: O(n²).

Jumping Houses

Binary search on coin count g. For fixed g, jump range is [max(1, d-g), d+g].

DP: score[i] = max(score[j] + value[i]) for j in range [i-R, i-L] where R = d+g, L = max(1, d-g).

Optimize with monotonic queue to O(n log V).

Charming Waltz

DP with time and position: maxDist[t][x][y] = max(maxDist[t-1][x][y], maxDist[t][x+dx][y+dy] + 1).

Optimize with roling array and monotonic queue for each direction.

Music Festival

Extract monotonic increasing sequences from each set. DP to find longest chain where each sequence's minimum exceeds previous maximum.

Optimize with BIT: sort by minimum, query maximum length for values less then current minimum, update with current maximum.

Time: O(n log n).

Xor Sequences

Construct adjacency matrix M where M[i][j] = 1 if (popcount(a[i]^a[j]) mod 3 == 0).

Initial vector V of length n with all 1s. Answer after k steps is sum of (V * M^(k-1)).

Use matrix exponentiation.

Gourmet

DP: value[time] = max(value[time - weight] + pleasure) with festival bonuses.

Since T is large, use matrix exponentiation with redefined multiplication: C[i][j] = max_k (A[i][k] + B[k][j]).

Split points into chains of length 5 to handle weights ≤ 5. Precompute matrix powers using binary lifting.

Fun Game

Two DP states: normal[step][node] for paths without explosion, exploded[step][node] for paths ending with explosion.

Transitions:

• normal[step][u] = Σ normal[step-1][v] for edges (v,u)
• exploded[step][u] = exploded[step-1][u] + normal[step-1][u]

Use matrix exponentiation with adjacency matrix.

Bear and Bowling 4