Problem C

Binary tomography deals with the problem of reconstructing binary images from a small number of projections. One of its most basic problems is to construct a binary ($\{ 0,1\} $-valued) matrix with given row and column sums. This is not always possible and your task is to determine when it is.


The first line of input contains two numbers $1\leq m,n\leq 1000$, the number of rows and columns of the matrix. The next line contains $m$ numbers $0\leq r_ i\leq n$ – the sum of each row in the matrix. The third line contains $n$ numbers $0\leq c_ j\leq m$ – the sum of each column in the matrix.


Output “Yes” if there exists an $m$-by-$n$ matrix $\mathbf{A}$, with each element either beeing 0 or 1, such that

\[ \sum _{j=1}^ nA_{i,j} = r_ i \; \forall i\in \{ 1,2,\dots ,m\} \textrm{ and } \sum _{i=1}^ mA_{i,j} = c_ j \; \forall j\in \{ 1,2,\dots ,n\} . \]

Otherwise output “No”.


The figure below illustrates a matrix with the row and column sums of sample input 1.

Sample Input 1 Sample Output 1
3 4
2 3 2
1 1 3 2
Sample Input 2 Sample Output 2
3 3
0 0 3
0 0 3

Please log in to submit a solution to this problem

Log in