Consider some inputs r
and c
and a matrix S
that satisfies them.
Throw away the contents of the last row in S
to get a new matrix S(n-1)
. If we fed S(n-1)
to the greedy algorithm and asked it to fill in this last row, it'd obviously recover a satisfying solution.
Well, now throw away the contents of the last two rows in S
to get S(n-2)
. Since we know a satisfying solution exists, we know that there are no j
such that c(j) - a(j) > 2
, and the number of j
such that c(j)-a(j) == 2
is smaller or equal to r(n-1)
. It follows that the greedy algorithm will set A[n-1, j] = 1
for the latter set of j
, along with some other j
for which c(j)-a(j) = 1
. But because we know there's a satisfying solution, it must be that the number of j
with c(j) - a(j) == 1
after the n-1
th row is filled is exactly r(n)
, and is hence satisfiable.
Anyway, we can extend this downwards: in S(n-k-1)
it must be the case that:
- there aren't any
j
such thatc(j) - a(j) > k+1
- there can be at most
r(n-k)
manyj
such thatc(j) - a(j) = k+1
, - and
Sum(c(j) - a(j)) == Sum(r(i), i >= n-k)
So after the greedy algorithm has processed the n-k
th row, it must be the case that
- there aren't any
j
such thatc(j) - a(j) > k
- there can be at most
r(n-k+1)
manyj
such thatc(j) - a(j) = k
, - and
Sum(c(j) - a(j)) == Sum(r(i), i >= n-k+1)
Hence when k = 0
, there aren't any j
such that c(j) - a(j) > 0