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?
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^7
However, 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.
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
Oh, the elements are all positive — I didn't noticed it. That will give n^4.
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
can you please explain the n^4 approach better? i understand the N^5 one
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.