### kalimm's blog

By kalimm, 9 years ago,

You are given a sequence A of N positive integers. Let’s define “value of a splitting” the sequence to K blocks as a sum of maximums in each of K blocks. For given K find the minimal possible value of splittings.

1≤N≤100000, 1≤Kmin(N, 100)

There are some solutions which is N * K * log(N), like monotonic queue + segment tree. But I'm not sure about this complexity works in 1 second.

Is there any better approach?

EDIT : Thank you ko_osaga for solution, and good explanation!

Here is the code.

• +32

 » 9 years ago, # |   +16 There is an O(NK) algorithm which utilizes two stacks and sweeping.If you are interested, see this code : http://oj.uz/submission/13117
•  » » 9 years ago, # ^ |   0 Can you explain your approach? I only know N^2*K dp approach
•  » » » 9 years ago, # ^ | ← Rev. 2 →   +11 DP Formula is : dp[i][j] = Min(j < k)(dp[i-1][k] + Max(k+1,j)). Naive calculation of these can be done in O(N^2K).For further optimization, We can associate the values between Max(i,j) and dp[i][j]. DP[i-1] : [1,2,3,4,5,6,7,6,9] Array[] : [3,1,4,1,5,9,2,6,5] Max(8,9) and Max(9,9) differs, which means Array[9] can only be mapped with dp[i-1][8].Max(6,9) and Max(7,9) differs, but Max(7,9) == Max(8,9). which means Array[7 ~ 8] can be mapped with dp[i-1][6 ~ 7]. Now, my solution will model those two arrays into stacks. The element in stacks fill this conditions : DPStack[s-1] + ArrStack[s-1] >= DPStack[s] + ArrStack[s], ArrStack[s-1] >= ArrStack[s].When new DP[i-1] and Array[i] is inserted in stack, both stacks are popped while ArrStack.top() < Array[i]. While popping the values, look for the dp values popped in the stack — we should pick the smallest from the popped element, and set it as the associated values for Array[i]. (Since the value from stack is smaller than Array[i], it can be associated with Array[i].) Now, we should insert those values (Array[i] and it's associated dp) into stacks only if the values are the smallest. Since every elements are popped and inserted into stack for one time, this algorithm has linear time complexity.If you still can't understand, feel free to ask me. Also, there is a simillar problem in US Open 2012 — check it if you want to. http://www.usaco.org/index.php?page=viewproblem2&cpid=138
•  » » » » 9 years ago, # ^ |   0 I can't understand why the first observation is right. Array = {100,100,1} Now dp[2][2] = 200 and dp[2][3] = 101.
•  » » » » » 9 years ago, # ^ | ← Rev. 2 →   0 My bad. I was confused over this problem and another problem in link. I will fix that part.(*Fixed.)
•  » » » » 2 weeks ago, # ^ |   0 I don't understand. Why does DPStack[s-1] + ArrStack[s-1] >= DPStack[s] + ArrStack[s] hold?
•  » » » » » 9 days ago, # ^ |   +8 It's not like they naturally hold, but we are adding the value that only satisfies such condition. You don't need to add a value with DPStack[s-1] + ArrStack[s-1] < DPStack[s] + ArrStack[s] as it's never a better choice than s-1 when you need it.
 » 9 years ago, # |   0 Auto comment: topic has been updated by kalimm (previous revision, new revision, compare).
 » 9 years ago, # |   0 Also divide and conquer optimization doesn't work for this one. Sorry about that. Fixed.