Contest Duration: - (local time) (100 minutes) Back to Home

G - Digits on Grid Editorial by en_translator

Consider the following undirected graph $$G$$:

• It has $$H$$ vertices $$a_1, a_2, \ldots, a_H$$ corresponding to each row and $$W$$ vertices $$b_1, b_2, \ldots, b_W$$ corresponding to each column, for a total of $$(H+W)$$ vertices.
• For each pair of integers $$(i, j)$$ such that $$1 \leq i \leq H$$ and $$1 \leq j \leq W$$, there is an undirected edge labeled $$c_{i, j}$$ between Vertex $$a_i$$ and Vertex $$b_j$$.
• There are no other vertices or edges.

Let $$\mathcal{R}$$ be the set of vertices corresponding to the rows, and $$\mathcal{C}$$ be the set of vertices corresponding to the columns. That is,

$$\mathcal{R} := \lbrace a_1, a_2, \ldots, a_H \rbrace$$
$$\mathcal{C} := \lbrace b_1, b_2, \ldots, b_W \rbrace$$

Note that $$G$$ is a bipartite graph whose vertices are divided into $$\mathcal{R}$$ and $$\mathcal{C}$$.

This problem can be rephrased as follows.

Starting from a vertex belonging to $$\mathcal{R}$$, we repeat “traveling from the current vertex to one of the adjacent vertices along the edge between them” $$2N$$ times. Find the number of different sequences of labels $$d_1d_2\ldots d_{2N}$$ that can be obtained by concatenating the labels on the traversed edges in order.

We will solve this problem with Dynamic Programming (DP). If we define DP table as

$$\mathrm{dp}[k][v] :=$$(the number of different sequences of labels $$d_1d_2\ldots d_k$$ corresponding to the first $$k$$ moves ending with vertex $$v$$),

the same sequences of label can be counted multiple times, so we cannot obtain the correct answer. This is because, for a sequence of label $$d_1d_2\ldots d_k$$, there may be in general multiple possible “current vertex $$v$$” right after traveling through the label sequence.
In order to deal with this issue, instead of single “terminal vertex $$v$$”, we use “the set of all possible terminal vertices as the results of the label sequence” for each label sequence $$d_1d_2\ldots d_k$$, so that the object and the sequence of labels correspond one-by-one, and thus counted without any duplicates.

In other words, we fill the DP table defined as:

$$\mathrm{dp}[k][S] :=$$（The number of different sequences of labels of length $$k$$ such that the set of possible terminal vertices after traversing those labels in the sequences is $$S$$).

Since graph $$G$$ is a bipartite graph,

• after even number of moves, the current vertex is limited to those in $$\mathcal{R}$$;
• after odd number of moves, the current vertex is limited to those in $$\mathcal{C}$$.

Therefore,

when considering $$\mathrm{dp}[k][S]$$, it is sufficient to consider

• only $$S$$ such that $$S \subseteq \mathcal{R}$$ when $$k$$ is event;
• only $$S$$ such that $$S \subseteq \mathcal{C}$$ when $$k$$ is odd.

Therefore, the number of states of DP to consider is $$\mathrm{O}(N(2^H + 2^W))$$.

We will now describe the specific steps of DP.

First, as the initial state of DP, we consider the case of $$k = 0$$, that is, $$\mathrm{dp}[0][\ast]$$. Since the initial position before the first move can be chosen from arbitrary vertex belonging to $$\mathcal{R}$$, so

$$\mathrm{dp}[0][\mathcal{R}] = 1$$;
$$\mathrm{dp}[0][S] = 0, \,\,\text{for}\,\,S \neq \mathcal{R}$$.

Next, we consider the transitions of the DP.
Consider a sequence of labels $$d_1 d_2 \ldots d_k$$ of length $$k$$. Also, let $$S$$ be the set of possible vertices right after traversing through these labels.
Then, for a label sequence $$d_1 d_2 \ldots d_kc$$ where digit $$c$$ is appended to the original one, let $$S'_c$$ be the set of all possible vertices right after traversing through them; then

• If $$k$$ is even, then $$S'_c = \lbrace b_j :$$ there exists $$i \in S$$ such that $$c_{i, j} = c$$;
• If $$k$$ is odd, then $$S'_c = \lbrace a_i :$$ there exists $$j \in S$$ such that $$c_{i, j} = c$$.

Based on these fact, it is sufficient to perform the following nine transitions:

• $$\mathrm{dp}[k+1][S'_1] \leftarrow \mathrm{dp}[k+1][S'_1] + \mathrm{dp}[k][S]$$
• $$\mathrm{dp}[k+1][S'_2] \leftarrow \mathrm{dp}[k+1][S'_2] + \mathrm{dp}[k][S]$$
• $$\mathrm{dp}[k+1][S'_3] \leftarrow \mathrm{dp}[k+1][S'_3] + \mathrm{dp}[k][S]$$
• $$\cdots$$
• $$\mathrm{dp}[k+1][S'_9] \leftarrow \mathrm{dp}[k+1][S'_9] + \mathrm{dp}[k][S]$$

each of which corresponds to the nine cases where the final digit $$c$$ are $$1$$ to $$9$$, respectively.

By filling the DP table with the initializations and transitions above, the answer for this problem is obtained as

$$\displaystyle\sum_{S \in \mathcal{R}} \mathrm{dp}[2N][S] - \mathrm{dp}[2N][\emptyset]$$.

Therefore, the problem has been solved in a total of $$O(N(2^H+2^W))$$ time.

posted:
last update: