Блог пользователя danhnguyen0902

Sequence Partition
Автор danhnguyen0902, 11 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Binary search?

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Could you please tell me more in details?

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        How this greedy works?

        → Ответить
        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится -11 Проголосовать: не нравится

          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.

          → Ответить
          • »
            »
            »
            »
            »
            »
            11 лет назад, # ^ |
              Проголосовать: нравится +4 Проголосовать: не нравится

            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

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              11 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              In statement was no information about subsequences should be nonempty.

              → Ответить
»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

this problem exists on spoj

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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?

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    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)

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        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)

        → Ответить
        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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!

          → Ответить
          • »
            »
            »
            »
            »
            »
            11 лет назад, # ^ |
            ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

            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 .

            → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится -10 Проголосовать: не нравится

        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 .

        → Ответить
        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          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.

          → Ответить
»
11 лет назад, # |
← Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится

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

→ Ответить