Voga's blog

Technique to maximize min(xa+yb,xb+ya)
By Voga, history, 5 years ago, In English

https://mirror.codeforces.com/problemset/problem/1307/D

I have elements 1 to N. Each element has two values xi and yi (1<=i<=N). Now I want to choose two elements a,b such that min(xa+yb,xb+ya) is maximized. There is a naive n^2 solution to check every pair of elements. But it is possible to do it in nlogn complexity. The problem link mentioned above has the editorial that describes the method but I couldn't get it. Can anyone explain ?

  • Vote: I like it
  • -17
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Auto comment: topic has been updated by Voga (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
← Rev. 6   Vote: I like it +2 Vote: I do not like it

For a given pair of elements a and b, there are two cases, 1) xa + yb <= xb + ya ,this can be rearranged to xa — ya <= xb — yb. For pairs of elements such that xa — ya <= xb — yb we must find the maximum possible value of xa + yb. We can do this efficiently by sorting the points based on decreasing order of their (x — y) value , then as we iterate from left to right we just store the maximum y (call this y_max) value we have seen so far and update the ans with the x value of the current element + y_max. 2) xa + yb >= xb + ya: such pairs would already have been covered in the first case with a and b flipped.

→ Reply