Question

People are mixed up on the first day of orientation, when they should actually be seated according to their roll number. But they can only move to an empty seat either to their left, right, front or back. If given a starting configuration, will we manage to get everyone seated roll number wise(iterated with rows given a higher priority over columns)? For simplicity, the empty seat is always the (n,n)th element of a nxn matrix. The final configuration should also leave that seat empty

Input Format

The input will consist of n^2 values. The first input gives the value of n and the subsequent (n^2 - 1) inputs correspond to the students' roll number (and their current seated position as determined by the index[0,n^2-1]. Row has a higher priority than column). The maximum value of n in the test cases is 64

Constraints

The runtime of the code in python should be under 20s and in C/C++ should be under 4s

Output Format

You need to return a single digit. 0 if the configuration can not be solved. 1 if the configuration can be solved

Sample Input 0

8 10 13 23 22 56 24 26 12 8 42 32 16 49 35 21 33 36 1 15 51 27 62 61 31 55 29 18 2 45 6 58 14 54 48 38 19 59 52 41 47 57 37 46 4 28 34 7 53 44 3 30 5 11 43 9 60 50 17 40 39 25 20 63

Sample Output 0

1

Sample Input 1

9 28 79 48 16 74 65 24 39 4 56 61 6 77 40 19 49 8 20 54 1 72 11 34 30 18 67 29 73 78 3 69 43 51 36 47 44 63 10 37 68 2 14 38 70 23 26 27 5 25 59 32 62 17 53 76 15 58 64 66 55 41 45 7 52 60 9 42 80 13 35 21 46 12 22 50 57 71 31 33 75

Sample Output 1

1

Answer 1

This puzzle is also known as sliding puzzle or 15 puzzle. It is also availabe in windows 7 desktop gadgets.

To check if the puzzle is solvable we first convert the 2d matrix in a row (we are already given input as a row). Then count the number of inversions in this row. An inversion is defined as a pair of students in which a student with greater roll number precedes another student.

For example:

3	1	2
4	5	6
8	7

This can be converted as follows

3

1

2

4

5

6

8

7

There are 3 inversion pair in the above matrix:

3 1

3 2

8 7

The result can be calculated by the formula:

1. If the grid width is odd, then the number of inversions in a solvable situation is even.
2. If the grid width is even, and the blank is on an even row counting from the bottom (second-last, fourth-last etc), then the number of inversions in a solvable situation is odd.
3. If the grid width is even, and the blank is on an odd row counting from the bottom (last, third-last, fifth-last etc) then the number of inversions in a solvable situation is even.

In our case the blank is always at the end i.e odd row. So if n is odd we need even inversions. And if n is even then also we need even inversions.

C++ code:

#include <iostream>
using namespace std;

int countInversions(int A[], int n)
{
    int inversions = 0;
    for(int i = 0; i < n - 1; i++)
        for(int j = i + 1; j < n; j++)
            if(A[i] > A[j]) {
                inversions ++;
            }
    return inversions;
}

int main()
{
    int n;  cin >> n;
    int A[n*n];
    for(int i = 0; i < n * n - 1; i++)
        cin >> A[i];
    
    int inv = countInversions(A, n*n-1);
    // if inversions are odd configuration is unsolvable
    if(inv % 2 == 1)    cout << "0";
    else                cout << "1";
}

Python Code:

def countInversions(L):
    n = len(L)
    inversions = 0
    for i in range(0, n):
        for j in range(i+1, n):
            if L[i] > L[j]:
                inversions += 1
    return inversions
    
L = [int(x) for x in input().split()]
inversions = countInversions(L[1:])

if inversions % 2 == 0:
    print("1")
else:
    print("0")

Time complexity: O(n^4). For n <= 64, it can run within the given time limits.

Screenshots:

C++ code:

Python code:

Output 1:

Output 2: