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.

Can you give me link of your problem

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 y

x 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 numbers

do 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:

6

1 1 1 1 1 1000

Your 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.

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

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<y(note it is usless to assign x or y some other value than ai or aj);

To find sum for each pair u can use binary search like this:

There can be four different type of numbers:

1> 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)*x

3>numbers>=(x+y)/2 and numbers<y do sum+=(count of such numbers)*y-(sum of such numbers)

4>for 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.