Problem: A binary matrix is an m x n matrix consisting of only zeroes and ones. Now you are given m integers, ith integer indicating the summation of the values of cells in ith row. You are also given n integers, ith integer indicating the summation of the values of cells in jth column.
Your task is to generate the binary matrix. As there can be multiple solutions, we want the solution which is lexicographically smallest. To compare two solutions, we first find the cell (topmost, then leftmost) where the solutions differ; then the solution which contains 0 in that cell is lexicographically smaller. So,
001 001
010 < 100
100 010
Input.
Input starts with an integer T (≤ 125), denoting the number of test cases.
Each case starts with a line containing two integers: m and n (1 ≤ m, n ≤ 50). The next line contains m integers, separated by a single space, denoting the row sums. The next line contains n integers, separated by spaces, denoting the column sum. All the integers will be between 0 and 50 (inclusive).
Output.
For each case, print the case number first. Then if there is no solution, then print 'impossible' on the same line. Otherwise, from the next line, print m lines each having n characters denoting the binary matrix as stated above.
Sample Input
5
3 3
1 1 1
1 1 1
3 3
1 1 2
2 2 1
2 3
30 30
30 20 10
2 9
5 5
1 1 2 1 1 1 1 1 1
3 3
1 2 3
3 2 1
Output for Sample Input
Case 1:
001
010
100
Case 2: impossible
Case 3: impossible
Case 4:
001001111
111110000
Case 5:
100
110
111
/***/ Please give some Hint or pseudocode [if needed] /***/
Construct a bipartite graph with n + m vertex, v1, v2, ..., vm representing each row, and u1, u2, ..., un representing the columns. Add an additional source s, and a sink t. Add edges (s, vi) with capacity equals to the numbers of ones in the row i, and add edges (ui, t) with capacity equals to the numbers of ones in the column i. Connect every vi with every uj with capacity 1 an all edges. If all edges form source and all edges to sink are saturated then exist a solution. If an edge (vi, uj) has flow 1 then put a 1 in (i, j). For finding the min lexicographic solution traverse the matrix by rows, if there is a 1 in position (i, j) let's try to put a 0 instead, to do this eliminate the edge (vi, uj) and try to find again a max flow, if there is one that meets the requirements puts the cell to 0, if not leave it in 1. To do the things faster when we remove an edge is not necessary calculate the max flow from the beginning, you can run a dfs for find an augmenting path from source to sink, if there exists then we have a max flow again.
jcg Will you please help in a problem which is kind of similar to this. The problem statement is as follows: Given N (number of rows) and M(number of columns), find the total number of binary matrices (containing only 0s and 1s) where sum of ith row of this matrix should be Ri and the sum of jth Column of the matrix should be Cj.
Input format : First line contains number of test cases( T ). Description of each test case is as follows, first line of each test case contains N and M number of rows and columns respectively. next line contains N integers ith integer denotes the sum if the ith row(Ri) next line contains M integers where jth integer denotes the sum of jth column(Cj)
Constraints:
1<=T<=10
1<=N <=8
1<=M<=8
0<=Ri<=M
0<=Cj<=N
Output format: (1) If there is only one solution satisfying the given criteria print this Matrix. (2) Otherwise print the total number of possible solution satisfying the given condition.
Sample Input:
3
4 4
1 1 1 1
1 1 1 1
3 3
3 2 3
3 3 2
4 4
1 2 1 3
3 2 2 1
Sample output:
24
1 1 1
1 1 0
1 1 1
0
Explanation: In the first test case you can put only one matrix in each row and each column so in first row there are 4 possibilities in second 3 possibilities in third 2 possibilities and in the last row there is only one remaining place so answer is 4 * 3 * 2 * 1=24 In second test case there is only one possible arrangement so print the corresponding matrix. In the third there is no possible arrangement.
If we only need to check if there exists a matrix or not then can we do it in linear time?
Yes, you can do this in O(n+m) time, you may refer this article. link