Cost of Coloring

The clean way to model the process is this:

Give every row and column a label: the color used the last time that line is painted. If a line is never painted, pretend its label is $0$.

For any cell, the final color is the color of the later-painted endpoint. Since operation colors never decrease, this is just

$color(i,j)=\max(R_i,C_j).$

Same-color order does not matter. If both endpoints have color $5$, the cell is $5$ either way. Shocking, I know.

Why the labels are unique

For a beautiful coloring, color $1$ appears. In a max-table $\max(R_i,C_j)$, color $1$ can appear only if some row has label $1$ and some column has label $1$.

Once that is true, labels are recoverable from the grid:

• for any row $i$, using a column with label $1$ gives $\min_j color(i,j)=R_i;$
• similarly, for any column $j$, $\min_i color(i,j)=C_j.$

So counting valid label assignments is the same as counting colorings. No hidden overcounting nonsense.

The value of one label assignment

Suppose exactly $r$ rows have label $1$, and exactly $c$ columns have label $1$.

Every row/column with label greater than $1$ is forced to be painted. For example, if row $i$ has label $x>1$, take any column with label $1$; the cell at their intersection has color $x$, so row $i$ must be painted. Same argument for columns.

So all higher-colored lines cost

$n-r+m-c$

operations.

What about the color-$1$ rows and columns? Their only job is to color the $r\times c$ submatrix where both endpoints have label $1$. To cover every cell of this complete bipartite grid, we need either its row or its column painted. The minimum vertex cover of $K_{r,c}$ has size

$\min(r,c).$

Therefore the minimum number of operations is

$$(n-r)+(m-c)+\min(r,c)=n+m-\max(r,c).$$

That is the main punchline.

So if the value is $s$, define

$t=n+m-s.$

Then we need

$\max(r,c)=t.$

Counting when higher colors are just allowed

First ignore the condition that every color $2,3,\dots,k$ appears.

Let $x$ be the number of allowed higher colors. We force color $1$ to appear by choosing:

• $r\ge 1$ rows with label $1$,
• $c\ge 1$ columns with label $1$.

The remaining $n-r$ rows and $m-c$ columns can independently choose any of the $x$ higher colors.

For fixed $r,c$, this gives

$$\binom nr\binom mc x^{n-r}x^{m-c}.$$

For value $s=n+m-t$, we need $\max(r,c)=t$. So define

$$A_x[s] = \sum_{\substack{1\le r\le n,\ 1\le c\le m\\ \max(r,c)=t}} \binom nr\binom mc x^{n-r+m-c}.$$

Compute that with prefix sums:

$$A_x[n+m-t] = \left(\sum_{r=1}^{t}\binom nr x^{n-r}\right) \left(\sum_{c=1}^{t}\binom mc x^{m-c}\right) - \left(\sum_{r=1}^{t-1}\binom nr x^{n-r}\right) \left(\sum_{c=1}^{t-1}\binom mc x^{m-c}\right).$$

When $t$ is bigger than $n$ or $m$, the sum just stops at that dimension.

Forcing all $k$ colors

The formula $A_x$ counts colorings where color $1$ appears, and all other used colors are chosen from some allowed set of size $x$.

A higher color appears in the grid iff it appears as at least one row/column label, because there is a label-$1$ line on the opposite side.

So we use inclusion-exclusion over the $k-1$ higher colors:

$$ans_s= \sum_{j=0}^{k-1}(-1)^j\binom{k-1}{j}A_{k-1-j}[s].$$

That removes labelings missing at least one required higher color.

Complexity

For each $x=0,1,\dots,k-1$, compute the row and column prefix sums and add its inclusion-exclusion contribution to every answer. This is

$O(k(n+m))$

plus factorial precomputation, easily fine for $n,m\le 2000$.