Pipeline Sum Communication

This is an interactive problem.

There are \(n+1\) people numbered from \(0\) to \(n\). For each \(i\) with \(0 \le i \le n-1\), person \(i\) holds an integer \(a_i\) in the range \([0,2^m-1]\). Person \(n\) wants to know the sum \[ a_0+a_1+\cdots+a_{n-1} \] expressed in binary (from the least significant bit to the most significant bit).

To accomplish this, the contestants may design a communication protocol with the following rules:

1. First, they decide on a total number of communication seconds \(N\).
2. For each of the next \(N\) seconds, every person \(i\) (with \(0 \le i \le n-1\)) simultaneously sends a single bit to person \(i+1\).
   • The sent bit is received just before the next second begins. In particular, a bit sent in the last second is never received.
   • No other form of communication is allowed.

Your task is to design an algorithm that uses as few communication seconds as possible so that after all transmissions the first 2200 bits stored in person \(n\)'s memory (each bit being either 0 or 1) represent, in binary (from low to high order), the value of \(a_0+a_1+\cdots+a_{n-1}\). (If the binary representation has less than 2200 bits, it is padded with 0's.)

Implementation details:

You must begin your program with the line

#include "mpc.h"

You do not need to (and should not) implement the main function. Instead, you need to implement the following two functions exactly as described:

int precalc(int n, int m);

• n is the number of people with an input number and m is the number of bits representing the number (i.e. the range is \([0, 2^m-1]\)).
• This function should decide and return the number of communication seconds \(N\) your protocol will use.

bool transmit(player &player, int round, int position);

• round is the current communication second, where \(1 \le round \le N\).
• position is the index of the person (\(0 \le position \le n\)).
• The structure player (defined in mpc.h) has two member variables:
  • bool last_message: the bit received from the previous person in the previous round (if position is 0 or round is 1, its value is always 0).
  • int memory[4096]: an array representing the player's "memory". Initially, for persons with position != n, the first m entries (from index 0 to m-1) contain the binary representation (from low-order to high-order) of a_position (each bit is either 0 or 1) and the rest are 0; for position == n, all entries are 0. In the transmit function, you may modify this array arbitrarily. Note that if you do not modify a player's memory in a call to transmit, then that player will retain the same memory on subsequent calls.
• Your function must return the bit that this person will send to the next person in this round. (When position == n or round == N, this return value has no effect.)

The protocol you design must ensure that after all transmit calls, the first 2200 entries of person \(n\)'s memory contain the binary representation (little-endian, each bit in \(\{0,1\}\)) of the sum \(a_0+a_1+\cdots+a_{n-1}\).

Your solution must conform to the time and memory limits imposed by the interactive library.

Testing:

A reference interactive grader (grader.cpp) is provided in the problem directory. The final grader uses an implementation that may differ from the reference, so do not rely on any specific behavior of the reference grader.

Compile your submission using the following command in the problem directory:

g++ mpc.cpp grader.cpp -o mpc -O2 -std=c++17 -lm

inputFormat

The input is read from standard input and has the following format:

• The first line contains two integers \(n\) and \(m\).
• The next \(n\) lines each contain m integers (each either 0 or 1) separated by spaces, representing the binary expansion (from least significant bit to most significant) of a_i.

outputFormat

Your program will not produce any direct output. Instead, the interactive library will use your implementations of precalc and transmit to simulate the communication protocol. After all communications, the library will output:

• A line containing a string of length 2200: the binary representation (little-endian) of \(a_0+a_1+\cdots+a_{n-1}\).
• A line containing the first 2200 entries of person \(n\)'s final memory concatenated together (with no spaces).
• If these two strings differ, a third line will indicate that the answer is incorrect; otherwise, it will display your score for that test case.

sample

1 3
1 0 1

1010... (2200 bits, representing the sum 5)