mak_0111's blog

Divide and conquer optimization
By mak_0111, history, 7 years ago, In English

I have been trying to understand dp divide and conquer optimization but I am not able to solve spoj NKLEAVES (http://www.spoj.com/problems/NKLEAVES/). How to calculate cost function C[i][j] for a bunch of leaves in O(1) time using appropriate preprocessing?

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by mak_0111 (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

Have some preprocessed arrays like this:

sum[i] = sum from right to left or sum[n] = w[n] and sum[i] = sum[i+1] + w[i]

aux[n] = w[n] and aux[i] = aux[i+1] + sum[i]

then you are able to have something like this: 1*w1 + 2*w2 + 3*w3 + 4*w4 + 5*w5... until the rightmost one. To get some part in the middle do this:

1*w1 + 2*w2 + 3*w3 + 4*w4 + 5*w5... — (1*w4 + 2*w5 + 3*w6...) — 3 * (w4 + w5 + w6...) = 1*w1 + 2*w3 + 3*w3

so C[i][j]=aux[i+1]-aux[j+1]-(j-i)*sum[j+1], this would be the cost to take all the leaves from i to j and stack them on i if I understood the problem right.

→ Reply
»
14 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone help debug the code?

Spoiler
→ Reply