Editorial for CCC '24 S5 - Chocolate Bar Partition
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 . Notice that the mean of each component of a valid partition must be . Now consider the transformation of . This reduces the problem to splitting array into the maximum number of parts such that each part has a sum of .
Now let be the prefix sum array for . That is,
We will solve the new problem with dynamic programming. Let represent the maximum number of parts we can split the first columns of the array such that the sum of each part is and there is a (possibly empty) component sticking out of the row (row or row ). Thus, for the base case we have that .
We can incrementally update starting from the smallest . First set to be the maximum of
- ( is sticking out)
- ( and are in one component)
- such that and (Add a "line component" from to )
- such that (Finish the component by cutting a chunk from the first cells on row and the first cells on row )
Then if , simultaneously update and as to signify that we split between column and (or we reach the end of ).
The final answer is . 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 is .
This results in an algorithm as seen in cases and . We can make it run in sub-quadratic time by maintaining maps of max and max as we compute .
For the first subtasks, we can generate all the possible partitions by hand for Subtask or by running a clever brute force for Subtask . 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