Блог пользователя rhezo

Автор rhezo, история, 8 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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