My n*log(n) idea is:

first sort all locations and then run DP.

In dp function there will be one state , say "POS" ( index of the left most location which is not included in any group ).

Then find the rightmost index of the location which can be included in the group with "POS". You can do it with binary search. Say it is "RT", then RT is right most index from POS which fullfill this condition L[RT]-L[POS]<=2*K , as problem requirement. So you can form a group From POS to RT (including all the index between them). BUT it is not obvious that it will give you the optimal solution if ,

FOR example : N = 6 , K = 3

locations : 2 5 6 8 9 10  
           index     : 1 2 3 4 5 6

for POS = 1 , RT will be = 4 . but if you form a group [1,4] then [5,6] will not be able to form any group.

So, you have to from a group from the set of [POS,RT] by removing last 0,1,2,3 locations and find the optimal result , if there is no way then nothing to do with it , just print -1.

Hi,

There is a very cool technique in this kind of problems.

In general, if you have a function like

dp(i) = min(dp(i - k), dp(i - k + 1), ... dp(i - 1)) + constant

you can use a segment tree (or similar) instead of an array in order to save the state of the dp.

Note: my solution here

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