### lol_py's blog

By lol_py, history, 6 weeks ago, You are given an array A of integers, you have to choose two integers x, y such that summation min(abs(A[i] — x), abs(A[i] — y)) for each i in 1 to N is minimised.

e.g:

A = [1, 2, 6, 7]

x = 1, y = 7

(1 — 1) + (2 — 1) + (6 — 7) + (7 — 7) = 2

2 <= N < 10^3

I tried to solve this greedily but got WA. Comments (7)
 » Can you give me link of your problem
 » 6 weeks ago, # | ← Rev. 2 →   I guess this should work:Let's consider an answer:let's sort numbers in increasing order.First part A of the numbers are going to be minimized by x, the second part B by yx is mean of A numbers, y is mean of B numbers. Otherwise we can improve answer, which is impossible for the answer ( aka the most optimal choice of x and y)Solution:1)sort numbersdo 2) for each split of the numbers in two (there will be 10^3 of them)2)divide numbers in first and second half, for each half find mean numbers which will be our x and y, calculate answer. Update optimal answer.
•  » » I think this is a counter case:61 1 1 1 1 1000Your solution will use x = 1, y = 334, when you can use x = 1, y = 1000.I was thinking in doing two ternary search one in the other in O(nlog²n), for a fixed x you can see that f(y) is convex, not sure for x, y tho.
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   Probably I explained poorly, but i meant doing this:A = {1} B = {1 1 1 1 1000}A = {1 1} B = { 1 1 1 1000}A = {1 1 1} B = { 1 1 1000}A = {1 1 1 1} B = { 1 1000}A = {1 1 1 1 1} B = {1000}And for each split find mean numbers which will be x and y. And find the best solution among them
•  » » » » Well usign the median it perhaps works, optimizing sum(abs(a[i]-x)) is when x = median, not mean, I'm not coding it if I cannot submit.
•  » » » » » Oh, I see. Median is optimal, I agree
 » 6 weeks ago, # | ← Rev. 2 →   Idea is sort the array.Then for each pair of ai,aj find the sum and take min. Here we will take x=ai,y=aj and x numbers <=x ,for them do sum+=(count of such numbers)*x-(sum of all this numbers)2> numbers which are >x but less than <(x+y)/2 do sum+=(sum of such numbers)-(count of such numbers)*x3>numbers>=(x+y)/2 and numbersfor numbers>=y do sum+=(sum of such numbers)-(count of such numbers)*y To find the sum of a range use prefix array.And since the arrya is sorted the count of numbers can be found using binary search.Time complexity O(n2logn)I hope u got the idea.Sorry for poor explanation.