tsu_'s blog

By tsu_, history, 9 days ago, In English,

Hi, 830A - Office Keys

In the above problem,the author has given a greedy solution to the problem,It was not really intuitive.. I saw some one discussing in the editorial that this problem infact can be solved with a very general DP solution.. It looks and feels like a well known DP problem,Can someone help me in solving this problem in DP way..I tried finding DP solution in submissions but was not able to..

EDIT: found one DPish solution but it does not make sense to me..28513159

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

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Sorry for the previous comment.

We need find numbers x such that

We can simulate this by repeatedly taking intersection using a set.

Take a look at my solution

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you put more detail in the above solution you are talking about...also is it a very general problem?! really disheartened that I was not able to solve it :(