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

×

MNZEQ – Editorial

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 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, 20:32

horsbug98's gravatar image

4★horsbug98
3236
accept rate: 21%

edited 11 Oct, 17:14

admin's gravatar image

0★admin ♦♦
19.6k349497539

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×992
×969
×860
×75
×75
×3

question asked: 25 Sep, 20:32

question was seen: 105 times

last updated: 11 Oct, 17:14