BABY  Baby
A baby tries to solve the wellknown eightqueen puzzle: the problem of placing eight chess queens on an 8×8 chessboard so that no two queens share the same row, column, or diagonal. The baby understands the concept of row and column quite well but diagonal is not very clear to her. As a result she succeeds placing eight queens on the board so that no two queens share the same row or column but there remains the possibility that some queens share the same diagonal.
Given baby's queens (a solution by the baby) and a valid eightqueen solution, it is possible to move baby's queens to positions of queens in the valid solution. Assume that in a single move, a queen can be moved one unit rowwise or columnwise into an unoccupied position.
Write a program to find the minimum number of moves required to move baby's queens to positions of queens in the valid solution. The program should be usable for a more general n queen puzzle where n queens are placed on an n×n chessboard, 4 ≤ n ≤ 16 . Assume that rows and columns of the chessboard are numbered 1, 2,..., n .
Input
The input consists of multiple test cases.
Each case begins with a line containing the integer n .
Each of the next two lines contains a sequence of n integers. Integers in the first line represent column numbers of baby's queens appearing in rows 1, 2,..., n respectively. In the same way, the second line contains column numbers of queens in the given valid solution. A space separates two consecutive integers in the sequence.
A line containing a zero '0' as the first character follows the last case.
Output
For each test case, print the minimum number of moves required.
Example
Sample Input 4 1 2 3 4 3 1 4 2 4 3 2 4 1 3 1 4 2 5 5 3 1 4 2 5 3 1 4 2 5 1 5 2 4 3 3 1 4 2 5 0 Sample Output 6 2 0 8
hide comments
tarungupta:
20190407 07:54:34
Since Time Limit is very less, don't take much additional space in dp matrix as initializing all with 1 can cost a TLE.


learnerinblack:
20180604 15:34:10
Hint :


enzymii:
20180314 09:44:07
Got accepted with mincostmaxflow rather than dp... 

siddharth9820:
20161226 21:26:26
Just do not use bottomup as the time limit is low.


Furquan Uddin:
20160914 08:28:23
Bottom up DP gave TLE while top down gave AC.


zoooma13:
20160814 03:36:49
For people who want an image : https://image.ibb.co/hFRBwn/BABY.png


jajusantosh:
20160617 07:54:14
will hungarian algorithm work? 

janvijay1997:
20160606 15:24:39
Take care of you DP table size to avoid TLE ! 

overflow_1378:
20160229 21:38:44
Isn't it a maximum matching problem?


sai krishna:
20160222 08:18:37
Just changed cin to scanf and got AC ;) 
Added by:  Duc 
Date:  20081209 
Time limit:  0.193s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  ACM Kanpur 2007 