kalimm's blog

X Zhautykov Olympiad : [Problem E] K Blocks [SOLVED]
By kalimm, 9 years ago, In English

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≤K≤min(N, 100)

http://izho.kz/2014/uploads/izho_day2_en_info.pdf

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.

  • Vote: I like it
  • +32
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +16 Vote: I do not like it

There is an O(NK) algorithm which utilizes two stacks and sweeping.

If you are interested, see this code : http://oj.uz/submission/13117

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your approach? I only know N^2*K dp approach

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +11 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I can't understand why the first observation is right.
        Array = {100,100,1}
        Now dp[2][2] = 200 and dp[2][3] = 101.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          My bad. I was confused over this problem and another problem in link. I will fix that part.

          (*Fixed.)

          → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't understand. Why does DPStack[s-1] + ArrStack[s-1] >= DPStack[s] + ArrStack[s] hold?

        → Reply
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          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.

          → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by kalimm (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Also divide and conquer optimization doesn't work for this one. Sorry about that. Fixed.

→ Reply