Finding if binary matrix exists given the row and

How to find out if it is possible to contruct a binary matrix with given row and column sums.

Input :

The first row of input contains two numbers 1≤m,n≤1000, 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 tried reading about Tomography algorithms but could not figure out an answer as all the papers related to Tomography algorithm is very complicated.

Can someone please help me..

I've successfully implemented randomly generating such matrices for R using a modeling based on network flow. I intend to write up those ideas one day, but haven't found the time yet. Reasearching for that, I read in Randomization of Presence–absence Matrices: Comments and New Algorithms by Miklós and Podani:

The Havel-Hakimi theorem (Havel 1955, Hakimi 1962) states that there exists a matrix X_n,m of 0’s and 1’s with row totals a₀=(a₁, a₂,… , a_n) and column totals b₀=(b₁, b₂,… , b_m) such that b_i ≥ b_i+1 for every 0 < i < m if and only if another matrix X_n−1,m of 0’s and 1’s with row totals a₁=(a₂, a₃,… , a_n) and column totals b₁=(b₁−1, b₂−1,… ,b_a₁−1, b_a₁+1,… , b_m) also exists.

I guess that should be the best method to recursively decide your question.

Phrased in my own words: Choose any row, remove it from the list of totals. Call that removed number k. Also subtract one from the k columns with larges sums. You obtain a description of a smaller matrix, and recurse. If at any point you don't have k columns with non-zero sums, then no such matrix can exist. Otherwise you can recursively build a matching matrix using the reverse process: take the matrix returned by the recursive call, then add one more row with k ones, placed in the columns from whose counts you originally subtracted one.

Implementation

bool satisfiable(std::vector<int> a, std::vector<int> b) {
  while (!a.empty()) {
    std::sort(b.begin(), b.end(), std::greater<int>());
    int k = a.back();
    a.pop_back();
    if (k > b.size()) return false;
    if (k == 0) continue;
    if (b[k - 1] == 0) return false;
    for (int i = 0; i < k; i++)
      b[i]--;
  }
  for (std::vector<int>::iterator i = b.begin(); i != b.end(); i++)
    if (*i != 0)
      return false;
  return true;
}