You are not logged in. Please login at www.codechef.com to post your questions!

×

# MNZEQ – Editorial

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

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 NX = 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.

This question is marked "community wiki".

asked 25 Sep '18, 20:32 3436
accept rate: 21% 19.8k350498541

 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,056
×1,024
×890
×94
×83
×3

question asked: 25 Sep '18, 20:32

question was seen: 157 times

last updated: 11 Oct '18, 17:14