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 = 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.

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 agoTurn out, the correct solution is: Binary search

M. Now we have to check if there is a way to splitaintoknon-empty continuous subarray such that the sum of each subarray does not exceedM.To do this, find

k_{min}andk_{max}, which are respectively the minimum and maximumksuch that there is a way to splitaintoknon-empty continuous subsequence (this can be done by dp with segment tree). Then, a partition exist ifk_{min}≤k≤k_{max}.However, I don't know why the last statement (a partition exist if

k_{min}≤k≤k_{max}) 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

Lborderand to the right of the last element, set toRborder.Consider two partitions

px,pywhich usex,yborders andx>y+ 1. The borders right to the right of twoLborderisu,vrespectively. Process some operations :If (

u= =v) set twoLbordertou,v.Define

pthe sum of element betweenu,v.If

uis to the left ofvCase 1 :

p< =M: add borderutopy, setLborder.Case 2 :

p>M: which mean sum of all the elements betweenLborderanduis < 0, removeufrompx.If

vis to the right ofu.Case 3 :

p< =M: same.Case 4 :

p>M: same.Note that Case 1 and 2 products two partitions which use

x- 1,yorx,y+ 1 borders, Case 3, 4 productsx+ 1,yorx,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 betweenx,y.Let

k_{min}is the minimal number of segments can be divided, and there is another partition havingdsegments. 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, otherwisednumber of segments can be divided.Obviously, all segments in two partitions must be positive. Otherwise, In the

d-partition, we reduce to solve problem withd- 1. In thek_{min}-partition, it is because of its definition. Let (1,x) be the first segment ink_{min}-partition, and (1,y) be the first segment ind-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 ≤k_{min}. Then it is sufficient to solve smaller problem ([y+ 1,n],d- 1).