ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1105. Observers Coloring

Give me some hints, please!!!
Posted by Aleksei Zobnin 28 Sep 2002 03:34
Can this task be solved using only sorting?
Does the solution always exist?
There's always a solution.
Posted by Maigo Akisame (maigoakisame@yahoo.com.cn) 13 Oct 2004 15:50
Denote by L the total length covered by all the intervals.
First delete all those intervals that is completely contained by any other. Then sort the remaining intervals. Now put those that have odd positions into the 1st group, and those with even positions into the 2nd group. Calculate the total lengths covered by each group, and let's call them s1 and s2. If s1>=L*2/3, then the intervals in the 1st group make a solution. If s2>=L*2/3, then the intervals in the 2nd group make a solution. Otherwise, the solution should contain the intervals in both groups, which is easy to prove.

Good Luck!
Re: There's always a solution.
Posted by Xeno 19 Oct 2004 13:29
What's the so called 'odd positions' or 'even positions' please?
Re: There's always a solution.
Posted by Maigo Akisame (maigoakisame@yahoo.com.cn) 19 Oct 2004 15:05
Now you've deleted some of the intervals. Sort the rest according to either the left end or the right end. 'Odd intervals' mean those at positions 1,3,5,7,etc in the sorted sequence, and 'even intervals' mean those at positions 2,4,6,8,etc.
Re: There's always a solution.
Posted by Kit 22 Apr 2005 12:48
What for this test:
0 109
10
0 100
1 101
2 102
3 103
4 104
5 105
6 106
7 107
8 108
9 109?

Your method gives the 1st group (1, 3, 5, 7, 9) and the 2nd groop (2, 4, 6, 8, 10). The 1st does not make a solution, like the second group or join of the 1st and the 2nd. This method really works?
Sorry for my English.
Re: There's always a solution.
Posted by Denis Koshman 9 Aug 2008 21:18
The idea is almost correct. Just remove segments which are covered by SOME SUBSET of other segments. I.e. find any chain which covers entire range [T0;T1], but segments i and i+2 do not overlap.
to Kit
Posted by Rumter (2) 17 Oct 2008 20:28
 Kit 22 апреля 2005 12:48
test:
0 109
10
0 100
1 101
2 102
3 103
4 104
5 105
6 106
7 107
8 108
9 109


The right answer 0?
sorry
Posted by Rumter (2) 17 Oct 2008 21:27
sorry, I bad read statement

right answer
1
1
Test
Posted by marqueewinq 23 Nov 2011 20:27
What if segments i and i+1 haven't crossing?
Smth like that:
----
     -----
By your idea, we should divide these sectors into different groups, but it's more effectively to join 'em.