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.