Discussion @ 1105. Observers Coloring @ Timus Online Judge

Is Sample Output correct ??? I think 7th observer couldn't be alone in the room, because in the same time there was 4th observer; Otherwise there is always solution ???

Posted by hajime 29 Dec 2001 01:42

I think you should try to understand the problem correctly. Sample output is right. 2 5 7 means that we ignore observers 1 3 4 6(+)

Posted by shitty.Mishka 29 Dec 2001 02:06

Here is the explanation of the output:
3 - number of observers
2
5
7
These are the observers we shall color, and now we consider only
observers 2,5 and 7(because we are interested only in colored
observers):
2: 0.0 - 10.0
5: 9.0 - 18.0
7: 19.0 - 20.0
So, from 0.0 to 9.0 (during 9 minutes)there was only observer 2 in
the room, from 10 to 18 (during 8 minutes)- only obesver 5, and from
19 to 20 (during one minute) there was only observer 7. So, total
time is 9+8+1=18, which is not less than 2/3*(20.0-0.0)=13.3333
Of course, this output is not the only possible output for this test
case, for example my program's output is:
3
2
5
4
I hope this will help
Good luck!

So always exists solution because at every moment in the room was at least one observer.

Posted by hajime 29 Dec 2001 03:19

Well, this is not correct. There always a solution, but this is not a correct way to prove that. Email me and I could give you some hints

Posted by shitty.Mishka 29 Dec 2001 13:10

>
>

Re: Well, this is not correct. There always a solution, but this is not a correct way to prove that. Email me and I could give you some hints

Posted by Denis Koshman 9 Aug 2008 21:25

There must be EXACTLY one observer, not at least one. Segments with no colored observers at all and segments with 2+ colored observers do not count.

Discussion of Problem 1105. Observers Coloring