Broadcasting Binary Bits over Communication Rounds

This is a communication problem.

There are several nodes, each initially holding a binary digit \(a_i\in\{0,1\}\). They wish to learn the initial numbers stored in every other node by communicating over \(K\) rounds.

At the beginning of each round, each node \(i\) chooses for each node \(j\) a binary number \(c_{i,j}\in\{0,1\}\). At the end of the round, every node \(j\) receives the sum \(s_j = \sum_i c_{i,j}\) of all bits sent to it in that round.

Your task is: for a given \(K\) (with \(1\le K\le 10\)), determine a (preferably as large as possible) number of nodes \(N\) (where \(1\le N\le 60\)) so that after \(K\) rounds, each node is able to determine every other node's initial bit.

Implementation Details

• You do not need to implement a main function.
• You need to implement two functions below:
1. int init(int K);
   • This function is given the total number of communication rounds \(K\). It must return a chosen number of nodes \(N\) (\(1\le N\le 60\)).
   • The interactor will call this function exactly once before any calls to send in each run.
2. unsigned long long send(int K, int N, int round, int number, const std::vector& received);
   • Parameters:
     • \(K\): Total communication rounds.
     • \(N\): The number of nodes returned by init.
     • round: The current round number, where \(1\le round\le K+1\). For rounds \(1\) to \(K\), you must send out numbers. For round \(K+1\), you are providing the final answer.
     • number: The node number for which your function is being called, \(0 \le number < N\).
     • received: A vector of integers. received[0] is the initial stored bit, and for \(1\le i < round\), received[i] is the number received by the node at the end of the \(i\)-th round.
   • For rounds \(1\) to \(K\): The function must return an unsigned 64-bit integer \(x\) representing the bits that the current node sends to all nodes. The \(i\)-th bit of \(x\) (when represented in binary with leading zeros as needed) is the bit sent to node \(i\).
   • For round \(K+1\): The function must return an unsigned 64-bit integer \(x\) whose \(i\)-th bit represents the final decision for node \(i\)'s stored bit.
• The interactor guarantees that the same call (with same parameters) will always be given the same return value from your functions.
• Time and memory constraints are generous (at least 900 ms and 448 MiB), so efficiency is not the primary concern in this problem.

Note: Your solution will be evaluated on several test cases.

inputFormat

This is an interactive problem. The only input provided by the interactor is the integer \(K\) (the total number of communication rounds). The interactor will then simulate multiple calls to your send function, providing the necessary parameters as described in the problem statement.

outputFormat

Your functions must return unsigned 64-bit integers as specified. For rounds \(1 \le round \le K\), the returned integer from \(send\) represents the binary vector of values sent to each node. For round \(K+1\), the returned integer represents the final conclusion about each node's initial bit (with the \(i\)-th bit corresponding to node \(i\)).

sample

K = 1;
For the single node (node 0), initial bit = 1.
Round 1: send returns 0.
Round 2: send returns 1 (final answer).

Final answer: 1