CodeVita 2016 Round 2 Question: Crack the Password

Problem : Crack the Password

Statement

Atul does lots of online transactions and has accounts in multiple banks, but to remember his passwords he created his own encryption technique and wrote down the enciphered passwords in a notepad. But he finds it very time consuming to decipher those passwords so he has asked for your help to develop a program to do the task quickly.

The approach he takes to encipher is,

1. First he writes down his password in a square matrix P of dimension N, sequentially from the first element (see example for better explanation). He chooses N such that N^2 is the least number above the length of the password. He then starts filling the matrix row-wise from top to bottom. If any matrix element remains blank, he fills all those blanks with the last element e.g. if the last element filled is z then he fills all other remaining elements in the matrix by z .
2. Then he creates new matrix A of the same dimensions such that every A(i,j) = P(j,i). Next he assigns the value of the alphabet in the password to that corresponding element in the matrix. So 'a' is substituted by 1, 'b' by 2, so on. Alphabets are only lower case. Also passwords contain characters from a to z only.
3. Then he finds another matrix B such that, the solution to the following equation gives a matrix with all the elements of principal diagonal as 1 and rest as 0, which is also called the eMat( encrypted matrix ) .

Your are provided with the eMat (encrypted matrix) or the matrix B, your task is to find all possible passwords and print them. 

Example:
Let the password be "passwords" as it has 9 characters , the most appropriate matrix will be a 3X3 matrix, hence the matrix will be 

After Step 1: 

 

After step 2: 

 

After step 3: 

The eMat for the given matrix will be 

-0.78378378378		0.18918918919		0.70270270270
-0.11850311850		0.07900207900		0.09563409563
0.87733887734		-0.25155925156		-0.72557172557

Input Format:

1. First line contains integer N, which is the dimension of square matrix eMat
2. Next N lines contain N space separated values (11-digit precision after decimal point) representing the eMat.

Output Format:


In a single line print the password, if multiple password values are possible print them separated by space, sorted by ascending order of their lengths.

Constraints:

1. When eMat is converted to Matrix A, round off the numbers in the matrix A to its nearest integer value to recover the alphabets in the password

Sample Input and Output

SNo.	Input	Output
1	3 -0.78378378378 0.18918918919 0.70270270270 -0.11850311850 0.07900207900 0.09563409563 0.87733887734 -0.25155925156 -0.72557172557	passwords
2	2 0.06666666667 -0.06666666667 -0.00350877193 0.05614035088	pas pass