AtCoder Beginner Contest 173
Updated:
Source codes
Solutions
A - Payment
If you pay by $10,000$-yen bill, the shopper gives back the change by coins and 1,000 yen bills. Flush that sum of value of the coins, i.e., $(10000 - n) \% 1000$.
B - Judge Status Summary
It is better to use map<string, ll> m;.
C - H and V
Apply bit-wise brute-force method.
D - Chat in a Circle
Assume $0$-indexed. We pick $a _ 0, a _ 1, \dots$ and insert in the rounded table.
Observation
First, we prepare lemmas to assert that $\{ a _ i \}$ is in descending order.
Lemma D.1: Assume that $\{ a _ i \}$ has two adjacent terms $a _ i$ and $a _ {i + 1}$ with $a _ i < a _ {i + 1}$. Fix the inserting points. Let $X$ be the score of it and $Y$ be the score of the sequence where we swap the value with the place of $a _ {i}$ and $a _ {i + 1}$. Then, it follows that $X \leq Y$.
Proof: If the $i$-th element does not effect the $(i + 1)$-th element, it follows that $X = Y$. If it does, it means the $i$-th element is adjacent to the $(i + 1)$-th element. Since $a _ {i + 1} > a _ {i}$, its comfort point of the swapped version is greater than or equal to that of the original one. Therefore, we have $X \leq Y$.
Lemma D.2: Assume that $\{ a _ i \}$ attains the maximum score. We can assume that $\{ a _ i \}$ is sorted in descending order.
Proof: We keep applying Lemma D.1 to the extent that $\{ a _ i \}$ in descending order.
Next, we apply greedy method. For this purpose, we resolve duplicated numbers.
Definition D.3: For $a _ i$s, we define $(a _ i, i) > (a _ j, j)$ if and only if $a _ i > a _ j$ or ($a _ i = a _ j$ and $i < j$). Hereinafter, we just use $a _ i$ to denote $(a _ i, i)$. The inequality $<$ is defined in the same way.
Hereinafter, whenever we compare $a _ i$s, we use this $<$. Note that for any two elements $a _ i$ and $a _ j$ with $i \neq j$, there is no possibility of $a _ i = a _ j$. Hence, $\{ a _ i \}$ is strictly decreasing. In addition, even if we replace $\min$ generated by this $<$ in the definition of the comfort point, we see that the result is the same.
Definition D.4: An element $a _ i$ is touched if, after it is inserted, it is adopted for the comfort point of other elements.
Note that this is well-defined since we have replaced the definition of $<$ for $\{ a _ i \}$ in Definition D.3.
Lemma D.5: Assume that $\{ a _ i \}$ is in descending order.
- The first element $a _ 0$ is touched just once.
- For $i = 1, \dots, n - 1$, The $i$-th element $a _ i$ is touched at most twice.
Proof: For 1., since $a _ 0$ is the largest element of $\{ a _ i \}$, it is touched only by $a _ 1$ and never after that. For 2., fix $i = 1, \dots, n - 1$. Suppose that $a _ i$ has been touched by $a _ j$. We see that $i < j$ and $a _ i \geq a _ j$, and thus $a _ i > a _ j$. Therefore, if we insert any element between $a _ i$ and $a _ j$, $a _ i$ is never touched by it and, letting its element be $a _ k$, we have $a _ i > a _ k$ and $a _ k$ has replaced $a _ j$ as $a _ i$’s new adjacent. Hence, $a _ i$ can be touched by just twice; from its left hand side or its right hand side.
By Lemma D.2 and Lemma D.5, the upper bound of the score is the first $(n - 1)$ elements of the queue $\{ a _ 0, a _ 1, a _ 1, a _ 2, a _ 2, \dots \}$, where $\{ a _ i \}$ is sorted in descending order.
Lemma D.6: The upper bound above is attained.
Proof: Let $v$ be the queue above. When we insert $a _ i$ and $a _ {i + 1}$ with $i = 1, 3, 5, \dots$, we just put $a _ i$ in the left hand side of $b = v[i - 1] = v[i]$ and $a _ {i + 1}$ in the other side. Before this moment, $b$ is surrounded by the elements greater than $b$. Therefore, their comfort points is both $b$. This completes the proof.
Solution
We sort $\{ a _ i \}$ in descending order. We sum up the first $(n - 1)$ elements of $\{ a _ 0, a _ 1, a _ 1, a _ 2, a _ 2, \dots \}$ and flush its sum.
E - Multiplication 4
Assume $0$-indexed. If $n = k$, the answer is deterministic. Hereinafter, we assume $n > k$.
Observation
Lemma E.1: The answer is negative if and only if $k \% 2 = 1$ and all the value of $a _ i$ are positive.
Proof: Suppose that there exists a nonnegative $b$ in the multiset $\{ a _ i \}$. We choose arbitrary $k$ elements from $\{ a _ i \} \setminus \{ b \}$. If the product of them is negative, there is at least a negative element. We eliminate it and we multiply $b$ instead of it to gain a nonnegative product. Then, suppose that all of $\{ a _ i \}$ are negative. In this case, the condition that the answer is negative is that $k \% 2 = 1$.
Hereinafter, we assume that $\{ a _ i \}$ is sorted in descending order.
Lemma E.2: If the answer is nonnegative, the answer is the product of the first $k$ terms of $\{ a _ i \}$.
Proof: By Lemma E.1, $\{ a _ i \}$ consists of nonnegatives, from which the conclusion follows.
Implementation
Hereinafter, we assume that the answer is nonnegative. We use two pointers $l = 0$ and $r = n - 1$.
If $k \% 2 = 1$, we use $a[l {+ +}]$, regardless of its value being positive or not.
We compare $a[l]a[l + 1]$ and $a[r]a[r - 1]$. We choose the greater one and multiply the result with it and proceed the pointer we have used by two. We do this manipulation for $k / 2$ times. This cannot run in out-of-range.
We prove that this manipulation is valid.
Lemma E.3: There is no possibility that the result is negative.
Proof: Assume to the contrary that the answer is negative. Then, there exists $l \leq r$ so that $a[l]a[l + 1]$ and $a[r]a[r - 1]$ are negative. Since $\{ a _ i \}$ is in descending order, it follows that $\{ a _ i \}$ has no zeros and $a[l] = a[r - 1] > 0$ and $a[l + 1] = a[r] < 0$ and picks their product, which contradicts the assumption that $n > k$. We complete the proof.
Lemma E.4: If the result is zero, the answer is zero.
Proof: There exists $l \leq r$ so that $a[l]a[l + 1]$ and $a[r]a[r - 1]$ are non-positive and we have picked either of those pairs. If either of them were negative, it would follow that there is no zeros. Therefore, we see $a[l]a[l + 1] = a[r]a[r - 1] = 0$. Since $\{ a _ i \}$ is in descending order, it follows that $a[l + 1] = a[r] = 0$. From the fact that we have picked either of those pairs, it follows that there are at most $k - 1$ nonzero elements in \{ a _ i \}. Therefore, the answer is $0$.
Lemma E.5: If the result is positive, the answer is its result.
Let $X$ be the set of the elements we have chosen. Let $Y$ be a set of the elements that attains the maximum. Let $h _ X, h _ Y$ be the product of $X, Y$, respectively. By definition, it follows that $0 < h _ X \leq h _ Y$. Suppose that $X \neq Y$. Then, $X$ and $Y$ do not contain any zeros. Let $p$ and $q$ be the number of positives and negatives of $Y$, respectively. Note that $q \% 2 = 0$. Let $Z = \{ a _ 0, \dots, a _ {p - 1} \} \cup \{ a _ {n - q}, \dots, a _ {n - 1} \}$ and $h _ Z$ be its product. Since the definition of $p$ and $q$ and the fact that $\{ a _ i \}$ is descending order, the former and the latter part of $Z$ are composed of positives and negatives, respectively and, considering the absolute value, It follows that $h _ Y \leq h _ Z$. Moreover, we consider the product of each pair of adjacent terms. Seeing the construction of $X$, it follows that $h _ Z \leq h _ X$. Hence, we conclude that $h _ X = h _ Y$.
References
E通らなかったけど
— みやこ (@MiKo_IZUMI) July 5, 2020
aソート
a0が負ならそのまま前からK個終わり
Kが奇ならa0とってスタート
以下Kが0になるまでaの頭2個の積と尻2個の積を比べて大きい方を取る
でやばいパターンが見つからん
この実装に加えて答えが0未満になったときは前からk個とる、でいけた
— かいとccs (@tran0826) July 6, 2020
場合分け一つだけで済むし、めちゃくちゃ軽くてビックリしてる(嘘だったらごめんhttps://t.co/o6hmJDRaJp
F - Intervals on Tree
Assume $0$-indexed.
Solution
Let $c(G)$ be the number of the connected components of the forest $G$. Let $e(G)$ the number of the edges of $G$ and let $v(e)$ be that of the vertexes of $G$. Then, it follows that \[ c(G) = v(G) - e(e). \] Let $G$ be the original graph. Let $G(L, R)$ be the forest where its vertexes consist of $[L, R]$ and its edges consists of the edges whose endpoints both belongs to $[L, R]$. Then, what we are required to calculate is \[ \sum _ {0 \leq L \leq R < N} c(G(L, R)) = \sum _ {0 \leq L \leq R < N} v(G(L, R)) - \sum _ {0 \leq L \leq R < N} e(G(L, R)). \tag{F.1} \]
First, we calculate the first term of (F.1). It follows that
\[
\begin{align}
N _ v = \sum _ {0 \leq L \leq R < N} v(G(L, R)) &= \sum _ {0 \leq L \leq R < N} \sum _ {i = 0} ^ {N - 1} \delta _ {L \leq i \leq R} \\
&= \sum _ {i = 0} ^ {N - 1} \sum _ {0 \leq L \leq R < N} \delta _ {L \leq i \leq R} \\
&= \sum _ {i = 0} ^ {N - 1} (i + 1)(N - i).
\end{align}
\]
This is calculated in $O(n)$. We don’t have to determine its closed form.
Next, we calculate the second term of (F.1). We write $e _ i = (u _ i, v _ i)$ being the $i$-th edges. Without loss of generality, we can assume that $u _ i < v _ i$. Then, using the same idea, it follows that
\[
\begin{align}
N _ e = \sum _ {0 \leq L \leq R < N} e(G(L, R)) &= \sum _ {i = 0} ^ {N - 2} \sum _ {0 \leq L \leq R < N} \delta _ {L \leq u _ i} \delta _ {v _ i \leq R} \\
&= \sum _ {i = 0} ^ {N - 2} (u _ i + 1)(n - v _ i).
\end{align}
\]
This is also done in $O(n)$-time. The answer is $N _ v - N _ e$.