MNZEQ – Editorial

general
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Arkapravo Ghosh
Tester: Arkapravo Ghosh
Editorialist: Arkapravo Ghosh

DIFFICULTY:

EASY

PREREQUISITES:

Maths, Greedy, Binary Search

PROBLEM:

Given N numbers a1, a2, a3, … , aN, you need to find the value X such that the result of the expression (a1 – X)2 + (a2 – X)2 + (a3 – X)2 + … + (aN – X)2 is minimum possible. If multiple answers are there, you need to output the maximum one.

QUICK EXPLANATION:

We can simplify the expression that we need to minimize. The expression can be written as (a12 + a22 + a32 + … + aN2) – 2X(a1 + a2 + a3 + … + aN) + NX2. We can denote the term (a1 + a2 + a3 + … + aN) as S. Now applying calculus to find the minimum value of the equation, we get -2* S + 2* N*X = 0. Hence X = S/N. If two values exist(ie. if X = *.50), then we need to output the maximum one(i.e. ceil(X)).

We can also solve this problem by applying binary search. We can see that for the given condition to be satisfied, the value of X should lie between the minimum value and the maximum value in the given array. So we can do a binary search in the range of the minimum value and maximum value and find the required result. Again we need to output the maximum one in case two values exist.

EXPLANATION:

The given expression can be written as (a12 + a22 + a32 + … + aN2) – 2* X* (a1 + a2 + a3 + … + aN) + N* X^2(eq. 1). We can denote the term (a1 + a2 + a3 + … + aN) as S. Now we apply calculus to find the minimum value of the equation. By differentiating, we get -2* S + 2* N* X(eq. 2). Again differentiating eq. 2, we get 2* N which is > 0. Hence we get the minimum value of eq. 1 by solving eq 2. Now equating eq. 2 with 0, we get, X = S/N. If two values exist(ie. if X%1 = 0.50), then we need to output the maximum one(i.e. ceil(X)).

We can also apply binary search as explained before. Here binary search will work because the value of X will lie between the minimum and maximum value, and also by intuition we can understand.
Here is a link to a binary search solution submitted by a contestant souradeep1999 :- link

AUTHOR’S AND EDITORIALIST’S SOLUTIONS:

Author’s and editorialist’s solution can be found here.