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.
I don't know how to do this part. I am also not able to understand this solution by I_love_Tanya_Romanova. Also this solution is very clean but still can't understand the last part.
Can anyone help me in this? There are also some solutions by Treaps, I would appreciate if anyone can elaborate on that too.
What if you calculate the median points Mi for every segment Li-Ri and use it as an index in some data structure (maybe Fenwick) for summing stuff? Then, for each query, you calculate the median point X of the segment A-B and every segment i that has Mi > = X should be matched with B (i.e. Ri should be matched with B); otherwise it should be matched with A (i.e. Li should be matched with A).
Just something I came up with... Maybe it's wrong, tell me what you think