22
\$\begingroup\$

My final-year project at the National University of Singapore is on Zarankiewicz's problem:

What is the maximum number of 1s in an \$m×n\$ binary matrix (\$m\$ rows and \$n\$ columns) with no \$a×b\$ minor (intersection of any \$a\$ rows and any \$b\$ columns) being all 1s?

For example, the matrix below contains a \$3×3\$ all-1 minor $$\begin{bmatrix} 0&(1)&1&(1)&(1)&1\\ 1&1&0&1&0&0\\ 0&(1)&0&(1)&(1)&0\\ 0&1&1&0&1&1\\ 1&1&0&0&0&1\\ 1&(1)&0&(1)&(1)&0 \end{bmatrix}$$ but this matrix contains no such minor – the intersection of any 3 rows and 3 columns always has at least one 0: $$\begin{bmatrix} 0&1&1&1&1&1\\ 1&0&0&1&1&1\\ 1&0&1&0&1&1\\ 1&1&0&1&0&1\\ 1&1&1&0&0&1\\ 1&1&1&1&1&0 \end{bmatrix}$$ Now any matrix with the maximum number of 1s is also maximal in the sense that adding another 1 anywhere in the matrix will create an \$a×b\$ minor. This task concerns itself with checking maximal matrices, not necessarily with the maximum number of 1s.

Task

Given a non-empty binary matrix \$M\$ of size \$m×n\$ and two positive integers \$a\$ and \$b\$ where \$a\le m\$ and \$b\le n\$, determine whether \$M\$ has no \$a×b\$ all-1 minor, but has at least one such minor if any 0 in \$M\$ is changed to a 1. Output "true" or "false"; any two distinct values may be used for them. Formatting is also flexible for \$M\$.

This is ; fewest bytes wins.

Test inputs

These are given in the form M a b.

"True" output:

[[0]] 1 1
[[0,1,1],[1,0,1],[1,1,0]] 2 2
[[0,1,0],[1,1,1],[0,1,0]] 2 2
[[1,1,0,1,0],[1,0,1,1,1],[0,1,1,0,1]] 2 3
[[1,1,1,1,1],[1,1,1,1,1],[1,0,0,0,0]] 3 2
[[0,1,1,1,1,1,1,1],[1,1,1,1,1,0,0,0],[1,1,1,0,0,1,1,0],[1,1,0,1,0,1,0,1],[1,1,0,0,1,0,1,1],[1,0,1,1,0,0,1,1],[1,0,1,0,1,1,0,1],[1,0,0,1,1,1,1,0]] 3 3
[[1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0],[1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0],[1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0],[1,1,0,0,0,0,1,1,0,0,1,1,1,1,0,0],[1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0],[1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0],[1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0],[1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0],[0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1],[0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1],[0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,1],[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1],[0,0,1,1,1,1,0,0,1,1,0,0,0,0,1,1],[0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1],[0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1],[0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1]] 3 3

"False" output:

[[1]] 1 1
[[0,1,0,1,0],[1,0,1,0,1],[0,1,0,1,0]] 1 3
[[0,1,0],[0,1,0],[0,1,0]] 3 1
[[0,0],[1,1]] 2 2
[[0,0,0,0,0,1,1,1,1],[0,0,1,1,1,0,0,0,1],[0,1,0,0,1,0,0,1,0],[0,1,0,1,0,0,1,0,0],[0,1,1,0,0,0,0,0,0],[1,0,0,0,1,1,0,0,0],[1,0,0,1,0,0,0,1,0],[1,0,1,0,0,0,1,0,0],[1,1,0,0,0,0,0,0,1]] 2 2
[[0,1,1,1],[1,0,1,1],[1,1,0,1],[1,1,1,0]] 4 4
[[1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1],[0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0],[0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0],[0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0],[0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0],[0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0],[0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1],[1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0],[0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0],[0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0],[0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1],[1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0],[0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0],[0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0],[0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0],[0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1],[1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0],[0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1],[1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1]] 2 2

The fifth "false" test case is indeed false since flipping the \$(4,5)\$ entry from 0 to 1 does not make a \$2×2\$ minor.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ You can confirm that your fifth "False" solution is, indeed, false? When you change M[0][0] to 1, the intersection of rows (0, 5) and columns (0, 5) are all 1s. \$\endgroup\$
    – Ajax1234
    Feb 6, 2022 at 20:24
  • \$\begingroup\$ @Ajax1234 It is indeed false – there is still no 2×2 minor after flipping M[4,5]. \$\endgroup\$ Feb 7, 2022 at 2:05
  • \$\begingroup\$ May I input the matrix as an array of integers whose binary representation is each rows? For example, [[1, 0, 0, 0], [0, 1, 1, 1], [0, 1, 0, 1]] -> [8, 7, 5], as 8=1000(2), 7=0111(2), 5=0101(2). \$\endgroup\$
    – tsh
    Feb 7, 2022 at 7:40
  • \$\begingroup\$ @tsh I told you input was flexible, but if not a common method please specify the format used in the answer. \$\endgroup\$ Feb 7, 2022 at 7:42

6 Answers 6

4
\$\begingroup\$

Python3, 175 bytes:

lambda m,a,b,z=lambda m:all(b>sum(map(all,zip(*s)))for s in combinations(eval(m),a)):z(M:=str(m))-any(z(M[:i]+'1'+M[i:])for i,c in enumerate(M)if"0"==c);from itertools import*

Try it online!

\$\endgroup\$
10
  • \$\begingroup\$ z=lambda m,a,b:any(b<=sum(map(all,zip(*s)))for s in I.combinations(m,a)) \$\endgroup\$
    – tsh
    Feb 7, 2022 at 8:16
  • \$\begingroup\$ (I:=i.span())[0], I[1] -> (I:=i.start()), I+1 -> (I:=i.end())-1, I -> str(m)[:(I:=i.end())]+'+1'+str(m)[I:] \$\endgroup\$
    – tsh
    Feb 7, 2022 at 8:21
  • \$\begingroup\$ not z(m,*c)and all(...) -> all(...)-z(m,*c) \$\endgroup\$
    – tsh
    Feb 7, 2022 at 8:23
  • \$\begingroup\$ 195 bytes: lambda m,a,b,z=lambda m:any(b<=sum(map(all,zip(*s)))for s in t.combinations(m,a)):all(z(eval(str(m)[:(I:=i.end())]+'+1'+str(m)[I:]))for i in re.finditer('0',str(m)))-z(m);import itertools as t,re \$\endgroup\$
    – tsh
    Feb 7, 2022 at 8:33
  • 1
    \$\begingroup\$ 175 bytes: lambda m,a,b,z=lambda m:all(b>sum(map(all,zip(*s)))for s in combinations(eval(m),a)):z(M:=str(m))-any(z(M[:i]+'1'+M[i:])for i,c in enumerate(M)if"0"==c);from itertools import* \$\endgroup\$
    – tsh
    Feb 7, 2022 at 8:46
4
\$\begingroup\$

R, 196 166 155 149 135 bytes

Or R>=4.1, 107 bytes by replacing four function occurrences with \s.

Edit: -14 bytes thenks to @Giuseppe.

function(M,a,b,`?`=all)M==sapply(seq(!M),g<-function(i){M[i]=1;?!combn(nrow(M),a,function(x)combn(ncol(M),b,function(y)?M[x,y]))})?g(0)

Try it online!

Straightforward brute-force.

Takes advantage of redefining `?`=all and operator precedence (? has the lowest and is both unary and binary operator).

\$\endgroup\$
2
2
\$\begingroup\$

J, 86 bytes

1=2#.1-((1 e.,@{@(<@(#~(-:~.)&>)@,@{@#"0;&i./@$)*/@,@{])"1 2],~$$"1,1:`[`]}"{~[:I.1-,)

Try it online!

The 2 long test cases time out on TIO, so I've removed them.

  • Creates a list of all 0-to-1 mutated versions of the input, with the input itself as the final element in that list.
  • For each of those, checks for the required minor, using brute force, returning 1 if a minor is found, 0 otherwise.
  • Swaps those zeros and ones
  • Convert to a binary number
  • Checks if the number is 1.
    • This will only be true of every 0-to-1 mutation has the minor, but the input does not.
\$\endgroup\$
2
\$\begingroup\$

Python 3, 176 bytes

lambda m,a,b:(z:=lambda m:all(b>sum(map(all,zip(*s)))for s in combinations(eval(m),a)))(M:=str(m))-any(z(M[:i]+'1'+M[i:])for i,c in enumerate(M)if"0"==c)
from itertools import*

Try it online!

Based on the Python answer by Ajax1234.

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 208 bytes

Returns \$0\$ or \$1\$.

Even though we don't have any combination built-in, this seems a bit too long. :-/

(m,a,b)=>(g=(v,n,C,i)=>i>>v.length||((h=i=>i&&i%2+h(i>>1))(i)^n||C(i))&&g(v,n,C,-~i))(m,a,p=>g(m[0],b,q=>m.some(X=Y=(r,y)=>r.some((v,x)=>p>>y&q>>x&~v&1?x-X|y-Y||![X=x,Y=y]:0))?1:(m[Y]||0)[X]+=2))&!/0/.test(m)

Try it online!

Commented

(m, a, b) =>                 // m[] = binary matrix, a = rows, b = columns
( g = (v, n, C, i) =>        // g is a helper function:
  i >> v.length || (         //   for each i >= 0 and less than 2 ** L,
    ( h = i =>               //   where L is the length of the vector v,
      i && i % 2 + h(i >> 1) //   count the number of set bits in i
    )(i) ^ n ||              //   if it's exactly equal to n:
      C(i)                   //     invoke C(i)
  )                          //
  && g(v, n, C, -~i)         //   keep going while the above is truthy
)(                           //
  m, a,                      // outer call to g: pick the rows
  p => g(                    // for each row bitmask p:
    m[0], b,                 //   inner call to g: pick the columns
    q =>                     //   for each column bitmask q:
      m.some(X = Y =         //     initialize X and Y to non-numeric values
      (r, y) =>              //     for each row r[] at position y in m[]:
        r.some((v, x) =>     //       for each value v at position x in r[]:
          p >> y &           //         if (x,y) belongs to a selected row
          q >> x &           //         and a selected column
          ~v & 1 ?           //         and v is even:
            x - X | y - Y || //           abort if (X,Y) is set and ≠ (x,y)
            ![X = x, Y = y]  //           otherwise set (X,Y) = (x,y)
          :                  //         else:
            0                //           do nothing
        )                    //       end of inner some()
      ) ?                    //     end of outer some(); if truthy:
        1                    //       do nothing
      :                      //     else:
        (m[Y] || 0)[X] += 2  //       add 2 to m[Y][X] (results in NaN if Y
                             //       is still non-numeric)
  )                          //   end of inner call to g()
) &                          // end of outer call to g()
!/0/.test(m)                 // make sure that all 0's in m[] are gone
\$\endgroup\$
2
\$\begingroup\$

Desmos, 247 241 bytes

B(n,i)=mod(floor(n/2^i),2)
P(n)=∑_{i=0}^nB(n,i)

f(L,w,h,a,b)=\{\sum_{X=0}^w\sum_{Y=0}^h\{0<\sum_{s=0}^{2^h-1}\sum_{t=0}^{2^w-1}\{P(t)=b,0\}\{P(s)=a,0\}\prod_{x=0}^w\prod_{y=0}^h\{B(t,x)B(s,y)=0,L[yw+x+1]=1,\{x=X\}\{y=Y\}=1,0\},0\}=0^L.\total\}

Extra newline needed for pasting of the piecewise inside f.

Takes input as a flattened list L, width&height w,h, and the a,b of the submatrices given in the problem.

Returns 1 for Zarankiewicz-minimal matrices, otherwise NaN.

Try it on Desmos! Takes too long for the larger test cases, so I commented them out.

Considering Desmos doesn't have 2d lists, combination built-in, or bit extract built-ins, this is decently good. Maybe the condition at the inside can be golfed (\{B(t,x)B(s,y)=0,L[yw+x+1]=1,\{x=X\}\{y=Y\}=1,0\}), or some conditions can be negated to simplify arithmetic, but I keep ending up longer.

How it works

Since there's no combination built-in, we iterate over the powerset of rows+columns given by u in binary, then filter for those with hamming weight a and b respectively.

We have a big summation that gets compared with 0^L.\total (number of 0s). If the matrix already has an a×b submatrix, then every summand is 1, so the comparison is (w+1)(h+1)=total(1-L), which is always false. If the matrix does not have an a×b all-1s submatrix, then summands are 1 only for entries that are 0 and lead to an a×b all-1s submatrix when changed to 1. Hence the condition is met only if every 0 entry leads to an a×b all-1s submatrix when changed to 1.

I have since merged s and t into u as u=2^w*s+t for -5 bytes.

B(n,i): the i'th bit of n, where the 0th bit is the LSB
B(n,i)=mod(floor(n/2^i),2)
# P(n): hamming weight of n, the number of 1 bits
P(n)=∑_{i=0}^nB(n,i)

f(L,w,h,a,b)=\{
  \sum_{X=0}^w\sum_{Y=0}^h # sum over all (X,Y)
  \{  # does the matrix has an a×b all-1 minor if (X,Y) is changed to 1?
    0<
      \sum_{s=0}^{2^h-1}\sum_{t=0}^{2^w-1} # sum over powerset of rows and columns
      \{P(t)=b,0\}\{P(s)=a,0\} # 1 if the number of rows = a and number of columns = b, so s,t defines an a×b submatrix
      \prod_{x=0}^w\prod_{y=0}^h # for all entries (x,y) in the matrix, is the following true?
      \{
        B(t,x)B(s,y)=0, # (x,y) is not in the selected submatrix, or
        L[yw+x+1]=1,    # the entry at (x,y) is 1, or
        \{x=X\}\{y=Y\}=1, # (x,y)==(X,Y), so the entry is changed to 1
        0
      \},
    0
  \}
  = 0^L.\total # is this sum equal to the number of 0s?
\}

Proper rendering of f for +9 bytes

(I have not kept this up to date with the latest golfs)

B(n,i)=mod(floor(n/2^i),2)
P(n)=\sum_{i=0}^nB(n,i)

Q=\{B(t,x)B(s,y)=0,L[yw+x+1]=1,\{x=X\}\{y=Y\}=1,0\}
f(L,w,h,a,b)=\left\{∑_{X=0}^w∑_{Y=0}^hsign(∑_{s=0}^{2^h-1}∑_{t=0}^{2^w-1}0^{(P(t)-b)^2}0^{(P(s)-a)^2}∏_{x=0}^w∏_{y=0}^hQ)=total(1-L)\right\}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I have no idea what's going on here but it's very impressive! \$\endgroup\$
    – Aiden Chow
    May 8, 2022 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.