 # Editorials of BOTM-UVCE NCode-October-2013

Practice

Contest

Author: Bharathkumar Hegde

Tester: Amogh Aithal

Editorialist: Bharathkumar Hegde

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.
``````