RECOVER - EDITORIAL

general
, , , , , ,
1

PROBLEM LINK:

Practice
Contest

Setter: Bogdan Ciobanu
Tester: Misha Chorniy
Editorialist: Taranpreet Singh

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Constructive Algorithms, Observations.

PROBLEM:

For Some N*N matrix, we define two Numbers to be related if manhattan distance between their positions in the matrix is either 1 or 2. We are given N and a list of such related numbers. Construct a N*N matrix having the same relations or determine if it is impossible to do so.

QUICK EXPLANATION

  • Assuming matrix exist and N > 2, there would be exactly four values which are related to exactly five values, due to being the corner of the matrix. We can fix either of them in one corner.
  • Now, We try all permutations of five vertices related to the corner we fixed, and assign them to related positions to the corner, we try to build the matrix using these six assigned values. If matrix exists, print that matrix, otherwise move to next permutation.
  • Assuming we fixed six values at corner, we assign values to positions in order of highest priority. Priority is nothing but the number of positions related to current positions which have their positions assigned. While assigning, the value to be assigned shall be the intersection of sets of related values present at all related positions.
  • Last thing, to handle base cases such as N \leq 2, we can simply print any matrix of size N*N if all values of the matrix are related as per input.

EXPLANATION

This being a constructive problem, may have multiple valid constructions. Feel free to share your construction in comments. I am sharing the construction I used to solve this problem.

Let us call the degree of a value as the number of values related to a value as per input, while the degree of a position as the number of positions, which are related to any position.

Considering a 5*5 matrix, Following is the degree of all positions in the matrix.


5 7  8  7  5
7 10 11 10 7
8 11 12 11 8
7 10 11 10 7
5 7  8  7  5

We can see, that for any fixed N, we can find the total number of relations is independent of values assigned to the matrix, just the sum of degrees of each position divided by 2. So, we can run a simple check, counting the number of values having x relations for 5 \leq x \leq max(12, y) where y is the maximum degree of any value in input and compare it with the number of values having x relations. If they differ, we are sure, that no matrix can exist with given relations.

After that, Various solutions being mirror images, rotations of a single matrix generate same relations, so, we can fix any corner and positions related to it to find an image of this matrix which shall be acceptable.

Suppose, we fix the top left corner any value related to exactly five values in the input. Now, Let us try all ways to assign values to positions related to the top left corner.


X 1 2 
3 4
5

Suppose we try all permutations of five values related to corner value and assign them to their respective positions as shown above. Now, Verify whether these six values are correctly assigned or not. This can be checked as follows.

Value at position 1 should be related only to values at positions X, 2, 3 and 4, but not 5.

Value at position 2 should be related only to values at positions X, 1 and 4, but not 4 and 5. Similar to other positions.

Also, Another validity check is to compare Number of related values to a value with the position. Taking example N = 5, Value at position 1 should have degree 7 while value at position 4 should have degree 10.

Suppose we have passed all these checks and now, want to build the whole matrix using these six values. An important observation is, that the value to be assigned at some position is always present in positions related to the current position. This means, that for assigning the value at some position, we can find candidates values for current positions being the intersection of the set of related values at positions, which are related to the current position.

Now, We just need to assign values to positions in a special order, which shall ensure that for the current position, we have already assigned sufficient positions to get exactly one valid candidate. This can be done using priority queue with tuple (priority, position) priority of each position being the Number of positions around positions which have been assigned values.

Now, if any check fails or at any time we get the candidate list to be empty, we simply try next permutation of values related to the corner. Print the matrix if we find any valid matrix.

For handling base cases like N \leq 2, we can simply print any N*N matrix with all values from 1 to N*N if all values are related in the input.

A number of constructive problems can be found here.

Soluion Complexity

Time complexity is O(N^2*LogN) per permutation for all 5! permutations per test case, logN due to priority queue operations, leading to Overall Time complexity O(N^2*logN) with a large constant per test case.

Memory Complexity should be of the order of O(N^2).

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile: