Voga's blog

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 ?

Full text and comments »

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