AtCoder Grand Contest 050 (Good Bye rng_58 Day 1)

AtCoder Grand Contest 050 (Good Bye rng_58 Day 1)

Source codes

• My submissions (AtCoder)
• My source codes (GitHub)

Solutions

A - AtCoder Jumper

B - Three Coins

C - Block Game

D - Shopping

E - Three Traffic Lights

We assume $0$-indexed both for time and for the traffic lights. Let $m _ i = g _ i + r _ i$ be the period of the traffic light $i$.

Overview

In my opinion, the reasons this problem is hard to solve can be divided into two pieces.

1. Chinese remainder theorem itself is useless, but its proof is critical.
   • We notice that this problem is related to Chinese remainder theorem. However, we cannot apply it for them directly since none of the two of $m _ 0$, $m _ 1$ and $m _ 2$ has to be coprime. In fact, we should not stick to this famous theorem to make this problem computable.
   • However, its proof is useful. Reduction of $m _ 0$, $m _ 1$, $m _ 2$ is a key to the solution. Its condition is induced very naturally once we understand a proof of Chinese remainder theorem.
2. One side of the paraphrases for time $x$ and its remainders $a _ 0$, $a _ 1$, $a _ 2$ is trivial, but the other side is hard to notice.
   • For counting up, first, we convert $x$’s condition into its remainders’. This is what everyone does in their first observation. It is so trivial that we do not come up with its reverse side. In this article, we discuss this point clearly.

I feel that these are also beautiful points particular in this problem. It requires that we thoroughly promote mathematical considerations by our brain and after that we try all the possibilities by our program. This must be rng_58-san’s favorite.

First Observation

We are working on $x \in [0, \mathop{\mathrm{lcm}}(m _ 0, m _ 1, m _ 2))$. Then, the problem requires that we should count the number of $(a _ 0, a _ 1, a _ 2) \in [0, g _ 0) \times [0, g _ 1) \times [0, g _ 2)$ that satisfies \[ \left( \exists x \in \mathbb{Z} \right) \left( \left\{ \begin{array}{l} x = a _ 0 \mod (m _ 0), \\
x = a _ 1 \mod (m _ 1), \\
x = a _ 2 \mod (m _ 2) \end{array} \right. \right). \tag{E.1} \] We find $m _ 0’$ that is simpler than $m _ 0$ so that (E.1) is equivalent to the following condition. \[ \left( \exists x \in \mathbb{Z} \right) \left( \left\{ \begin{array}{l} x = a _ 0 \mod (m _ 0’), \\
x = a _ 1 \mod (m _ 1), \\
x = a _ 2 \mod (m _ 2) \end{array} \right. \right). \tag{E.2} \] Note that both (E.1) and (E.2) are existence conditions for $x$. This is important for the following reasons.

• We do not have to choose the same $x$ in (E.1) and (E.2).
• We do not have to care concrete $x$ for (E.1) and (E.2) when we seek $m _ 0’$. Just existence is suffice.

Before finding good $m _ 0’$, we develop an extended version of Chinese remainder theorem. Though Chinese remainder theorem and its extension will not be clues for solutions, the proof of them will be a strong weapon.

Extended Chinese Remainder Theorem

Remark E.1: I would like to argue Chinese remainder theorem in terms of rings. But if you prefer concrete arguments, you just let $R = \mathbb{Z}$, $I = (m _ 0)$, $R / I = \mathbb{Z} / (m _ 0)$ and so on. If so, note that \[ \begin{align} (m _ 0) &= \{ \text{multiples of } m _ 0 \}, \\
\mathbb{Z} / (m _ 0) &= \{ \text{quotients of the diviser $m _ 0$} \}, \\
(m _ 0) \cap (m _ 1) &= (\mathop{\mathrm{lcm}}(m _ 0, m _ 1)), \\
(m _ 0) + (m _ 1) &= (\gcd(m _ 0, m _ 1)). \end{align} \]

We promise that when we call $R$ a ring, $R$ is a unitary commutative ring.

Theorem E.2: Let $R$ be a ring. Let $I, J \subset R$ be ideals. Let $f \colon R \to R / I \times R / J$ be a homomorphism defined by \[ f(x) = \left( x \mod I, x \mod J \right). \tag{E.3} \] Then, the following 1. - 3. hold.

1. $\ker f = I \cap J$.
2. It follows that \[ \begin{multline} \mathop{\mathrm{Im}} f = \{ z \in R / I \times R / J \mid \\\ (\exists x, y \in R)(z = \left( x \mod I, y \mod J \right) \\\ \land x = y \mod I + J) \}. \tag{E.3’} \end{multline} \]
3. $R/(I \cap J) \cong \mathop{\mathrm{Im}} f$.

Proof: For 1., the argument is the same as the proof for Chinese remainder theorem. We omit it. For 2., let $S$ be the right-hand side of (E.3’). It is easy to show that $\mathop{\mathrm{Im}} f \subset S$. Let $z \in S$. Then, there exist $x, y \in R$ that satisfies $z = (x \mod I, y \mod J)$ and $x = y \mod I + J$. By definition of sum of ideals, there exists $a \in I$ and $b \in J$ that satisfies $x - y = b - a$. Letting $w = x + a = y + b$, we see that $f(w) = (x \mod I, y \mod J) = z$. i.e., $z \in \mathop{\mathrm{Im}} f$. Therefore, $S \subset \mathop{\mathrm{Im}} f$. Combining the result above, we see that $S = \mathop{\mathrm{Im}} f$. For 3., we apply fundamental homomorphism theorem for $f$. (qed)

In Chinese remainder theorem, we add an assumption that $I + J = R$ to obtain an isomorphic $R / (I \cap J) \cong R / I \times R / J$.

The correspondence between $x$ and $(a _ 0, a _ 1, a _ 2)$

Before applying Theorem E.2 to our problem, we think twice of our first consideration where we actually used the following proposition.

Proposition E.3: We consider the following system again. \[ \left\{ \begin{array}{l} x = a _ 0 \mod (m _ 0), \\
x = a _ 1 \mod (m _ 1), \\
x = a _ 2 \mod (m _ 2). \end{array} \right. \tag{E.1’} \] It follows that \[ \begin{align} &\sharp\{ x \in [0, \mathop{\mathrm{lcm}}(m _ 0, m _ 1, m _ 2) ) \mid 0 \leq x \% m _ i < g _ i \text{ for } i = 0, 1, 2. \} \\
= &\sharp\{ (a _ 0, a _ 1, a _ 2) \in [0, g _ 0) \times [0, g _ 1) \times [0, g _ 2) \mid (\exists x \in \mathbb{Z})(\text{(E.1’) holds.}) \}. \tag{E.4} \end{align} \]

You may think that this is obvious and trivial, but in my opinion, this is a critical key when we come to the final obstacle to obtain our solution later.

Proof: We define $f \colon \mathbb{Z} \to \mathbb{Z} / (m _ 0) \times \mathbb{Z} / (m _ 1) \times \mathbb{Z} / (m _ 2)$ by \[ f(x) = (x \mod m _ 0, x \mod m _ 1, x \mod m _ 2). \] By the same argument in Theorem E.2, we have a ring isomorphic $\mathbb{Z} / ((m _ 0) \cap (m _ 1) \cap (m _ 2)) \cong \mathop{\mathrm{Im}} f$. By definition of image, \[ \mathop{\mathrm{Im}} f = \{ z \in \mathbb{Z} / (m _ 0) \times \mathbb{Z} / (m _ 1) \times \mathbb{Z} / (m _ 2) \mid (\exists x \in \mathbb{Z})(f(x) = z) \}. \] Letting $z = (a _ 0 \mod m _ 0, a _ 1 \mod m _ 1, a _ 2 \mod m _ 2)$, we have \[ \begin{multline} \mathop{\mathrm{Im}} f = \{ (a _ 0 \mod m _ 0, a _ 1 \mod m _ 1, a _ 2 \mod m _ 2) \\\ \in \mathbb{Z} / (m _ 0) \times \mathbb{Z} / (m _ 1) \times \mathbb{Z} / (m _ 2) \mid \\\ (\exists x \in \mathbb{Z})(\text{(E.1’) holds.}) \}. \end{multline} \] Let $\tilde{f} \colon \mathbb{Z} / ((m _ 0) \cap (m _ 1) \cap (m _ 2)) \to \mathop{\mathrm{Im}} f$ be an isomorphism induced by $f$. From $\tilde{f}$, we take one representative element from each quotient set to obtain a bijection $g \colon [0, \mathop{\mathrm{lcm}}(m _ 0, m _ 1, m _ 2)) \to G$ which is defined by \[ g(x) = (x \% m _ 0, x \% m _ 1, x \% m _ 2), \] where we set \[ G = \{ (a _ 0, a _ 1, a _ 2) \in [0, m _ 0) \times [0, m _ 1) \times [0, m _ 2) \mid (\exists x \in \mathbb{Z})(\text{(E.1’) holds.}) \}. \] Note that $\tilde{f}$ is an ring isomorphism wheres $g$ is just a bijection. Next, we restrict $g$’s range and domain as follows. We set \[ G’ = \{ (a _ 0, a _ 1, a _ 2) \in G \mid 0 \leq a _ i < g _ i \text{ for } i = 0, 1, 2. \}, \] and we set $\tilde{g} \colon g ^ {-1} (G’) \to G’$ induced by $g$. Now we see that \[ \begin{align} G’ &= \{ (a _ 0, a _ 1, a _ 2) \in [0, g _ 0) \times [0, g _ 1) \times [0, g _ 2) \mid (\exists x \in \mathbb{Z})(\text{(E.1’) holds.}) \}, \\
g ^ {-1} (G’) &= \{ x \in [0, \mathop{\mathrm{lcm}}(m _ 0, m _ 1, m _ 2) ) \mid 0 \leq x \% m _ i < g _ i \text{ for } i = 0, 1, 2. \}. \end{align} \] Since $\tilde{g}$ is a bijection, we have (E.4) as desired. (qed)

Reduction of mods

For the case of twins

We come back to the proposition “(E.1) $\Longleftrightarrow$ (E.2)”. But before the normal case, we consider the case of twins so that we can apply Theorem E.2. We seek for the sufficient condition of the proposition “(E.5) $\Longleftrightarrow$ (E.6)” defined as follows. \[ \begin{align} \left( \exists x \in \mathbb{Z} \right) \left( \left\{ \begin{array}{l} x = a _ 0 \mod (m _ 0), \\
x = a _ 1 \mod (m _ 1) \end{array} \right. \right), \tag{E.5} \\
\left( \exists x \in \mathbb{Z} \right) \left( \left\{ \begin{array}{l} x = a _ 0 \mod (m _ 0’), \\
x = a _ 1 \mod (m _ 1) \end{array} \right. \right). \tag{E.6} \end{align} \]

Lemma E.4: The following condition is sufficient for the proposition that (E.5) is equivalent to (E.6). \[ \gcd (m _ 0, m _ 1) = \gcd (m _ 0’, m _ 1). \tag{E.7} \]

Proof: We consider (E.5) with $f$ defined by (E.3). The condition (E.5) is equivalent to the following. \[ (\exists x \in \mathbb{Z}) \left( f(x) = (a _ 0 \mod (m _ 0), a _ 1 \mod (m _ 1)) \right), \] which is equivalent to \[ (a _ 0 \mod (m _ 0), a _ 1 \mod (m _ 1)) \in \mathop{\mathrm{Im}} f. \] By Theorem E.2.2, this is equivalent to the following. \[ a _ 0 = a _ 1 \mod (m _ 0) + (m _ 1). \tag{E.8} \] Here we note that $(m _ 0), (m _ 1) \subset (m _ 0) + (m _ 1)$. By the same argument, we see that (E.6) is equivalent to the following. \[ a _ 0 = a _ 1 \mod (m _ 0’) + (m _ 1). \tag{E.9} \] If we assume (E.7), we actually see that (E.8) is equivalent to (E.9) by definition of $\gcd$. (qed)

For the case of triples

By Lemma E.4, we obtain the result for triples.

Lemma E.5: The following condition is sufficient for the proposition that (E.1) is equivalent to (E.2). \[ \gcd (m _ 0, \mathop{\mathrm{lcm}}(m _ 1, m _ 2)) = \gcd (m _ 0’, \mathop{\mathrm{lcm}}(m _ 1, m _ 2)). \tag{E.10} \]

Proof: If there is no $x \in \mathbb{Z}$ satisfying $x = a _ 1 \mod (m _ 1)$ and $x = a _ 2 \mod (m _ 2)$, (E.1) is equivalent to (E.2). Hereinafter, we assume that there exists $x \in \mathbb{Z}$ satisfying these equations.

Then, we have $(a _ 1 \mod (m _ 1), a _ 2 \mod (m _ 2)) \in \mathop{\mathrm{Im}} f’$ where $f’ \colon \mathbb{Z} \to \mathbb{Z} / (m _ 1) \times \mathbb{Z} / (m _ 2)$ defined by $f’(x) = (x \mod (m _ 1), x \mod (m _ 2))$. By Theorem E.2.3, there exists $a _ 1’ \in \mathbb{Z}$ so that $x = a _ 1’ \mod (m _ 1) \cap (m _ 2)$ and, for any $x \in \mathbb{Z}$ satisfying this equation, both $x = a _ 1 \mod (m _ 1)$ and $x = a _ 2 \mod (m _ 2)$ hold.

Therefore, (E.1) is equivalent to \[ \left( \exists x \in \mathbb{Z} \right) \left( \left\{ \begin{array}{l} x = a _ 0 \mod (m _ 0), \\
x = a _ 1’ \mod (m _ 1) \cap (m _ 2) \end{array} \right. \right), \] and (E.2) is equivalent to \[ \left( \exists x \in \mathbb{Z} \right) \left( \left\{ \begin{array}{l} x = a _ 0 \mod (m _ 0’), \\
x = a _ 1’ \mod (m _ 1) \cap (m _ 2) \end{array} \right. \right). \] We apply Lemma E.4 for these to complete the proof. (qed)

Computation of reductions

We argue how to apply (E.10) for our solution. Let \[ m _ i = \prod _ {j = 0}^{N - 1} p _ j ^ {\alpha _ {ij}} \] be prime factorization of $m _ i$ for $i = 0, 1, 2$. The meaning of (E.10) is that, for $j = 0, \dots, N - 1$, we can replace the maximum of $\alpha _ {0j}$, $\alpha _ {1j}$, $\alpha _ {2j}$ by the second-maximum of $\alpha _ {0j}$, $\alpha _ {1j}$, $\alpha _ {2j}$.

As a result, we can reduce the triple $(m _ 0, m _ 1, m _ 2)$ into $(m _ 1’, m _ 2’, m _ 3’)$ as follows. \[ \begin{align} m _ 0’ = g \cdot 1 \cdot b \cdot c, \\
m _ 1’ = g \cdot a \cdot 1 \cdot c, \\
m _ 2’ = g \cdot a \cdot b \cdot 1, \\
\end{align} \] where $g = gcd(m _ 0, m _ 1, m _ 2)$, $a$ is multiples of all the factors that is included in $m _ 1’ / g$ and $m _ 2’ / g$ but not included in $m _ 0’ / g$, and so on. In addition, we see that $\mathop{\mathrm{lcm}}(m _ 0’, m _ 1’, m _ 2’) = gabc$.

Coming up with a solution

Why is this reduction useful? Because we can use Proposition E.3 again as follows.

Recall that our aim is to count the triples $(a _ 0, a _ 1, a _ 2) \in [0, g _ 0) \times [0, g _ 1) \times [0, g _ 2)$ that satisfies \[ \left( \exists x \in \mathbb{Z} \right) \left( \left\{ \begin{array}{l} x = a _ 0 \mod (m _ 0’), \\
x = a _ 1 \mod (m _ 1’), \\
x = a _ 2 \mod (m _ 2’) \end{array} \right. \right). \tag{E.11} \]

Here, we are facing a multiplicity phenomenon. Generally speaking, it may occur that $g _ i \geq m _ i’$. Then, for a single $x$, there may be two or more $a _ i, a _ i’ \in [0, g _ i)$ satisfying $x = a _ i \mod (m _ i’)$ and $x = a _ i’ \mod (m _ i’)$. However, we can solve this difficulty. In this case, $a _ i = a _ i’ \mod (m _ i’)$ holds, i.e., $a _ i$ is single in $\mod (m _ i’)$. Therefore, we can count $a _ i \in [0, m _ i’)$ and multiply the result with the multiplicity of $a _ i$. We define $q _ i = g _ i / m _ i’$ and $r _ i = g _ i \% m _ i’$ for $i = 0, 1, 2$. We define a function $F$ as follows.

$F(l _ 0, l _ 1, l _ 2) = $ the number of the triples $(a _ 0, a _ 1, a _ 2) \in [0, l _ 0) \times [0, l _ 1) \times [0, l _ 2)$ that satisfies (E.11). Here, we consider $l _ i \in \{ r _ i, m _ i’ \}$ for each $i = 0, 1, 2$.

Then, there are $8$ triples for $(l _ 0, l _ 1, l _ 2)$. When we choose $l _ i = m _ i$, we sum up the result with multiplicity $q _ i$.

We consider how to calculate $F(l _ 0, l _ 1, l _ 2)$. Instead of counting $(a _ 0, a _ 1, a _ 2) \in [0, l _ 0) \times [0, l _ 1) \times [0, l _ 2)$ that satisfies (E.11), we apply Proposition E.3 to the case of (E.11) to count $x \in [0, \mathop{\mathrm{lcm}}(m _ 0’, m _ 1’, m _ 2’))$. This can be elementarily done. Thanks to the reduction above, we can just simulate about $x$.

Evaluation of periods

Without loss of generality, we assume $a \leq b \leq c$, which means $m _ 0’ \geq m _ 1’ \geq m _ 2’$. We have \[ b ^ 2 \leq gbc = m _ 0’ < m _ 0 \leq 2 \cdot 10 ^ {12}. \] Therefore, $a \leq b < 1.5 \cdot 10 ^ 6$. The number of change of the traffic lights $0$ and $1$ in $[0, gabc)$ is $2a$ and $2b$ respectively. Therefore, we can simulate the change of the traffic lights $0$ and $1$. In addition, we have \[ gabc \leq m _ 0’ a < 2 \cdot 10 ^ {12} \cdot 1.5 \cdot 10 ^ 6 = 3 \cdot 10 ^ {18}. \] Hence, $x$ can be represented as a $64$-bit integer.

Looking back to our path

Note that we took the following strategies.

• In “First Observation”, we decided to count $(a _ 0, a _ 1, a _ 2)$ instead of $x$.
• We reduced $(m _ 0, m _ 1, m _ 2)$ into $(m _ 0’, m _ 1’, m _ 2’)$ so that (E.1) was equivalent to (E.11) including the existence condition about $x$.
• In this observation, we converted our problem into simulation. This means that we decided to count $x$ instead of $(a _ 0, a _ 1, a _ 2)$. This is the reverse side of the first observation.

Implementation of Simulation

To make $F(l _ 0, l _ 1, l _ 2)$, we implement the following two steps.

1. We list up all the segments within $[0, gabc)$ in which both of the traffic lights $0$ and $1$ are green by simulation for time $x$.
2. For each segment $[l, r)$, we calculate the number of seconds in which the traffic light $2$ is also green.

We can implement 1. in a normal way. First, we list up the beginning time and the ending time for $i = 0$ and $1$. We call them events. and sort it by time. and sort it by time. Next, we sort events by time. Then, we do simulation of time through events to gather all the segments we are seeking.

We can calculate 2. in $O(1)$-time for each segments. We count how many times the segment overlaps $[km _ 2’, (k + 1)m _ 2’)$-type segments. We treat the left end and the right end as exceptions.

For a segment $[l, r)$, let $q = l / m _ 2’$, $s = l \% m _ 2’$, $q’ = r / m _ 2’$, $s’ = r \% m _ 2’$. The count is as follows.

• The left end: $\max(l _ 2 - s, 0)$,
• Medium: $(q’ - q - 1) l _ 2$,
• The right end: $\min(s’, l _ 2)$.

Check for Imput 2 (Memo)

F - NAND Tree

Others