Finding if binary matrix exists given the row and column sums

How to find out if it is possible to contruct a binary matrix with given row and column sums.

Input :

The first row of input contains two numbers 1≤m,n≤100000, the number of rows and columns of the matrix. The next row contains m numbers 0≤ri≤n – the sum of each row in the matrix. The third row contains n numbers 0≤cj≤m – the sum of each column in the matrix.


Output “YES” if there exists an m-by-n matrix A, with each element either being 0 or 1. Else "NO".


Input: n=3 m=2 (no. of rows and columns)
2 1 0 (number of 1's that should be present in each row respectively)
1 2 (number of 1's that should be present in each column respectively)

Output: Possible


1 1
0 1
0 0
Topic archived. No new replies allowed.