Doubt in the following algorithm

[ChPravin]

Hello all,

Problem :

We are given two arrays of integers, R[1..m] and C[1..n]
such that R[1]+R[2]+...+R[m]=C[1]+C[2]+..+C[n]=k.
Give an O(kmn) algorithm that returns an m× n matrix of 0s and 1s such
that row i contains exactly R 1s and column j contains exactly C[j] 1s,
for all 1 ? i ? m and 1 ? j ? n. If there is no such matrix, your algorithm
should return nil.

I have written the following code for the problem above but it doesn't seem to work in the required complexity.Kindly give in your suggestions,either to modify the code to obtain the desired complexity or suggest a new approach:

for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
//I am assuming R[1..m] and C[1..n] to be initialized already
if(r>=1 ^ c[j] >=1)
{
//p is the matrix being filled
p[j]=1;
r--;
c[j]--;
}
p[j]=0;
}
}

Thanks and regards

[mf]

I have written the following code for the problem above but it doesn't seem to work in the required complexity.

Why? Its complexity is O(mn), which is also in the class O(kmn), so its alright.
The problem, I guess, is that it doesn't solve your problem?

Construct a flow network with source s, sink t, a vertex A_i for each row i, vertex B_j for each column j. Connect the source to A_i with an edge of capacity R; connect B[j] to sink with an edge of capacity C[j], and connect every A_i to every B_j with an edge of capacity 1, and find maximum flow using Ford-Fulkerson algorithm. If there exists a flow of value k, you can read your matrix off the flow values of edges between A_i's and B_j's, and if there's not, then there's no such matrix.

[hwwong]

I think this can transformed to a linear algebra problem trivially.

[mf]

Nope. We're looking not just for some real-valued matrix, but for a "matrix of 0s and 1s".

[hwwong]

Nope. We're looking not just for some real-valued matrix, but for a "matrix of 0s and 1s".

If the equations have a unique solution, simply check if all variables are either 1,0
Otherwise, put free variables as 1 or 0. Then check if the rest of all variables have integral solutions.