## 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 subarrays to assign to the groups. We can retrieve the sum of the pages for each subarray with a prefix sum array in .

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

Time Complexity: For the second subtask, we can perform dynamic programming. Let represent the best answer with the first chapters and 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 .

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: For the third subtask, we can binary search for the answer. Let be the current that is tested to see whether it is possible to split the novel into up to groups. We can greedily assign a subarray of chapters by looping until the last index which would allow . We can do the same for for all . If the entire array can be assigned, then is valid. Otherwise is invalid.

If is valid, we must then test a lower (we overshot). Otherwise, we undershot, and we must test a higher . We must find the location where is invalid, and is valid. 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: where is maximum possible answer .

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 , we can binary search (again) for the maximum length subarray to assign to group . Everything else is the same as subtask three.

Time Complexity: where is maximum possible answer .

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 to in the time complexity, but it is not needed for this problem.