Check if it is possible to create a Binary Matrix When sum of each row and column is given?

Question

Given sum of each row and each column in a matrix check whether a binary matrix can be created ?

Input :

The first row of input contains two numbers 1≤m,n≤100000000, 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".

I trid the solution posted in Finding if binary matrix exists given the row and column sums

Above Solution works fine for small inputs but when input is of the order of 1 billion then the testing plaforms like codility times out.I need a solution that is better than o(m*n).Can someone please help here?

Answer 1

you can use maxflow algorithm;it is available in different sources such as https://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/ or somewhere else.

for this problem you have to make a graph with 4 layers; in first and 4th use just one node,in fact they are source and destination in maxflow algorithm.

and in second and third layer you have to use m and n node and between each node from one layer to another layer is an edge with capacity=1 this is what you named matrix in your question .

as we say before in your second layer we have m node and all is connected to first node(source in maxflow algorithm) and it's weights are what you get as input. and for third and 4th(destination node) is the same with m node and m input values.

after running your algorithm, if all the capacity of nodes are used so your answer is yes,and if not your answer is no. why? everywhere you used capacity it show the 1 in your matrix and you need all 1s so your answer should have all the flow. and as you see,between node number a from secnod layer and nember b from third ,if it has flow so in your matrix m, m[a][b]=1.