Avoidland - min number of steps to place n pawns so that there is only in each row and column? [closed]

Question

Avoidland is a puzzle played on an n×n board with n pawns. The pawns are initially placed on the squares of the board, at most one pawn per square. The goal is to move the pawns so that they “avoid” each other—there cannot be a row or a column with more than one pawn. In one move a pawn can move to a neighboring unoccupied square, that is, a square that shares a side with the pawn’s current location and there is no pawn on it. Given the initial locations of the pawns, what is the minimum number of moves needed to solve the puzzle?

Input The first line contains an integer n, then n lines follow. The i-th line contains the initial row and column coordinates of the i-th pawn, separated by space. Each coordinate is an integer between 1 and n. You may assume that n is at most 1000000.

Output The line contains the minimum number of moves needed to solve the puzzle.

Sample Input 1   
3
1 3
2 3
3 1

Sample Output 1
1


Sample Input 2  
4
1 4
4 1
1 1
4 4

Sample Output 2
4

My approach: The solution would require each row and column to have 1 pawn exactly. For the initial configuration, make a rightmost column which contains the sum of the number of pawns in each row. Make a bottom row which contains the sum of the number of pawns in each column. Now we need to find the minimum number of steps to make each of these arrays into all 1s and add them up but I am confused how to do that.

Answer 1

I think your approach is a great one. Once you have computed the histogram of pawns in each row/column, you can use a greedy algorithm to count the moves.

Suppose we have a 0,0,3,1 histogram that we need to change into 1,1,1,1.

It is clear that we may as well move the pawn closest to the left into the first position, the second pawn closest to the left into the second position, etc.

Therefore simply iterate through the histogram and add up the distance between the i^th pawn found and position i (where we want to place it).

e.g. in Python:

A = [0,0,3,1]

t = 0
i = 0
for pos,count in enumerate(A):
    for k in range(count):
        t += abs(pos-i)
        i += 1
print t

This prints an answer of 3, corresponding to moving one pawn left twice, and one pawn left once.

The complexity is O(n) because the inner loop is executed exactly once for each pawn.