If you haven't tried the NPCAPC contest before and you want to do some kind of virtual participation, this editorial is not for you. I do not intend to spoil the questions and the contest experience.

C: Solve with friends

Solution: This problem is an easy one. You can first consider we use all by A and C first. Now, we want to consider when is it better to choose B and D instead.

B[i] + D[front] <= A[i] + C[back] Now we move stuff related to i to the left, B[i] — A[i] <= C[back] — D[front]. Now, we notice that B[i] — A[i] should be minimized. This inspires us to sort the indices concerning the values of B[i] — A[i]. Then the rest is brute force.

L: Construction of Town You want to minimize the total score (calculated with the equation that the problem has given).

Wrong idea that I've tried: You make a straight chain and just do (1, 3), (1, 4)..., (1, N), (2, 4),...

Solution: We can do (1, 2), (1, 3), (1, N). Then for each remaining edge, we can do like (2, 3), (2, 4)...(2, N), (3, 4)...

This is because we want to minimize the distances entirely. Given that X is non-decreasing, we know that the solution above is optimal.

M: Admired Person Solution: First sort the two arrays (to make sure you don't pair smaller values with large values when there is a more optimal pairing).

Then, define dp[i][j] = minimum cost that we can have after considering i numbers in array A and j numbers in array B.

dp[i][j] = min(dp[i — 1][j], dp[i — 1][j — 1] + abs(A[i] — B[j]))

If we take i and j, we come from state(i — 1, j — 1), and add the cost. If we do not take it, we come from the state(i — 1, j). The answer is dp[N][M]. However, defining all values of i, dp[i][0] = 0 is also needed.

B: Some Sum of Subset Solution: First sort the array in descending order. Then we can let dp[i][j] = number of ways we can get if we have considered i numbers and sum = j.

For each layer of DP, you can calculate the values that contribute to the answer with the respective k. First, consider only transferring those that only add A[i] to transfer (those that use A[i]), and also make sure that you perform min(M, sum) to make sure there is no overflow. Then the answer for each k is dp[i][M] * C(N — i, k). This is because we can choose an index afterwards and it does not change the outcome. Remember to add the dp values from the previous layer too after the calculations.

H: Music Game Solution: Greedy, we want to put those that are easier (as in expected time taken to pass) in front. This is optimal because if we fail in front, we can restart again and repeat. Then we want to sort by t[i] / P(fail). Since the numbers might be too big, we might need to use __int128. The rest is just calculations.

A: Welcome to NPCAPC Solution: When I observed that the value of N is so big, I immediately realized that it might be matrix exponential. The concept is like this: you have two layers of DP, and let their names be X and Y. If we want to transfer Y[9] += X[4] * 6, we can let the matrix be M[4, 9] += 6. Then, you just want to define the initial matrix then multiply it with the matrix after binary exponential.

In this case, we know the specific states that we want to go to (using the encoding 7 * i + j). Then we want to deduct it from the number of alphabets that we can use and does not affect our answer (52 initially).

In my code, I precomputed the matrices and stored them inside an array so that I didn't have to waste extra time.

I: Left Equals Right Solution: First we notice that since we must split the array in some way we can have sum on the left = sum on the right. That means that we must have an even sum to get some positive answer.

After finding the sum, let S = sum / 2. Then we can utilize a dp with the states defined as dp[i][j][k] = number of ways that we can have after considering i numbers in the list, gotten j indices, and sum = k. dp[i][j][k] = dp[i — 1][j][k] + dp[i — 1][j — 1][k — A[i]]. When we don't perform anything we automatically transfer the dp[i — 1][j][k] from the previous layer. If we take A[i], that means that we must come from the previous layer, taken j — 1, and previous sum = k — A[i]. Make sure no out-of-bounds is performed in the code.

Then the answer is simply the sum of dp[N][i][S] * (i!) * (N — i)!

K: Peace with Magic Solution: We know that we must either do + D[i] or — D[i]. This inspires us to perform a dp with the states defined as dp[i][j] = minimum score after considering i indices and current height = j. If we go up, we will go to dp[i + 1][j + D[i]] (set min with dp[i][j][k] + D[i]). If we go down, we will go to dp[i + 1][max(0, j — D[i])] (+max(0, D[i] — j)). The answer is then the minimum value in dp[N].

D: Two Box Partial solution: Let dp[i][S] = the number of ways such that after i moves the current box can have at set S. dp[i][j] += dp[i — 1][j ^ bit]. The answer is then the sum of dp[N][i]. This awards 10 points.