ICPCAM2019 Editorial (Unofficial)

As the replay contest is over those who have cracked the logic for any question or have solved it kindly share your approach along with question link and solution link.

Problem - https://www.codechef.com/AM19MOS/problems/COLINT

My approach :

The first observation is that if some range say [L,R] in which many ranges overlaps are the only one we need to consider.
else, if the whole range is does not overlaps with any other range, than we can print it with any colour and there would be no change in our answer.

Now, sort all the ranges with their starting points.
and maintain three pointers ,
MaxYellow = -1,
MaxBlue = -1,
MaxCommon = -1,

This all shows the maximum ending point of our coloured range.
MaxCommon shows the maximum ending in which before that they are coloured with yellow and blue to form green.

Now there are few cases to handle,

It will be better if i give visual, so i have written with diagram explaining cases.

My AC Submission(with comments) :
https://www.codechef.com/viewsolution/28575180

3 Likes

Thanks @anon2040365

My approach is the same as yours, but we dont need to use three max values separately: just maintain max(right end of any interval) and when adding intervals color opposite to the one with max R value.

2 Likes