AtCoder Grand Contest 039


AtCoder Grand Contest 039

Source codes


A - Connection and Disconnection

Basic Strategy

Suppose we have a function $f(S)$ that flushes the correct answer. Then, we can basically see that the answer is described as the following form: $f(KS) = A(K - 1) + B$, where $A, B$ is a constant.

This is seen through the construction of $f$. We write $N = \lvert S \rvert$. For $i = 1, \dots, N - 1$, if $S[i - 1] = S[i]$, we change $S[i]$ for some character that must be different from $S[i + 1]$, such as #. This greedy method works well if there exists $j$ so that $S[j - 1] \neq S[j]$. We divide $S$ into $T + U$ and we have \[ f(KS) = f(T) + f((K - 1) (U + T) ) + f(U) = f(T) + f(U) + (K - 1) f(U + T). \] So we set $B = f(T) + f(U) = f(S)$ and $A = f(U + T)$.

To write the code, it is easy for us to compute $B = f(S)$ and $A + B = f(2S)$.

Corner Cases

If the string is composed only by one character, the strategy above doesn’t work. We can see this problem by the single character S = "a". We have $f(a) = 0$, $f(aa) = 1$, $f(aaa) = 1$, $f(aaaa) = 2$, $f(aaaaa) = 2$, and so on.

In this case the answer is $NK/2$.

B - Graph Partition

When can we construct the solution?

First, let us show the following lemma.

Lemma B.1: We can construct the solution if and only if the graph is a bipartite graph.

Proof. Suppose we have constructed the solution $\{ V _ i \}$. We color each $e \in V _ i$ red if $i$ is odd and blue if $i$ is even. Then, the constraints confirm that each edge must connect a red vertex and a blue vertex. That means the graph is bipartite. Suppose the graph is a bipartite graph. Then, we can easily construct $V _ 0$ which contains all red vertexes and $V _ 1$ which contains all blue vertexes.

So we have to decide if the graph is a bipartite graph or not. If not, the answer is -1.

The answer

We show the next lemma.

Lemma B.2: Suppose the graph is a bipartite graph. Then, the answer is the diameter $+1$.

Proof. Let $D$ be the diameter. By Lemma B.1, we can construct $\{ V _ i \}$. Assume to the contrary that the answer is greater than $D + 1$. Then, we can take a path whose length is greater than or equal to the answer by the graph’s connectedness. This contradicts the definition of the diameter. Thus the answer must be less than or equal to $D + 1$. In addition, We can construct $V _ 0, \dots, V _ D$ as follows. We take a pass $v _ 0, \dots, v _ D$ that attain the diameter. We set $V _ i$ as follows.

$V _ i = $ the set of the vertexes whose distance with $v _ 0$ is $i$.

Obviously, $v _ i \in V _ i$, especially $v _ D \in V _ D$. For any edge $e = (u, v)$, the difference of the distance between $u$ and $v _ 0$ and the distance between $v$ and $v _ 0$ is less than or equal to $1$. If it were $0$, it would break the bipartite property. Thus the difference is $1$, which satisfies the constraints.

How to compute the diameter

It is well-known that how to compute the diameter of a tree. We just do DFS twice and the time complexity is $O(N)$. But this problem, the graph is not necessarily a tree. We can compute, however, its diameter by definition: \[ D = \max _ {u, v} d(u, v). \] We use the Warshall-Floyd algorithm to calculate $d(u, v)$ for all $u$ and $v$ in $O(N^3)$-time.

C - Division by Two with Something

D - Incenters


日本語 English
内心 incenter
重心 centroid
外心 circumcenter
垂心 orthocenter
傍心 excenter


Let $O = (0, 0)$ be the central point of the unit circle $K$. On $K$, we take three different points $A, B, C$. Let $I$ be the incenter of $\triangle ABC$. Let $A’$ be the central point of the arc $BC$ without $A$. We define $B’, C’$ as the similar way. Then, we see that $I$ is the orthocenter of $\triangle A’B’C’$. Note that $O$ is the circumcenter of $\triangle A’B’C’$, too. Let $G$ be the centroid of $\triangle A’B’C’$. Here, we use the Euler line, i.e. $3\vec{OG} = \vec{OI}$. Therefore, we conclude that \[ \vec{OI} = 3\vec{OG} = \vec{OA’} + \vec{OB’} + \vec{OC’}. \tag{C.1} \]

We fix $B$ and $C$. Then $A’$ is also fixed, provided that the relative positions of $A, B, C$ are the same. We count how many points are on the two arcs $BC$ respectively and add them up to $A’$. This solution works in $O(N^2)$-time.

E - Pairing Points

F - Min Product Sum