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:
Output “YES” if there exists an m-by-n matrix A, with each element either being 0 or 1. Else "NO".
Example:
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
Explanation:
1 1
0 1
0 0
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:
Output “YES” if there exists an m-by-n matrix A, with each element either being 0 or 1. Else "NO".
Example:
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
Explanation:
1 1
0 1
0 0
Well that didn't take long to find.
https://stackoverflow.com/questions/27930197/how-to-build-a-binary-matrix-from-sums
https://stackoverflow.com/questions/27930197/how-to-build-a-binary-matrix-from-sums
Topic archived. No new replies allowed.