Counting Trees

All submissions for this problem are available.
Mr. Devu Singh has a farm. The farm is represented as a matrix, divided into rows and columns, with each element being equal to 1, if the corresponding area in the farm contains a tree, and 0 otherwise. Every element in the farm can contain atmost one tree.
Mr. Devu Singh loves his farm. However, Devu Singh has a short memory. He cannot remember which of the elements in the farm has a tree in them. What he does remember is the total number of trees in each row and each column, but is not sure about this information either. He wishes to know, that for such constraints, whether there exists a matrix satisfying these constraints. If there does exist such a matrix, output the lexicographically smallest one, otherwise output 1.
For lexicographically comparing two matrices A and B, you write the matrix A and B as a string of 0/1 by writing in row major order (ie, first write first row, then second row and so on upto nth row.). Now lexicographically compare the two strings generated in this way.
Input Format
First line contains T : number of test cases.
For each test case, first line has N and M.
Next line contains N space separated integers where ith one represents sum of the ith row.
Line after that contains M space separated integers where ith one represents sum of ith column.
Output Format
For the ith test case, the first line contains the string "TestCase #:i" (without quotes). From the next line, output matrix of size N x M, as N lines containing M integers each (without space), with Element[i,j] = 0 or 1, depending on whether there can be a tree in that area. Output 1, if no such matrix exists.
Constraints
 1 ≤ T ≤ 20
 1 ≤ N, M ≤ 50
 0 ≤ Sum of elements in a row ≤ M
 0 ≤ Sum of elements in a column ≤ N
Sample Input
3
4 4
3 2 3 1
4 3 1 1
4 4
1 3 0 2
1 1 2 2
1 1
1
0
Sample Output
TestCase #:1
1101
1100
1110
1000
TestCase #:2
0001
0111
0000
1010
TestCase #:3
1
Explanation
For first test case, the given matrix is the lexicographically smallest one with sum of row1 =3,
sum of row2 =2, sum of row3 =3, sum of row4 =1 and sum of column1 =4, sum of column2 =3, sum of column3 =1, sum of column4 =1.
Similarly for the second test case, the given matrix is the lexicographically smallest one satisfying the given constraints.
For the third test case, there cannot be any matrix of size 1x1 and sum of row1=1 and sum of column1=0. Hence output is 1.
Author:  iopc_admin 
Tags  iopc_admin 
Date Added:  28022014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP 4.3.2, CPP 4.9.2, GO, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions