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.
Ignore.
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.
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
Yeah, sorry, I totally missed negative a[i]
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))
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 = 3and 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 specificMwould work.Let me know if I misunderstood your idea.
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/
Thanks, I'll read the blog someday.
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.
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.
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).