ivplay's blog

By ivplay, history, 5 years ago, In English

Problem Link I can think about a n^2 DP approach, But I don't know how to optimize it further :( . Any hints,plz??? Thanks in advance.

EDIT: NICE PROBLEM. SOLVED IT. WROTE A TUTORIAL ON IT. https://www.linkedin.com/pulse/beautiful-composition-data-structure-algorithm-najim-ahmed?published=t

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

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

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

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