By adsijf, history, 4 weeks ago,

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

• -5

 » 4 weeks ago, # |   0 Auto comment: topic has been updated by adsijf (previous revision, new revision, compare).
 » 4 weeks ago, # |   +19 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.
•  » » 4 weeks ago, # ^ |   0 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?
•  » » 4 weeks ago, # ^ |   0 The official constraints of that problem is 1 <= n <= 1e5, 1 <= m <= 2e9, 1 <= a[i] <= 2e9
• »
»
»
4 weeks ago, # ^ |
+8

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

## __ 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

•  » » » » 4 weeks ago, # ^ |   0 Thanks a lot, now I could understand your idea ^^
 » 4 weeks ago, # |   -8 It appears you can use Lagrange multipliers for this. The concept applies here, and I'm sure you can convert it into actual working code.
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by adsijf (previous revision, new revision, compare).