Editorial for COI '19 #3 Semafor

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

We will solve the harder case $M = 2$ ~M = 2~.

We represent a state of the board by a bitmask of $10$ ~10~ bytes. Call a bitmask nice if the represented board shows a valid number.

It is well known that the vertices of the hypercube graph are all bitmasks of some size ( $10$ ~10~ here), and the edges connect bitmasks which differ in exactly one place. Let $H$ ~H~ denote the adjacency matrix of the hypercube.

Then the problem, formally, asks for the following: for each nice bitmask $Y$ ~Y~, find the number of walks of length $N$ ~N~ from $X$ ~X~ to $Y$ ~Y~ of length $N$ ~N~ in the hypercube, such that the walk visits the set of nice bitmasks every $K$ ~K~ steps.

Claim 1: The number of walks of length $D$ ~D~ in the hypercube, starting in $X$ ~X~ and ending in $Y$ ~Y~, equals the $(X, Y)$ ~(X, Y)~-th entry in the matrix $H^D$ ~H^D~.

Proof: Look into Daniel A. Spielman's "Spectral and Algebraic Graph Theory", brilliant stuff. For an elementary proof, it's Lemma 3 on this link. □

Definition 2: Let $B$ ~B~ be the principal submatrix of $H^K$ ~H^K~ indexed by only the rows and columns of the nice bitmasks.

Claim 3: The number of walks (from $X$ ~X~ to $Y$ ~Y~) of length $N$ ~N~ in the hypercube, where $K$ ~K~ divides $N$ ~N~, such that every $K$ ~K~ steps the walk visits a nice bitmask, equals the $(X, Y)$ ~(X, Y)~-th entry in the matrix $B^{N/K}$ ~B^{N/K}~.

Proof: Left as an exercise. □

There are several steps in the solution. We need to calculate the matrix $B$ ~B~, then calculate $B^{N/K}$ ~B^{N/K}~, and then multiply it with the matrix corresponding to the last $N \bmod K$ ~N \bmod K~ steps. We omit the third because it is very similar to the first step, so we assume $K$ ~K~ divides $N$ ~N~ in the rest of the editorial.

Let us solve the second step (raising $B$ ~B~ to the $N/K$ ~N/K~-th power) first. It is enough to use naive binary exponentiation and multiply two matrices in the ordinary cubic complexity, because for $M = 2$ ~M = 2~ we are dealing with $100 \times 100$ ~100 \times 100~ matrices.

The first step is tougher, because $B$ ~B~ is a submatrix of $H^K$ ~H^K~, and $H$ ~H~ is a $1024 \times 1024$ ~1024 \times 1024~ matrix for $M = 2$ ~M = 2~. Naive calculation of $H^K$ ~H^K~ passes only the subtask $M = 1$ ~M = 1~. For smaller $K$ ~K~ and $M = 2$ ~M = 2~, it can be done with clever dynamic programming, and this should give the first four subtasks.

For the full problem, we need to raise the hypercube matrix to some power faster.

Claim 4: The $(X, Y)$ ~(X, Y)~-th entry of the matrix $B$ ~B~ depends only on the number of bits in which the bitmasks $X$ ~X~ and $Y$ ~Y~ differ.

Proof: Without loss of generality, we can XOR all vertices of the hypercube with some fixed bitmask. Thus, we can assume $X = 0$ ~X = 0~. It's also clear that the order of the bits doesn't matter at all. Hence, the number of walks from $0$ ~0~ to $Y$ ~Y~ depends only on the bitcount of $Y$ ~Y~.

Claim 4 shows that it's enough to calculate the first row of the matrix $H^K$ ~H^K~. Depending on the exact implementation, it can pass the first five subtasks, or even pass the whole problem. (Ask Dorijan Lendvaj for the XOR-convolution solution of quadratic complexity that runs faster than the official solution.)

The official solution calculates the numbers of walks starting in $X = 0$ ~X = 0~ in a smarter way. It's enough to calculate, for every $0 \le r \le 10$ ~0 \le r \le 10~, the number of walks starting from bitcount $0$ ~0~ and ending in bitcount $r$ ~r~.

The number of ways in which we can get from one bitcount $0 \le r \le 10$ ~0 \le r \le 10~ to another is given by the following $11 \times 11$ ~11 \times 11~ matrix:

$\displaystyle C = \begin{bmatrix} 0 & 10 & 0 & 0 & \dots & 0 & 0 & 0 \\ 1 & 0 & 9 & 0 & \dots & 0 & 0 & 0 \\ 0 & 2 & 0 & 8 & \dots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \dots & 9 & 0 & 1 \\ 0 & 0 & 0 & 0 & \dots & 0 & 10 & 0 \end{bmatrix}$

By raising the matrix $C$ ~C~ to a suitable power, we can get the number of walks of length $K$ ~K~ from bitcount $0$ ~0~ to each bitcount $0 \le r \le 10$ ~0 \le r \le 10~. To get the actual number of walks in the hypercube, we just need to divide by a suitable binomial coefficient, due to symmetry.

There is an even faster solution, which uses exponential generating functions. The number of walks of length $K$ ~K~ from the bitmask $0$ ~0~ to some bitmask with $10-r$ ~10-r~ bits equals the coefficient next to $\frac{x^K}{K!}$ ~\frac{x^K}{K!}~ of the following expression:

$\displaystyle \left(\sum_{i=0}^\infty \frac{x^{2i}}{(2i)!}\right)^r \left(\sum_{i=0}^\infty \frac{x^{2i+1}}{(2i+1)!}\right)^{10-r} = \left(\frac{e^x+e^{-x}}{2}\right)^r \left(\frac{e^x-e^{-x}}{2}\right)^{10-r}$

By expanding the expression carefully, we get a solution of the complexity $\mathcal O((5M)^2 + (5M) \log K)$ ~\mathcal O((5M)^2 + (5M) \log K)~, that is, calculating entries of the $n \times n$ ~n \times n~ hypercube matrix raised to some power $K$ ~K~ is possible in time $\mathcal O(\log n \log K)$ ~\mathcal O(\log n \log K)~.

For similar ideas, look into Herbert Wilf's free book generatingfunctionology.

Comments

There are no comments at the moment.