Hello guys :)

Today I tried to solve IOI 2015's first problem (Boxes with Souvenirs). I thought of dynamic programming:

`dp[i] = min(dp[j] + min(l, 2 * (l - pos[j + 1]), 2 * pos[i])`

( j >= i — k and j < i)

So this algo is **O(N^2)** and it time limit. My question is how to reduce it to **O(N)**.

Thanks in advance :)

You can make use of the fact that there will be

atmostone full circle in the optimal solution.If there is more than

one full-circlethen we have given2Ksouvenirs ( atmost ) and spent2Lseconds.Now say

Xof these souvenirs lie on the left semicircle andYof these souvenirs lie on the right semicircle. ( X + Y = 2K )Observe that we could have gone clockwise(for

Xitems) or anticlockwise(forYitems) and returned without completing a full circle for each case such that the sum of time taken would have been< 2L( This is because we take

Lseconds atmost for one side andL-2seconds for the other)Now try to construct two

DPs: one forclockwiseand the other foranti-clockwise.Let

DP_CW[i]= Time taken to give first 'i' teams their souvenirs moving in aclockwisedirection.DP_CW[i]=DP_CW[i-K] + ( 2 * P[i] ), if i >= KDP_CW[i]=2*P[i], otherwise.Similarly build

DP_ACW[i]for anti-clockwise direction.You can then merge these

two DPs togetherconsidering thetwocases separately . (No Full Circle and One Full Circle)This would work in time.

Code : Boxes with Souvenirs

Thanks a lot!

Lovely .. :)