xuanquang1999's blog

Need help with a problem from VOI 2005
By xuanquang1999, history, 9 years ago, In English

I'm trying to solve the following problem (from VOI 2005).

Given a sequence a with n numbers, find the minimum M such that there's a way to split sequence a into k non-empty continuous subsequence and the total sum of each subsequence does not exceed M.

Constrains: 1 <= k <= n <= 15000, |ai| <= 30000, ai may be negative.

The best solution I can come up for this problem is the following O(n^2*k) DP solution:

Call f[i][k] the minimum value M for the sequence that contain first i numbers, d[i] the sum of the first i number of sequence. Then we have the following formula: f[i][k] = min(max(f[j][k-1], d[i]-d[j])) (with 0 <= j < i)

Of course, with such big constrains, this solution is not fast enough. Is there a faster solution for this? Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Ignore.

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

    That is certainly true for the case a[i] >= 0, but are you sure it work well when a[i] may be negative? (I am not sure and do not know how to prove) Update: Yeah it seems to work too.

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

    I think your algorithm may be wrong for like 4 2 4 -1 -1 4?

    for binary search m = 3, p = 3 and the program will judge answer = 3 as invalid, but actually amswer is 3

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

OK, I think I came up with the solution this time :).
Again, do a binary search on M.
Now denote dp[i] as minimum number of subsegments you can divide [1..i] in.
You can see that dp[i] = min(dp[j]) + 1 for 0 <= j < i and presum[i] — presum[j] <= M (presum[i] = a[1] + a[2] + ... + a[i])
presum[i] — presum[j] <= M can be rewritten as presum[i] — M <= presum[j].
So let's store an array best[i], which corresponds to min value of dp[j] for all j such that presum[j] = i.
We see that we only need two types of operations with our array best[]:
1. Update a value
2. Get maximum on suffix (when calculating dp[i], we are interested in indices [presum[i]-M...+inf])
This can be easily done by segment tree or BIT.
Yeah, I see that presum[i] can get really big (450M) to store in a segment tree, but you can compress all values (presum[1]..presum[n] and presum[1]-M...presum[n]-M), and use compressed indices.
Complexity is O(N*log(N)*log(Sum))

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

    If it's possible to divide the sequence to k subsequence, it's not always possible to divide the sequence into larger than k subsequence.

    For example: with M = 3 and sequence -1 5 -1, it's possible to divide the sequence into 1 subsequence (-1 5 -1), but it's not possible to divide it into 3 subsequence (-1, 5, 1).

    So, I don't think that finding minimum number of subsegments we can divide [1..n] in for a specific M would work.

    Let me know if I misunderstood your idea.

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

    I think this solution is perfect, I mean the same when compare to the standard solution discussed in here. Have you read this xuanquang1999? (Sorry for inconvenience but this link is in Vietnamese) http://vnoi.info/forum/5/4954/

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

My apology for bumping a blog from 3 years ago

Turn out, the correct solution is: Binary search M. Now we have to check if there is a way to split a into k non-empty continuous subarray such that the sum of each subarray does not exceed M.

To do this, find kmin and kmax, which are respectively the minimum and maximum k such that there is a way to split a into k non-empty continuous subsequence (this can be done by dp with segment tree). Then, a partition exist if kmin ≤ k ≤ kmax.

However, I don't know why the last statement (a partition exist if kmin ≤ k ≤ kmax) is correct. I spent about three days trying to prove this, but it did not go anywhere. Can anyone help me with this.

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

    Let's imagine between two consecutive elements of array, there is a border. There is also a border to the left of 1st element, set to Lborder and to the right of the last element, set to Rborder.

    Consider two partitions px, py which use x, y borders and x > y + 1. The borders right to the right of two Lborder is u, v respectively. Process some operations :

    If (u =  = v) set two Lborder to u, v.

    Define p the sum of element between u, v.

    If u is to the left of v

    Case 1 : p <  = M : add border u to py, set Lborder.

    Case 2 : p > M : which mean sum of all the elements between Lborder and u is  < 0, remove u from px.

    If v is to the right of u.

    Case 3 : p <  = M : same.

    Case 4 : p > M : same.

    Note that Case 1 and 2 products two partitions which use x - 1, y or x, y + 1 borders, Case 3, 4 products x + 1, y or x, y - 1 borders but eventually, all the borders of two partitions will be coincide so we can have all the partitions use all the values of borders between x, y.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 8   Vote: I like it +25 Vote: I do not like it

    Let kmin is the minimal number of segments can be divided, and there is another partition having d segments. We will try to reduce problem to smaller problem in term of pair (length_of_sequence,  d). That means firstly we reduce problem to smaller number of elements, otherwise d number of segments can be divided.

    Obviously, all segments in two partitions must be positive. Otherwise, In the d-partition, we reduce to solve problem with d  -  1. In the kmin-partition, it is because of its definition. Let (1,  x) be the first segment in kmin-partition, and (1,  y) be the first segment in d-partition.

    If x  = y: we reduce to solve smaller problem ([x  +  1,  n],  d  -  1).

    If x  <  y: sum(x  +  1,  y)  =  sum(1,  y)  -  sum(1,  x)  <  sum(1,  y)  ≤  M. So, we solve smaller problem ([x + 1,  n],  d).

    If y  <  x: similarly, sum(y + 1, x) < M. So the minimal number of segments of [y + 1, n] can be divided is  ≤ kmin. Then it is sufficient to solve smaller problem ([y + 1, n], d - 1).

    → Reply