PROBLEM LINK:Setter: Bogdan Ciobanu DIFFICULTY:MediumHard 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
EXPLANATIONThis 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.
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.
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 ComplexityTime 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 Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 13 Dec '18, 15:11
