Editorial for Valentine's Day '19 S3 - Mathematical English


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.

Author: Ninjaclasher

For the first subtask, we can loop through all possible ways to split the array into at most M subarrays to assign to the groups. We can retrieve the sum of the pages for each subarray with a prefix sum array in \mathcal{O}(1).

Let sum_i be the sum of the i^{th} subarray. We can prove that it is always optimal to assign the largest sum_i to the group with the largest g_i, the second largest sum_i to the group with the second largest g_i, etc. After testing all possible ways to split the array into at most M subarrays, we can output the best answer.

Time Complexity: \mathcal{O}(N^{M-1})


For the second subtask, we can perform dynamic programming. Let dp[i][j] represent the best answer with the first i chapters and j groups. The transition is trivial, and is left as an exercise for the reader (Hint: try all possible subarrays for the current group, including the empty subarray). The answer should be in dp[N][M].

Note that this dynamic programming algorithm only considers the groups in a specific order. However, in the actual problem, the groups are unordered. Thus we need to test all permutations of the group, and run dynamic programming on each permutation. Also note that some optimizations should be utilized that are described in the first subtask. For example, you should use a prefix sum array instead of looping.

Time Complexity: \mathcal{O}(M! \cdot M \cdot N^2)


For the third subtask, we can binary search for the answer. Let mid be the current \max s_j that is tested to see whether it is possible to split the novel into up to M groups. We can greedily assign a subarray of chapters by looping until the last index which would allow s_1 \le mid. We can do the same for s_j for all 1 \le j \le M. If the entire array can be assigned, then mid is valid. Otherwise mid is invalid.

If mid is valid, we must then test a lower mid (we overshot). Otherwise, we undershot, and we must test a higher mid. We must find the location where mid is invalid, and mid+1 is valid. mid+1 is then the answer.

Note that we run into the same problem as subtask two, and all permutations of the groups must be tested.

Time Complexity: \mathcal{O}(M! \cdot M \cdot N \cdot \log K) where K is maximum possible answer (K = \sum_{i=1}^N p_i).


For the fourth subtask, we can use the same algorithm as subtask three. However, notice that instead of looping to find the subarray to assign to group j, we can binary search (again) for the maximum length subarray to assign to group i. Everything else is the same as subtask three.

Time Complexity: \mathcal{O}(M! \cdot M \cdot \log N \cdot \log K) where K is maximum possible answer (K = \sum_{i=1}^N p_i).

Note: For those that are TLEing but implementing the correct algorithm, it may help to know that division is extremely slow (around 10x slower than multiplication!), so always multiply instead of divide.

Note 2: There is an observation that could be made to reduce the M! to 2^M in the time complexity, but it is not needed for this problem.


Comments

There are no comments at the moment.