Best Compromise

Photo by Andy
Nelson

There is a saying “a good compromise makes no one happy”. As
distressing as that may be, I guess most people still think it
is a good idea to seek the best agreement. The problem though,
is to define the measure in which the word “best” gets a
meaning. Let us consider $n$ people, each with a firm belief on
$m$ different yes/no
issues. We may think of the people’s beliefs as binary strings
$b_ i$ of length
$m$ for $0<i\leq n$, i.e. one string per
person, with entries reflecting a person’s belief in each of
the $m$ issues. An
*agreement* is also a binary string $a$ of length $m$, indicating the agreed outcome of
each of the $m$ issues.
Some would argue that the agreement $a$ that minimises the maximum of
$H(b_ i-a)$ over all
$i$, where $H(x)$ is the Hamming function
counting the number of non-zero entries of the vector
$x$, is the best
compromise. Unfortunately, it is widely believed that finding
this agreement is computationally infeasible for $n$ and $m$ large. Another reasonable
suggestion is the agreement $a$ that minimises $\left(\sum _{i=1}^ n H(b_ i-a)^
p\right)^{1/p}$ for some positive integer $p$. Note in particular that when
$p\rightarrow \infty $,
this measure coincides with the former. I for one am most
content with the choice of $p=1$ though, don’t you agree?

On the first line of input is a single positive integer $t$, telling the number of test scenarios to follow. Each test scenario is described by two positive integers $n\leq 100$ and $m\leq 100$, on a line of their own. Then follow $n$ lines, each containing a binary string $b_ i$ on $m$ ‘0’ and ‘1’ characters.

For each test scenario, output the assignment $a$ that minimises the measure above with $p = 1$, on a row of its own. If there are several solutions, output anyone.

Sample Input 1 | Sample Output 1 |
---|---|

2 5 5 00000 00100 01001 01101 00101 1 7 0110010 |
00101 0110010 |