lol_py's blog

By lol_py, history, 19 months ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
19 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Can you give me link of your problem

»
19 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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.

  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      19 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          19 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh, I see. Median is optimal, I agree

»
19 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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.