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

Автор FCBLOK, 10 лет назад, По-английски

I have built a brute force solution to this problem but of course time limit exceeded monster has appeared!

please can anyone explain a solution or just give a hint for this problem, i have read the editorial but i didn't understand what is written.

Problem B

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

»
10 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

You can see my solution at ....

Max[i].val is Max value of (Sum x[b]->x[b+k-1]) | if b in [i,n]. And Max[i].ind will be minimum index with this optimal Sum.

Using this you can remove second loop to find optimal b index in brute force solution. (Because if you selected index a, index b will be from [a+k] to [n])

The idea is same as editorial solution.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

You can do that:

1. Build the cumulative sum of the array (t[])

2. Go from left to right. Store in dpleft[i] the amount in the interval i, i-k. (dpleft[i] = t[i] — t[i-k])

3. Go from right to left. Store in dpright[i] the amount in the interval i, i+k. (dpright = t[i+k] — t[i])

4. Build the indexes in index left[] and index right[] and initialize with i (left) and n — i (right).

5. Go from k to n-k. If dpleft[i] > dpleft[i-1] then update indexleft[i] with i-k+1 (It means the max sum of any interval k that finishes at i from left to right, starts at position i-k+1) else update indexleft[i] with the max we have in indexleft[i-1] and update dpleft[i] with dpleft[i-1] (The previous position has the max value starting from 1 for any k interval)

6. Do the same now from right to left.

7. Go from k to n-k and take the max value of dpleft[i] + dpright[i]

This is my Solution.