Detailed mathematical approach

Problem Summary

For an \(n\times n\) binary matrix \(A\), let \(r(A)\) be the number of distinct rows and \(c(A)\) the number of distinct columns. The matrix complexity is

$\kappa(A)=\max(r(A),c(A)).$

For each integer \(k\in\{0,1,\dots,n^2\}\), define

$m_n(k)=\min\{\kappa(A): A \text{ is an } n\times n \text{ binary matrix with exactly } k \text{ ones}\}.$

The required quantity is

$C(n)=\sum_{k=0}^{n^2} m_n(k).$

The implementation does not search over matrices directly. Instead, it marks which values of \(k\) are achievable with complexity \(1\), \(2\), or \(3\), and then every unmarked value contributes \(4\).

Mathematical Approach

The key idea is to treat the problem as a reachability problem on the interval \(0,1,\dots,n^2\). Each construction marks certain counts of ones, and the final sum only depends on how many counts fall into each complexity class.

Step 1: Complexity 1

Complexity \(1\) means every row is identical and every column is identical. For a binary square matrix that happens only for the all-zero matrix and the all-one matrix, so

$m_n(0)=m_n(n^2)=1.$

These two endpoints are the only values with complexity \(1\), and they account for the constant term in the final counting identity.

Step 2: Complexity 2

For the two-type constructions used by the implementations, the \(n\) indices are split into two groups of sizes \(a\) and \(b\) with

$a+b=n.$

The admissible block patterns reduce to three independent weights:

$a^2,\qquad b^2,\qquad 2ab.$

Hence, for each split \(a+b=n\), the implementation enumerates the seven nonempty subset sums

$a^2,\ b^2,\ 2ab,\ a^2+b^2,\ a^2+2ab,\ b^2+2ab,\ a^2+b^2+2ab=n^2,$

and then discards the endpoints \(0\) and \(n^2\), which were already handled in the complexity-1 case. The union over all \(a\) gives the full set of counts with complexity \(2\).

Step 3: A Simple Family with Complexity at Most 3

Before the full three-type analysis, the implementations mark the explicit product family

$k=ab,\qquad k=n^2-ab,\qquad 0\le a,b\le n.$

The second value follows from complementation: replacing every \(0\) by \(1\) preserves the numbers of distinct rows and columns, so achievable counts come in complementary pairs \(k\leftrightarrow n^2-k\). This inexpensive family already covers many values with complexity at most \(3\).

Step 4: Complexity at Most 3 from Three Types

The main construction splits \(n\) into three parts

$a+b+c=n,\qquad a\le b\le c.$

A three-type pattern is encoded by a binary \(3\times3\) template. The implementations enumerate all \(2^9=512\) templates, keep only those whose three rows are pairwise distinct, whose three columns are pairwise distinct, and whose row-pattern multiset matches the column-pattern multiset. After deduplication, this leaves exactly \(46\) distinct coefficient tuples.

For every surviving template, the number of ones has the quadratic form

$k=d_1a^2+d_2b^2+d_3c^2+e_{ab}ab+e_{ac}ac+e_{bc}bc,$

where each diagonal coefficient satisfies \(d_i\in\{0,1\}\) and each mixed coefficient satisfies \(e_{ab},e_{ac},e_{bc}\in\{0,1,2\}\). The diagonal terms count within-type blocks, while the mixed terms count cross-type blocks. Evaluating all \(46\) forms over all ordered partitions \(a\le b\le c\) marks every value reached by this three-type construction.

Step 5: Turn Reachability into \(C(n)\)

Let

$T=n^2+1,$

$N_2=\#\{k: m_n(k)=2\},\qquad N_{\le 3}=\#\{k: m_n(k)\le 3\},\qquad N_4=T-N_{\le 3}.$

Since exactly two values have complexity \(1\), we obtain

$C(n)=2+2N_2+3(N_{\le 3}-N_2-2)+4N_4.$

Simplifying gives the identity used by the implementations:

$C(n)=3T-4-N_2+N_4.$

So the task is reduced to marking the complexity-2 set and the complexity-\(\le 3\) set, then counting how many integers lie in each.

Worked Example: \(n=5\)

For \(n=5\), we have \(T=5^2+1=26\). The complexity-2 construction marks exactly

$\{1,4,8,9,12,13,16,17,21,24\},$

so \(N_2=10\). The combined complexity-\(\le 3\) construction covers all values \(0,1,\dots,25\), hence \(N_4=0\).

Therefore

$C(5)=3\cdot 26-4-10+0=64.$

The same result can be read directly from the complexity classes:

$1+1+10\cdot 2+14\cdot 3=64.$

So only \(0\) and \(25\) have complexity \(1\), ten values have complexity \(2\), and the remaining fourteen values have complexity \(3\).

How the Code Works

The C++, Python, and Java implementations use the same pipeline. First they generate the finite catalogue of \(46\) three-type coefficient tuples from the \(512\) binary \(3\times3\) templates. Next they allocate two reachability containers over the interval \(0\) through \(n^2\): one container for values with complexity at most \(3\), and one container for values with complexity \(2\). The C++ and Java implementations pack these states into bitsets, while the Python implementation stores them in byte arrays.

After that, the implementation marks the simple family \(ab\) and \(n^2-ab\), precomputes the squares \(0^2,1^2,\dots,n^2\), and loops over all ordered partitions \(a\le b\le c\) with \(a+b+c=n\). For each partition it evaluates the \(46\) quadratic forms and marks the resulting counts. A separate loop over all \(a+b=n\) marks the seven nonempty subset sums built from \(a^2\), \(b^2\), and \(2ab\), ignoring \(0\) and \(n^2\). Finally it counts the marked positions and applies

$C(n)=3(n^2+1)-4-N_2+\bigl((n^2+1)-N_{\le 3}\bigr).$

The C++ implementation also checks the known values \(C(5)=64\), \(C(10)=274\), and \(C(20)=1150\) before evaluating the full target input.

Complexity Analysis

The template generation is constant work because the search space has only \(512\) patterns. Marking the product family costs \(O(n^2)\) time. The main partition loop has \(O(n^2)\) states, since \(a\le b\le c\) and \(a+b+c=n\), and each state evaluates only \(46\) constant-size quadratic forms. The complexity-2 loop is \(O(n)\). Therefore the overall running time is \(O(n^2)\).

Memory usage is dominated by the two reachability containers on \(0,\dots,n^2\). The packed C++ and Java versions use \(\Theta(n^2)\) bits, while the Python version uses \(\Theta(n^2)\) bytes for the same logical state space.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=782
2. Binary matrix: Wikipedia — Binary matrix
3. Bit array: Wikipedia — Bit array
4. Quadratic form: Wikipedia — Quadratic form
5. Integer partition: Wikipedia — Integer partition