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.
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.
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.
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.
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.
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)!
