final_tsu's blog

Need help with problem 830A..
By final_tsu, history, 7 years 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

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

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

→ Reply
»
7 years 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

→ Reply
  • »
    »
    7 years 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 :(

    → Reply