MCO16502 - Editorial

dps
easy
editorial
mco16502

#1

PROBLEM LINK:

Practice
Contest

Author: Zi Song Yeoh

DIFFICULTY:

EASY

PREREQUISITES:

DYNAMIC PROGRAMMING

PROBLEM:

Split an array into k parts such that the maximum sum of a part is minimal, for all 1 \le k \le n, where n is the array size.

EXPLANATION:

First, let’s look at a slow solution. Let dp*[j] denote the answer when we consider the subarray [1..j] and divide it into i parts. Let sum(i, j) denote the sum of the values in subarray [i..j] (this can be computed in O(1) with prefix sums)

Now, the recurrence is simple. We test all possible ways to divide the last part. Thus, dp*[j] = min_{k < j}(max(dp[i - 1][k], sum(k + 1, j))). This immediately gives us an O(n^{3}) solution, which is unfortunately too slow to AC.

Another idea is to binary search the answer. We solve for each k separately. We binary search for the answer and suppose we want to check if v can be the answer. Then, we can just find the maximum number of parts we can divide the array such that each part has sum at most v greedily (with an O(n) loop). Thus, this solution is O(n^{2}\log a_{i}), which will most probably only pass up to Subtask 3.

We need to eliminate the log factor. We’ll return to the dp solution. The key is to note that we don’t have to iterate through all possible k each time. For a fixed i, the key fact is that as j increases, the minimal possible optimal value of k is non-decreasing. Thus, we can achieve an amortized O(n) complexity for each i. Thus, the total complexity is O(n^{2}).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

RELATED PROBLEMS: