aajjbb's blog

First Gym:: Problem E
By aajjbb, 13 years ago, In English

I was not able to solve the E problem in time of the contest, I'm dealing with a wrong answer in Test 2, In my solution, I'm always looking for the nearest room, I'm wondering if this greedy approach is wrong ?


Here come's my code:

http://pastebin.com/LqnmYtaD 

How did you guys solved this problem ?

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I think that greedy approach is incorrect due to something like this:

1
2 2 200000
1 100120
100000 1
99999 1
99998 10000
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Thank you, I did not thought in this test case ? How did  you solved ? Is a Dijkstra possible ? I thought on that too, but didn't mind how to implement;
    → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution.

it's dp. for each position of new step, we looking for nearest result with less position, or wih greater or equal check both of them. 

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Nice, DP is my weak point, I was wondering states for dp for this problem to, but I didn't got the idea, thanks.
    → Reply