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

## F - Cleaning Robot Editorial by en_translator

For convenience, we interpret “executing a program consisting of a $$k$$-time concatenation of string $$S$$” as “executing string $$S$$ for $$K$$ times.”

Let us denote by $$(0, 0) \rightarrow (x_1, y_1) \rightarrow (x_2, y_2) \rightarrow \cdots \rightarrow (x_{|S|}, y_{|S|})$$ the transitions of Robot’s position. Here, $$|S|$$ denotes the length of $$S$$.
Let $$a, b$$ be $$x_{|S|}, y_{|S|}$$, respectively.

Let $$V_1$$ be a set of squares which robot visits during the first time of execution (including the initial position before the first execution $$(0, 0)$$). In other words, $$V_1$$ is a set consisting of $$(0, 0), (x_1, y_1), (x_2, y_2), \cdots, (x_{|S|}, y_{|S|})$$, without duplicates. Let us arbitrarily number the elements of $$V_1$$, denoting

$$V_1 = \lbrace (X_1, Y_1), (X_2, Y_2), \ldots, (X_N, Y_N) \rbrace$$.

Here, $$N$$ is the number of elements of $$V_1$$.
Then, set $$V_2$$, the set of squares which robot visits during the second time of execution (including the initial position before the second execution), can be obtained by shifting each element of $$V_1$$ by $$(a, b)$$:

$$V_2 = \lbrace (X_1 + a, Y_1 + b), (X_2 + a, Y_2 + b), \ldots, (X_N + a, Y_N + b) \rbrace$$.

Set $$V_3$$, the set of squares which robot visits during the third time of execution (including the initial position before the third execution), can be obtained by again shifting each element of $$V_2$$ by $$(a, b)$$:

$$V_3 = \lbrace (X_1 + 2a, Y_1 + 2b), (X_2 + 2a, Y_2 + 2b), \ldots, (X_N + 2a, Y_N+ 2b) \rbrace$$.

Generally, set $$V_k$$, the set of squares which robot visits during the $$K$$-th time of execution (including the initial position before the $$K$$-th execution), can be represented as:

$$V_k = \lbrace (X_1 + (k-1)a, Y_1 + (k-1)b), (X_2 + (k-1)a, Y_2 + (k-1)b), \ldots, (X_N + (k-1)a, Y_N+ (k-1)b) \rbrace$$.

Especially note that, for $$i = 1, 2, \ldots, N$$, $$(X_i, Y_i) \in V_1$$ corresponds to:

• $$(X_i + a, Y_i + b)$$ for the second execution;
• $$(X_i + 2a, Y_i + 2b)$$ for the third execution;
• $$\cdots$$
• $$(X_i + (k-1)a, Y_i + (k-1)b)$$ for the $$k$$-th execution.

Here, for $$i = 1, 2, \ldots, N$$, let

$$d_i$$ := （minimum integer $$j$$ such that $$(X_i+ja, Y_i+jb) \in V_1$$

If there does not exist such integer $$j$$, we define $$d_i := \infty$$.

Then, focusing $$(X_i, Y_i) \in V_1$$, as for the first $$d_i$$ executions,

• it visits Square $$(X_i, Y_i)$$ for the first time during the first execution;
• it visits Square $$(X_i + a, Y_i + b)$$ for the first time during the second execution;
• it visits Square $$(X_i + 2a, Y_i + 2b)$$ for the first time during the third execution;
• $$\cdots$$
• it visits Square $$(X_i + (d_i-1)a, Y_i + (d_i-1)b)$$ for the first time during the $$d_i$$-th execution.

However, for $$(d_i+1)$$-th execution and later,

• it visits Square $$(X_i + d_ia, Y_i + d_ib)$$ during the $$(d_i+1)$$-th execution, but this is not his first visit there.
(By the definition of $$d_i$$, $$(X_i + d_ia, Y_i + d_ib) \in V_1$$, so it already visited during the first execution)
• it visits Square $$(X_i + (d_i+1)a, Y_i + (d_i+1)b)$$ during the $$(d_i+2)$$-th execution, but this is not his first visit there.
($$(X_i + (d_i+1)a, Y_i + (d_i+1)b) = ((X_i+d_ia) + a, (Y_i+d_ib) + b)$$, so it already visited during the second execution)
• it visits Square $$(X_i + (d_i+2)a, Y_i + (d_i+2)b)$$ during the $$(d_i+3)$$-th execution, but this is not his first visit there.
($$(X_i + (d_i+2)a, Y_i + (d_i+2)b) = ((X_i+d_ia) + 2a, (Y_i+d_ib) + 2b)$$, so it already visited during the third execution)
• $$\cdots$$

and so on.
Therefore, while executing $$S$$ for $$K$$ times, this $$(X_i, Y_i)$$ changes an unvisited square to a visited one $$\min(d_i, K)$$ times.

Therefore, the answer for this problem is

$$\displaystyle\sum_{i = 1}^N \min(d_i, K)$$.

Thus, this problem boils down to finding $$d_i$$ for all $$i = 1, 2, \ldots, N$$. We will explain how to do it.

If $$a = b = 0$$, we can see that $$d_1 = d_2 = \cdots = d_N = 1$$. Also, if $$a = 0, b \neq 0$$, we can swap the role of $$X$$ coordinates and $$Y$$ coordinates to assume that $$a \neq 0$$, so we hereinafter assume $$a \neq 0$$.

First, for each $$i = 1, 2, \ldots, N$$, we calculate

$$q_i = \left\lfloor \displaystyle\frac{X_i}{a} \right\rfloor$$

$$s_i = X_i - q_i a$$

$$t_i = Y_i - q_i b$$,

and group the elements of $$V_i$$ depending on $$(s_i, t_i)$$. ( We define that $$(X_i, Y_i)$$ and $$(X_j, Y_j)$$ belongs to the same group if and only if $$(s_i, t_i) = (s_j, t_j)$$.)

For any $$1 \leq i, j \leq N$$,

$$(s_i, t_i) = (s_j, t_j) \Leftrightarrow (X_j, Y_j) = (X_i + (q_j-q_i)a, Y_i + (q_j-q_i)b)$$,

so by sorting the elements of each group by $$q_i$$, we can “find the value of $$d_i$$ for each $$i = 1, 2, \ldots, N$$ in a total of $$\mathrm{O}(|S|\log|S|)$$ time.”

Therefore, we can solve this problem in a total of $$\mathrm{O}(|S|\log|S|)$$ time.

posted:
last update: