Hi, I need some help in MINMAGIC problem on Codechef.
The problem statement in short: There are N segments, and Q queries. Each query is of the form (A, B). For each segment we need to choose a point on it, say X and find min(abs(A - X), abs(B - X)). We need to add this minvalue for all such segments and report the answer.
What I did: It is easy to find the answer for all segments whose right end point is less than A and whose left end point is greater than B. The minvalue is 0 for intervals that contain either A or B.
So the problem essentially boils down to this: Given 2 points (A, B) and some N segments all between A and B. For each segment we either choose its left end point or right end point and find the minvalue as above and add it for all the segments.
Can anyone help me in this? There are also some solutions by Treaps, I would appreciate if anyone can elaborate on that too.