Given two input arrays [R1, ..., Rn] and [C1, ..., Cn]. We want to create a binary matrix A (of size-nxn) such that the sum of elements in column i of A be Ci and the sum of elements in row j of A be Rj.
I tried to fill using greedy algorithm : fill 1's from left to right and decrement Ci's and do this for each row. But, it didn't work. (Also, then I tried to sort rows and columns in decreasing order but still didn't work)
This can be solved using Maximum Flows. A similar (harder version of this) problem is available on LightOJ, and my code for reference
Here is the solution.
We will first create a bipartite graph. Let the number of rows be no_rows and number of columns be no_cols.
Now create no_rows + no_cols nodes. Arrange the first no_rows nodes in the left (which will form one "partite" of our bipartite graph). Lets number these nodes as l1, l2, ..., lno_row.
Similarly arrange the last no_cols nodes in the right (which will form the second "partite"). Lets number these as r1, r2, ... , rno_cols.
Now add edges between each li and rj for all 1 <= i <= no_rows and
1 <= j <= no_cols, oriented from the left to the right, with a capacity of 1.
Now create a source(S) and a sink(T). Add edge of unit capacity oriented from source to each vertex on the left.
Similarly add edges of unit capacity oriented from each vertex on the right, to the sink.
Now just find the Maximum Flow in this graph. Now if there exists a flow between some li and some rj, that implies that the cell (i, j) will have 1, otherwise it will have 0.
Note: To ensure that there even exists such a binary matrix, make sure that each of the (S, l) edges and (r, T) edges are completely filled.
Edit: Here is an implementation of Dinic in C++ ideone
Edit 2: The capacity of the edge connecting the source to any li is Ri (where R is the given input array indicating row sums). Similarly the capacity of the edge connecting ri to sink T is Ci (where C is the array given in input indicating column sums)