Daredevil666's blog

By Daredevil666, history, 13 days ago, In English

Problem — https://cses.fi/problemset/task/1163 13

I am not getting this problem. I think the sample output is incorrect!

Input: 8 3 3 6 2

Output: 5 3 3

According to the sample, the input answer should be: 5 3 2 but the sample output is 5 3 3

Demonstration:

0 1 2 3 4 5 6 7 8 ! ! ! I mean after adding 2 how the longest path without traffic light is 3 and not 2? Somebody, please help. Is there a catch that I am losing?

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it
0-2-3-6-8

6-3=3 So the longest passage is 3, not 2.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But we have put a tower on 6 so why we are also taking 6 in answer, my point is that on 4 and 5 there will not be any tower but on 6 there will be a tower and on 3 also there will be tower too

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry, I didn't understand it. Initially we have:

      0-8
      

      After adding first traffic lights at point 3:

      0-3-8
      

      Here we have the longest passage without traffic lights with length 5: 3-8. Next we add the traffic lights at point 6:

      0-3-6-8
      

      Now we have two longest passages with length 3: 0-3 and 3-6. And finally we add the traffic lights at the point 2:

      0-2-3-6-8
      

      The longest passage among all possible passages (0-2, 2-3, 3-6, 6-8) is 3-6 with the length 3. So the last answer is 3.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Got it at last. The problem is about the distance free of the traffic lights, not about the consecutive number of points free of the traffic lights and of maximum length. We can freely drive from the point 3 to the point 6 without meeting a single traffic lights.