vee_sharp's blog

By vee_sharp, history, 9 years ago, In English

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.

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

| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.