danhnguyen0902's blog

Sequence Partition
By danhnguyen0902, 11 years ago, In English

Hi everyone,

This is one of the problems used in our National Olympiad in Informatics, and it has remained unsolved since 2005. Your help would be really appreciated! So here it is:

Given a sequence of N elements a[1], a[2], ..., a[N] and a positive number K. A partition is defined to include several consecutive elements in the original sequence. Write a program that splits the given sequence into k partitions such that the maximum sum among those partitions is minimized. Write out the desired sum.

Constraints:

  • 1 ≤ k ≤ n ≤ 15000

  • |ai| ≤ 30000

Example:

Input

9 4 (N and K)

1 1 1 3 2 2 1 3 1 (a[1], a[2], ..., a[N]

Output

5

Explain:

We can divide the original sequence into 4 partitions:

(1, 1, 1)

(3, 2)

(2, 1)

(3, 1)

The maximum sum among the partitions above is 5 (= 3 + 2), and it is the best minimum sum we can achieve while splitting the sequence into 4 partitions.

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

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

Binary search?

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

    Could you please tell me more in details?

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

      You could google what means "binary search". Then you could apply it for searching answer. You need only check if it is possible to split sequence in k subsequences with sum less than x. You could do it greedy

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

        you told the easy part ,but for each binary search iteration how to check if there's an answer?

        How this greedy works?

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

          greedy adding from left to right until sum less x or negative segment. You could precalc right ends of negative segments walking from right to left.

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            How to ensure that we used exactly K partitions?

            for example let this array that we should check if we can divide it into 2 parts with sum less than 3

            5 -3

            we can make the first part less than 3 by taking both 5 and -3 but in this case will not remain any numbers for the second partition

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

              In statement was no information about subsequences should be nonempty.

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

this problem exists on spoj

→ Reply
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Well, I found out this solution yesterday, but I don't quite understand how he used a Binary Search Tree (seems like a Treap) to handle the DP relation (step 3). Is there anybody get it?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    i dont understand greedy solution proof at all but dp solution + binary search makes sense. first use binary search for M (maximum sum) than with dp check is there a solution .

    in dp F[i] = for segment [i,N] , maxsimum K then we can calculate all F from right to left , in each step F[i] = i<j && sum(i,j)<=M max(F[j]+1) and G[i] = for segment [i,N] , minimum K in each step G[i] = i<j && sum(i,j)<=M min(G[j]+1) if F[1]>=K and G[1]<=K we can assume that there is a solution. for calculate F and G efficient use segment tree . overall complexity O(N.log N.log N)

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Can you be more specific about how to use segment tree to calculate F and G?

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

        use segment such that segment[i] = k . it means that there is j range_sum[1,j] = iand f(i) = k. so for calculate F in i.th position while iterating from right to left you can get solution from segment tree with query(sum[i]-m,inf)

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

          I'm sorry, but I'm still a little foggy about your approach. In the range_sum[1, j] = i, shouldn't i be very large? Or maybe I'm misunderstanding the way you do. Is range_sum[1, j] = a[1] + a[2] + ... + a[j]? And what is k here? Is it the k given in the input?

          Thank you!

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

            first k = how many partition , range_sum[i,j] = a[i] + a[i+1] + .. ar[j]

            second yes you are right you have to give all these number id so you compress them like that

            -5 10 1548944 10 123 434442

            then compress

            1 2 5 2 3 4 ~~~~~

            after this operation maximum element is at most N . here is implementation with segment and with fenwick . fenwick is 5 times faster than classic segment .

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

      How can you prove this statement ? " if F[1]>=K and G[1]<=K we can assume that there is a solution."

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        if all numbers were in positive just finding minimum number of partitions is enough . proof is simple we have k partitions each of them is less then M so for more partitions we can just divide them into 2 partitions so that k increase by one . if we have also negative numbers we have to calculate maxsimum k also .

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          You didn't convince me, what's the formal and general proof for the assumption you just made ? I'd like to see a formal proof.

          → Reply
»
11 years ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

OK, I got accepted with a mix of the ideas thrown in this thread. I'll explain my solution...

  • Let Ai be the ith element in the sequence.
  • Let Si be the prefix sum until element i, that is A1 + A2 + A3 + ... + AN.
  • Let sum(i, j) be Ai + A(i + 1) + ...Aj.
  • Let idx(s) be the compressed index of a certain sum s.
  • Let T(s) be node idx(s) of our segment tree.
  • First of all, we do binary search on M, and on each iteration we compress the prefix sums in the following way: Let X be an empty set, then for each i in range 1..N, we insert into X values Si and Si - M. Once we're done, we iterate through the set and keep track of what index corresponds to what sum using a map.
  • Now we determine whether it is possible to partition the sequence into K smaller sequences each with a sum <= M. To do that, we use DP + Segment Tree.
  • Each node in our segment tree will be a pair (x,y). x will indicate the minimum number k so that we can partition the whole sequence into k smaller sequences, each with sum <= M. y will indicate the maximum number k so that we can partition the whole sequence into k smaller sequences, each with sum <= M. Index i in our segment tree will contain data of nodes whose prefix sum compressed index is i.
  • Now we go through the sequence from left to right. Suppose we're at index i. We will want to know, for every index j (j < i), such that sum(j + 1, i) <  = M two indexes p and q, so that T(Sp).x is minimal and T(Sq).y is maximal. Then we will update node Si of our segment tree with values T(Sp).x + 1 and T(Sq).y + 1. We want sum(j + 1, i) to be  <  = M but sum(j + 1, i) = Si - Sj so we're looking for Si - Sj <  = M which means Sj >  = Si - M. So we will query our tree in the range Si - M, ∞.
  • Then if T(SN).x <  = K and T(SN).y >  = K, it is possible with value M. Otherwise, it is not.

If you want to check the code, see here -> C++ solution

→ Reply