Secure Matrix Communication

This is a communication problem with a non-adaptive interactive library.

Alice has an \( n\times n \) 0-1 matrix \( A \) satisfying the following condition:

There do not exist indices \(0 \le i_1 < i_2 < n\) and \(0 \le j_1 < j_2 < n\) such that \[ A_{i_1,j_1} = A_{i_2,j_2}, \quad A_{i_1,j_2} = A_{i_2,j_1}, \quad A_{i_1,j_1} \neq A_{i_1,j_2} \] all hold simultaneously.

Alice wants to communicate the matrix \( A \) to Bob. For security reasons, the communication protocol is as follows:

1. Alice selects some of the \( n^2 \) elements of \( A \) by calling the function select(i, j).
2. The interactive library has two hidden permutations \( p \) and \( q \) (both on \( \{0,1,\dots,n-1\} \)).
3. Bob receives an \( n\times n \) matrix \( B \) where for every selected element \((i,j)\), we have \( B_{p_i,q_j} = A_{i,j} \), and for every non-selected element \((i,j)\), \( B_{p_i,q_j} = -1 \).

Bob's task is to fill in all \(-1\) entries of the matrix \( B \) with either \(0\) or \(1\) so that for every \(0 \le i,j < n\), the equality \( B_{p_i,q_j} = A_{i,j} \) holds.

Implementation Details

This is a communication problem with a non-adaptive interactive library.

• You do not need (and should not) implement the main function. You are forbidden from accessing standard input/output streams.
• At the top of your file, include the declaration:

  void select(int x, int y);

• You are allowed to call the provided function:

  void select(int i, int j);

  Ensure \(0 \le i,j < n\). Let \( k \) be the total number of calls made to this function.
• Implement the following functions:

void send(vector<vector> A);

The parameter A is an \( n\times n \) two-dimensional vector of integers (each element is either \(0\) or \(1\)). In this function, you should call select to choose the elements you want to transmit. You may not call select more than \( n^2 \) times.

vector<vector> reconstruct(vector<vector> B);

For the matrix \( A \) provided to send, the parameter B in reconstruct is a matrix of the same dimensions where the following holds for the hidden permutations \( p, q \):

• If select(i,j) was called, then \( B_{p_i,q_j} = A_{i,j} \).
• Otherwise, \( B_{p_i,q_j} = -1 \).

Your return value C from reconstruct must satisfy for all \(0 \le i,j < n\):

\( C_{p_i,q_j} = A_{i,j} \).

Notes

• The calls to select in send and the output of reconstruct should depend only on the values of the given parameters. Inconsistent behavior on multiple calls with the same parameter values will result in a Wrong Answer.
• The hidden permutations \( p,q \) are fixed and non-adaptive. You cannot directly access them.
• Each test case contains multiple independent data sets. For each data set, send and reconstruct are each called exactly once. Their combined running time will be measured.
• Do not rely on any behavior specific to the sample grader, as the actual grader will behave differently.

Simplified Approach: One trivial solution is to call select for every \((i,j)\) in send (total \( n^2 \) calls). Then, in reconstruct, since every entry has been transmitted, simply return the matrix B as is.

inputFormat

There is no standard input. Instead, the functions send and reconstruct will be called with a matrix as a parameter.

For send: a 2D vector (or equivalent in your programming language) representing the \( n\times n \) matrix \( A \).

For reconstruct: a 2D vector (or equivalent) representing the matrix \( B \) after applying the hidden permutations \( p \) and \( q \), where non-selected positions contain \(-1\).

outputFormat

The function reconstruct should return a 2D vector (or equivalent) \( C \) satisfying \( C_{p_i,q_j} = A_{i,j} \) for all \(0 \le i,j < n\).

sample

Test Case 1: n = 2, A = [[0, 1], [1, 0]]

After calling send (which selects all positions), reconstruct returns B unchanged, which equals the permuted A with no -1 entries.