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

Автор vee_sharp, история, 9 лет назад, По-английски

I am trying to solve the problem RENT on SPOJ. Here is the link http://www.spoj.com/problems/RENT/.I have done it using dynamic programming and binary search. I cant figure out what is wrong with my code.Here is a link to my code : http://ideone.com/UgnBRN . Please Help.

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Are you taking into account that if a rent ends at time t, then the next one has to start at least at time t + 1 ???

The statement says otherwise, I know, but you can't start a rent at the same time you end the previous one. The statement is incorrect.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Found my error. :) I was doing ar[mm] and sometimes it was returning mm=-1. So that was showing garbage values. Thanks a ton :)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Well I solved this problem allowing to begin a rent at the same time another ends. I guess there is no case like that in the test cases...

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      There is a test case like that in SPOJ Toolkit, but perhaps not in the official test cases. In that case, the SPOJ Toolkit solution is wrong and the problem statement is right.