Editorial for CCC '24 S5 - Chocolate Bar Partition


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

The first section will go over the full solution and the last paragraph will touch upon the intended solutions for some subtasks. Let the mean of the entire array be \mu. Notice that the mean of each component of a valid partition must be \mu. Now consider the transformation of A_{i,j} = T_{i,j} - \mu. This reduces the problem to splitting array A into the maximum number of parts such that each part has a sum of 0.

Now let P_{j,i} be the prefix sum array for A_j. That is,

\displaystyle P_{j,i} = \sum_{c=1}^{i} A_{j,c}

We will solve the new problem with dynamic programming. Let dp[k][i] represent the maximum number of parts we can split the first i columns of the array such that the sum of each part is 0 and there is a (possibly empty) component sticking out of the k^{\text{th}} row (row 1 or row 2). Thus, for the base case we have that dp[k][0] = 0.

We can incrementally update dp[k][i] starting from the smallest i. First set dp[k][i] to be the maximum of

  1. dp[k][i-1] (A_{k,i} is sticking out)
  2. dp[3-k][i-1] (A_{k,i} and A_{3-k,i} are in one component)
  3. dp[k][j] + 1 such that P_{3-k,j} = P_{3-k,i} and j < i (Add a "line component" from A_{3-k,j+1} to A_{3-k,i})
  4. dp[3-k][j]+1 such that P_{k,i} + P_{3-k,j} = 0 (Finish the component by cutting a chunk from the first i cells on row 3-k and the first j cells on row k)

Then if P_{1,i} +P_{2,i} = 0, simultaneously update dp[1][i] and dp[2][i] as max(dp[0][i], dp[1][i]) + 1 to signify that we split between column i and i + 1 (or we reach the end of i = N).

The final answer is dp[1][N]. To help understand how this is sufficient, it is helpful to draw out the transitions with multiple cases and notice that the sum of the component that is sticking out for dp[k][i] is P_{k,i}.

This results in an \mathcal{O}(N^2) algorithm as seen in cases 3 and 4. We can make it run in sub-quadratic time by maintaining maps of P_{k,i} \rightarrow max dp[k][i] and P_{k,i} \rightarrow max dp[3 - k][i] as we compute dp[k][i].

For the first 2 subtasks, we can generate all the possible partitions by hand for Subtask 1 or by running a clever brute force for Subtask 2. The other subtasks are used to reward suboptimal dynamic programming solutions such as using the sum of the component as a state, using the prefix of the first row and the second row simultaneously as a state or with suboptimal transitions.


Comments

There are no comments at the moment.