cniks117's blog

By cniks117, 11 years ago, In English

please explain me the approach to solve the problem http://mirror.codeforces.com/problemset/problem/332/B ..i read the editorial but couldnt understand the soln.. thanx in advance

Tags 332b, dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I didn't read editorial, but this is my solution :) Although, I don't think it will be different.

So your task is to find non-intersecting segments with length k and maximum possible sum. First think we can notice is, that seqments are always exactly of length k. So you can precompute sum of sequence [a, a + k - 1] for each a. This can be easily done with one traverse of array. When we knew sum for sequence [a, a + k - 1] just add element xa + k and subtract element xa and you obtain sum for sequence [a + 1, a + k].

Now we can fix some b. We know sum for [b, b + k - 1], but what about first sequence. Where is best possible a. Well, simply is the sequence [a, a + k - 1] with biggest sum and a + k - 1 < b. But we cannot process all such a, because we will get solution with time complexity O(n2).

But we can also precompute the best a for interval [0, i] for every i using dp. Again, if some Si is the biggest sum of some sequence of length k in interval [0, i], than max(Si, sum([i - k + 2, i + 1])) is answer for interval [0, i + 1]. And we already compute value of sum([i - k + 2, i + 1]) in first transition.

With all of this we just go through all possible b and pick Sb - 1 as the best position for a. You can check my implementation (with som comments) here: 4270931. Time complexity of this solution is O(n).

I hope this is clear enough. If you got any additional questions just ask :)