Observe that after performing operations of type 1 and type 2, the grid is in the following form: there are permutations $p_1,\ldots,p_N$ and $q_1,\ldots,q_N$ such that the integer at row $i$ and column $j$ equals $p_i+q_j$.
Operations of type 3 will relabel the integers in the cells. Our task is now to find $p_1,\ldots,p_N$ and $q_1,\ldots,q_N$ so that $p_i+q_j$ is the same as the given table up to relabeling.
Now, if $p_1,\ldots,p_N$ and $q_1,\ldots,q_N$ yield a valid answer, then $N+1-p_1,\ldots,N+1-p_N$ and $N+1-q_1,\ldots,N+1-q_N$ also yield a valid answer. This corresponds to replacing each cell with value $x$ with value $2N+2-x$. Thus, for $N>1$, there are always at least two possible answers. The full solution below will show that there can be no other answers.
Subtask 1 $N\le 6$
We can brute force all permutations $p_1,\ldots,p_N$ and all permutations $q_1,\ldots,q_N$, and check if the result is valid. We then take the lexicographically minimum valid answer.
This solution takes $\mathcal{O}(N!^2\cdot N^2)$.
Daniel Zhang's Python code:
import itertools N = int(input()) arr = [[int(x) for x in input().split()] for i in range(N)] # arr consists of numbers 2,3,...,2N each at least once. # candidate consists of numbers 2,3,...,2N each at least once. # This function checks that every instance of integer x in candidate maps to the same value in arr. # Since arr and candidate have the same number of distinct integers, # this is enough to ensure that they are relabelings of each other. def is_valid(candidate): label = [None]*(2*N+1) for i in range(N): for j in range(N): if label[candidate[i][j]] is None: label[candidate[i][j]] = arr[i][j] if label[candidate[i][j]] is not arr[i][j]: return False return True best = None for ps in itertools.permutations(range(1,N+1)): for qs in itertools.permutations(range(1,N+1)): candidate = [[ps[i]+qs[j] for j in range(N)] for i in range(N)] if is_valid(candidate): if best is None or candidate < best: best = candidate for line in best: print(" ".join(map(str,line)))
Subtask 2 $N\le 8$
We brute force all possible permutations of rows $p_1,\ldots,p_N$ (type 1 operations).
Suppose we guessed correctly and undid the permutation. The first two rows of the table would look like
2 3 4 ... N 3 4 5 ... N+1with columns permuted (type 2 operations), and integers relabeled (type 3 operations)
Now, before type 3 operations, 2 is the only number appearing in the first row but not the second row, 3 is the number in the second row belonging to the 2 in the first row, 4 is the number in the second row belonging to the 3 in the first row, and so on. From this, we can determine $q_1,\ldots,q_N$.
Among all our guesses for $p_1,\ldots,p_N$ and $q_1,\ldots,q_N$, we check if it is valid, and take the lexicographically minimal solution.
This solution takes $\mathcal{O}(N!\cdot N^2)$. A more careful analysis of the below implementation shows it is actually $O(N!\cdot N)$.
Daniel Zhang's Python code:
import itertools N = int(input()) arr = [[int(x) for x in input().split()] for i in range(N)] if N == 1: print(2) exit() # arr consists of numbers 2,3,...,2N each at least once # candidate consists of numbers 2,3,...,2N each at least once # This function checks that every instance of integer x in candidate maps to the same value in arr def is_valid(candidate): label = [None]*(2*N+1) for i in range(N): for j in range(N): if label[candidate[i][j]] is None: label[candidate[i][j]] = arr[i][j] if label[candidate[i][j]] is not arr[i][j]: return False return True best = None for pinv in itertools.permutations(range(0,N)): where0 = [None]*(2*N+1) where1 = [None]*(2*N+1) for j in range(N): where0[arr[pinv[0]][j]] = j where1[arr[pinv[1]][j]] = j qinv = [] for v in range(N*2+1): if where0[v] is not None and where1[v] is None: qinv.append(where0[v]) # At this point, qinv contains all integers in row pinv[0] that are not in row pinv[1] if len(qinv) != 1: continue # There is exactly one integer in row pinv[0] that is not in row pinv[1] # These two rows look like # 2 3 4 ... N # 3 4 5 ... N+1 # under some permutation of columns, and relabeling of integers for j in range(N): qinv.append(where0[arr[pinv[1]][qinv[j]]]) ps = [0]*N qs = [0]*N for j in range(N): ps[pinv[j]] = j+1 qs[qinv[j]] = j+1 candidate = [[ps[i]+qs[j] for j in range(N)] for i in range(N)] if is_valid(candidate): if best is None or candidate < best: best = candidate for line in best: print(" ".join(map(str,line)))
Subtask 3 $N\le 100$
Observe that row $i$ and row $j$ will have $N-1$ integers in common if and only if $|p_i-p_j|=1$.
The graph on vertices $1,\ldots,N$ with an edge between $i$ and $j$ if row $i$ and row $j$ have $N-1$ integers in common is a path, and the ordering of vertices on this path determines two possibilities for $p_1,\ldots,p_N$ (corresponding to traversing the path in two directions).
We can do the same to determine two possibilities for $q_1,\ldots,q_N$.
We can check all four candidate answers and take the lexicographical minimum of the valid ones.
This solution takes $\mathcal{O}(N^3)$.
Daniel Zhang's Python code:
import itertools N = int(input()) arr = [[int(x) for x in input().split()] for i in range(N)] # arr consists of numbers 2,3,...,2N each at least once # candidate consists of numbers 2,3,...,2N each at least once # This function checks that every instance of integer x in candidate maps to the same value in arr def is_valid(candidate): label = [None]*(2*N+1) for i in range(N): for j in range(N): if label[candidate[i][j]] is None: label[candidate[i][j]] = arr[i][j] if label[candidate[i][j]] is not arr[i][j]: return False return True def get_ps(arr): adj = [[] for i in range(N)] for i1 in range(N): for i2 in range(i1+1,N): if len(set(arr[i1]) & set(arr[i2])) == N-1: adj[i1].append(i2) adj[i2].append(i1) res = [] for i in range(N): if len(adj[i]) <= 1: pinv = [i] for j in range(N): for k in adj[pinv[j]]: if k not in pinv: pinv.append(k) ps = [None]*N for j in range(N): ps[pinv[j]] = j+1 res.append(ps) return res pss = get_ps(arr) qss = get_ps([[arr[j][i] for j in range(N)] for i in range(N)]) best = None for ps in pss: for qs in qss: candidate = [[ps[i]+qs[j] for j in range(N)] for i in range(N)] if is_valid(candidate): if best is None or candidate < best: best = candidate for line in best: print(" ".join(map(str,line)))
Full solution
For each integer, count the number of times it occurs in the table. Note that the frequency of the integer in a cell is preserved under relabelings (type 3 operations). We will use this to determine its value before relabelings.
Consider what the table looks like before type 3 operations.
There will be two integers that appear exactly once: $2$ and $2N$. If $2$ is in row $i$ column $j$, then $p_i=1$ and $q_j=1$. Then, the numbers in row $i$ must be $1+1,1+2,1+3,\ldots,1+N$ in some order. These have frequencies $1,2,\ldots,N$ respectively, and the ordering of these in the row uniquely determines $q_1,\ldots,q_N$. The numbers in column $j$ must be $1+1,2+1,3+1,\ldots,N+1$ in some order. These have frequencies $1,2,\ldots,N$ respectively, and the ordering of these in the column uniquely determines $p_1,\ldots,p_N$.
Since frequencies are preserved under type 3 operations, we can still perform this procedure on the array after type 3 operations to deduce $p_1,\ldots,p_N$ and $q_1,\ldots,q_N$. The only caveat is that we don't know exactly where $2$ was before type 3 operations, but it must be one of the two cells with a unique number. These two possibilities yield two potential answers. Furthermore, all real answers must be included among them. If $N>1$, we know there are at least two answers (the one guaranteed by the problem, and the same after applying $x\mapsto 2N+2-x$), meaning that both potential answers are real, and differ by the map $x\mapsto 2N+2-x$.
This solution takes $\mathcal{O}(N^2)$. This also proves there are at most two answers, which means that the answer is unique up to the transformation $x\mapsto 2N+2-x$.
Daniel Zhang's C++ code:
#include <cstdio> #include <vector> int table[1000][1000]; int ans[2][1000][1000]; int freq[2001]; int rs[1000]; int cs[1000]; int N; int pick_lexmin(){ for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ if(ans[0][i][j]<ans[1][i][j]){ return 0; } if(ans[0][i][j]>ans[1][i][j]){ return 1; } } } return 0; } int main(){ scanf("%d",&N); for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ scanf("%d",&table[i][j]); freq[table[i][j]]++; } } for(int u=2;u<=N*2;u++){ if(freq[u]==1){ for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ if(table[i][j]==u){ for(int k=0;k<N;k++){ rs[k]=freq[table[k][j]]; cs[k]=freq[table[i][k]]; } break; } } } break; } } for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ ans[0][i][j]=rs[i]+cs[j]; ans[1][i][j]=2*(N+1)-rs[i]-cs[j]; } } int k=pick_lexmin(); for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ if(j) printf(" "); printf("%d",ans[k][i][j]); } printf("\n"); } }
Brandon Wang's Python code:
from collections import defaultdict N = int(input()) if N == 1: print(2) exit() arr = [] for _ in range(N): arr.append(list(map(int, input().split()))) freqs = defaultdict(lambda: 0) for i in range(N): for j in range(N): freqs[arr[i][j]] += 1 def find(u): for i in range(N): for j in range(N): if arr[i][j] == u: return i, j def get_perm(u, v): ui, uj = find(u) vi, vj = find(v) perm = {u: 2, v: 2*N} for j in range(N): x = arr[ui][j] perm[x] = 1 + freqs[x] for i in range(N): x = arr[i][vj] perm[x] = 2*N - freqs[x] + 1 return perm def apply(perm): result = [] for i in range(N): result.append([perm[x] for x in arr[i]]) return result u, v = None, None for i in range(2, 2*N+1): if freqs[i] == 1: if u is None: u = i else: v = i break arr1 = apply(get_perm(u, v)) arr2 = apply(get_perm(v, u)) def display(arr): for row in arr: print(*row) for i in range(N): for j in range(N): if arr1[i][j] < arr2[i][j]: display(arr1) exit() if arr1[i][j] > arr2[i][j]: display(arr2) exit() display(arr1)