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.