Блог пользователя aajjbb

First Gym:: Problem E
Автор aajjbb, 13 лет назад, По-английски

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 ?

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I think that greedy approach is incorrect due to something like this:

1
2 2 200000
1 100120
100000 1
99999 1
99998 10000
→ Ответить
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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;
    → Ответить
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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. 

→ Ответить
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Nice, DP is my weak point, I was wondering states for dp for this problem to, but I didn't got the idea, thanks.
    → Ответить