Editorials of BOTM-UVCE NCode-October-2013

general
, ,
1

PROBLEM LINK :

Practice

Contest

Author: Bharathkumar Hegde

Tester: Amogh Aithal

Editorialist: Bharathkumar Hegde

DIFFICULTY:

Cake Walk

PROBLEM:

There will be useful things scattered in row of 10<sup>5</sup> boxes, a bot has to move all the useful things to a single box in minimum number of moves.

QUICK EXPLANATION:

Sort the useful positions and find sum of the distances from all useful positions to an useful position which is <strong>(n/2)<sup>th</sup></strong> useful position.

EXPLANATION:

First sort all the given useful positions. Let the positions be <strong>a<sub>1</sub> < a<sub>2</sub> < a<sub>3</sub> < .... < a<sub>n</sub></strong>. Let position 
<strong>a<sub>opt</sub></strong> be the position to which all useful things are to be moved in minimum number of moves. Therefore minimum moves required is

	min_moves = (aopt - a1) + (aopt - a2) + .... (useful positions on left of aopt) 
		    + (aopt - aopt) + .... 
		    + (an-1 - aopt) + (an - aopt)  (useful positions on right of aopt) 

From the above equation it is quite clear that, if we balance the number of useful positions in right and left of a<sub>opt</sub> we can obtain the 
minimum number of moves to collect all useful things in a<sub>opt</sub>. Hence if <strong>a<sub>opt</sub> = a<sub>n/2</sub></strong> then it is possible to obtain minimum number of moves.