adsijf's blog

Someone help me with this problem please!
By adsijf, history, 4 years ago, In English

Given an array a consisting of n elements, call array b consisting of n elements such that (a[1] — b[1])^2 + (a[2] — b[2])^2 + ... + (a[n] — b[n])^2 is minimum and sum of all elements of array B is equal to m.

Given n, array A, m, find the value of (a[1] — b[1])^2 + (a[2] — b[2])^2 + ... + (a[n] — b[n])^2.

Constraints : 1 <= n <= 1e5 , 1 <= m <= 2e9, 1 <= a[i] <= 2e9

Input : first line n,m respectively, second line is the elements of array A Output : the expected value

Ex: 

Input : 3 3
        3 4 5
Output : 27
Input : 10 4
        2 3 4 5
Output : 4
  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by adsijf (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

LOGIC::

The sum of the given expression will be minimum when each part of the sum is minimum. Greater numbers have greater squares, thus we decrease the greater numbers.

CODE ::

For the given array A, select the maximum element present, then decrease the element by 1. Repeat it "m" times. LOOP Then print the sum of squares of all elements of array A.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks ^^, but actually this problem constrains is quite large, 1 <= m <= 2e9, 1 <= a[i] <= 2e9, (I've forgoten to write it in the post) Do you come up with some ideas to solve for the large m?

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The official constraints of that problem is

    1 <= n <= 1e5, 1 <= m <= 2e9, 1 <= a[i] <= 2e9

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      We here also find an array such that square of its elements is the answer. __ Take the sum of array A, __ from this minus the " m ". __ Now you have the sum of required array.

      The logic used is same as above go to bottom for explanation

      as n < 10e5, the below solution has time complexity of O(n)

      a = [Given array]

      sum_of_a = sum(a)

      sum_of_arr = (sum_of_a) — m

      a.sort()

      arr = []

      for (i=0 ; i<=len(a) ;i++)

      smallest_of _a = a[i]

required_smallest = (sum_of arr / (n-i))

if smallest_of_a < required_smallest :

    arr.append(smallest_of_a)

else:

    append required_smallest (n-i) times

      the array arr must be the answer

      calculate the sum of squares of array arr

      ******* Here we know the sum of the required array, so we just need the particular elements::

      the best case will be all elements are same and they are lesser than or equal to minimum of array A

      ** in other cases the other elements might be smaller

      ** so we append the smaller elements from array A.

      __ and we again go to try the best case for leftover (n-i) elements.

      **** Q. What have we done?

      When we get array arr, we observe that the maximum elements of A are decreased to an appropriate value and the rest of smaller elements remain same.

      if any queries feel free to ask

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks a lot, now I could understand your idea ^^

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by adsijf (previous revision, new revision, compare).

→ Reply