speedster's blog

SPOJ problem PICAD
By speedster, history, 9 years ago, In English

I have been trying to solve This problem unable to do it i looked at the solution but can't understand how this why is taking a factor of 2 helping ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Indeed, multiplying everything by 2 helps because you can make each person enter at an even time and leave at an odd time, so you don't have to worry about what to count first.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    can you give me a case where marking [a +1] [b+1 -1] fails. And thank you tenshi_kanade you always help people out :)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      There are many tricky cases in this problem. For example, try the following out...

      7 7 4 4 6 4 7 4 8 4 9

      Answer in this case is 3 3.

      Another one...

      10 15 3 10 15 10 15 10 15.

      Here, the answer is 3 3 too.

      → Reply