### hiddentesla's blog

By hiddentesla, history, 7 years ago,

here is a (shortened) question from one of my old national olympiad

given N and K and an array of N integers 1 and 10^6 inclusive.

partition the array into exactly K subarrays and calculate their sum. find the minimum possible difference of the maximum sum and the minimum sum.

(1<k<=n<=40)

for example for N=6 and K=3 and array={5 1 1 1 3 2}

the optimal way is to split it into [5][1 1 1][3 2] so the maximum sum is 5, minimum sum is 3 so the answer is 5-3=2.

i think the right step is to use prefix sum so pref[i] -> sum of element from 1..i

i thought about DP[pos][k][lmin][rmin][lmax][rmax] where it means the answer for subarray 1..pos where we already made k subarray and the subarray with minimum sum is in lmin..rmin and the subarray with maximum sum is in lmax..rmax. transition is O(n) so the complexity is O(n^7)

i also have an idea of fixing Lmin,Rmin,Lmax,Rmax (O(n^4)) and find if we can get K-2 subarrays from the remaining elements with the sum between (pref[Rmin]-pref[Lmin-1]) and (pref[Rmax] — pref[Lmax-1]). but i need an O(n) way to do that but it seems i cant find one (think about a greedy strategy which moves from left to right and increase cnt whent the current sum is >=min and reset sum to 0. but it does not work the cnt>k because its not certain that we can split something and keep the sum>=mn

so can i have some hints for this problem?

• +18

| Write comment?
 » 7 years ago, # |   +26 Idea of fixing Lmin, Rmin, Lmax, Rmax is the right approach, but rather than fixing indices, let's just calculate all n^2 partial sum and sort it.So, for n^4 times, we can check if given array can be partitioned with k intervals with S <= partial sum <= T. This can be done in n^3 time, so time complexity : n^7However, if (S, T) have a solution, then (S, T+1) and (S-1, T) obviously have a solution, so with two pointer, we just have to check for n^2 times. so it is reduced to n^5, which will fit in time limit.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 Can't we see whether there is a partition or not within a range of sums in N^2? Keep a dp(i, j) whether we can partition the prefix of length i in j intervals and keep some pointers for fixed j and moving i and some partial sums on dp(dp is 0 or 1). That would lead us to N^4 which is even better
•  » » » 7 years ago, # ^ |   0 Oh, the elements are all positive — I didn't noticed it. That will give n^4.
•  » » » » 7 years ago, # ^ |   0 If they weren't it'd still exist a better than N^3 solution. You can get N^2logN by keeping the partial sums of the prefixes that could be partitioned in j-1 intervals in a set. When computing a dp value, you only need to know whether you havr some i with dp(i, j-1)=1 and the partial sum in a certain range. You can easily do that on a set. Ohh and btw, if for fixed j you compute the values of dp from right to left with a preprocessing in NlogN(just one at the very beginning, not for each j), that is just sorting the partial sums, you'd get N^2logstar which is almost as good as N^2. You can use disjoint sets because computing from right to left, you just need to delete elements from the set and query the first values greater than something
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 can you please explain the n^4 approach better? i understand the N^5 one
•  » » » » 7 years ago, # ^ |   0 The maxsum state is pretty much sparse, and you could use map . so the state will be [N][K][max_sum] , use negative or something to define if max_sum isn't choosed yet.