TopCoder problem "Equidistance" used in SRM 281 (Division I Level Three)



Problem Statement

    

A number of items are arranged on a long shelf (infinitely long, in fact) in a retail store. Each item's position can be described with an integral offset from some fixed point on the shelf.

There seems to be no order in how the items are currently arranged on the shelf. The store management, however, wants the shelf to be as aesthetically pleasing as possible in order to attract more customers. The management chooses to rearrange the items on the shelf so that they become equidistant, meaning that the distance between each pair of adjacent items is the same. The positions of all items must remain integers after rearranging, and no two items may occupy the same position.

Moving an item requires effort, which is measured as the absolute value of the distance that an item is moved. The management wants the items to be rearranged using the minimum possible amount of total effort, where total effort is the sum of efforts required to move each item.

Given a int[] initial, the current positions of the items on the shelf, return the minimum total effort required to make the items equidistant.

 

Definition

    
Class:Equidistance
Method:minimumEffort
Parameters:int[]
Returns:long
Method signature:long minimumEffort(int[] initial)
(be sure your method is public)
    
 

Constraints

-initial will contain between 2 and 50 elements, inclusive.
-Each element of initial will be between -2,000,000,000 and 2,000,000,000, inclusive.
 

Examples

0)
    
{ 1, 4, 7, 10 }
Returns: 0
The items are already equidistant (the distance between every two adjacent items is 3) so no work needs to be done.
1)
    
{ 4, 3, 1 }
Returns: 1
Moving the element at position 4 to position 5 makes the items equidistant with an effort of 1.
2)
    
{ 3, 3, 3 }
Returns: 2
The items are initially stacked one on top of another, but we don't allow this, so we move one of the items to one side and another one to the other side.
3)
    
{ -2000000000, 2000000000 }
Returns: 0
A pair of items at different positions is always equidistant.
4)
    
{ 2, 3, 4, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18 }
Returns: 8

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=5949

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8078&pm=5949

Writer:

lovro

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Math