AtCoder Beginner Contest 140
Updated:
- Review: 2020-06-03
Source codes
Solutions
A - Password
Just flush $N ^ 3$.
B - Buffet
First, we accumulate $\sum _ i B _ i$. Then, for each $i$, if $A _ {i} + 1 = A _ {i + 1}$, we add $C _ {A _ i}$ to the final results.
C - Maximal Value
Assume $0$-indexed. The minimum number of $A _ i$ for $i \in N$ is $\min(B _ {i - 1}, B _ i)$, where we define $B _ {-1} = B _ N = \infty$. We compute each $A _ i$ and sum up to obtain the answer.
D - Face Produces Unhappiness
Solution
First, let’s consider the operation deeply. In this operation, there is no meaning if we break the subsequence the people in which are in same direction. So we can do run-length compression. In other words, if we see, for example, $LLLLL$, we replace this with the single $L$ and gain $4$ points immediately. Therefore, we don’t have to keep the information of the length. We use $X$ to denote this “initial” points.
Thus the string becomes such as $LRLRLR…$. We do the operations to maximize the final points. We see that, even if we restrict the range of the operation to just one character, we have the same result.
Then, how much do we gain by each operations? The answer is $2$ for almost any cases. But take a look into this carefully in the small cases.
- $L$: We cannot do the operation and gain any points.
- $LR$: We can do the operation once and gain $1$ point.
- $LRL$: We can do the operation once and gain $2$ point.
- $LRLR$: We can do the operation twice and gain $2$ and $1$ point(s).
- $LRLRL$: We can do the operation twice and gain $2$ points for each operation.
Here we conclude that the final result is expressed as follows. \[ \min(N - 1, X + 2K). \]
E - Second Sum
Observation
Assume $0$-indexed. For each $0 \leq n < N$, when will $n$ be the second largest in the range $[r, l]$? We see that $n$ is the second largest in $[r, l]$ if and only if the following conditions hold.
- $a _ i = n$ is contained in $[r, l]$, i.e., $i \in [r, l]$.
- As many as one element larger than $n$ is contained in $[r, l]$, i.e., there exists exactly one element $r \leq j \leq l$ so that $a _ j > n$.
Solution
For each $a _ i$ with $i \in N$, we count how many ranges hold the conditions above. We use $X _ i$ to denote the count. Thus the final result is as follows. \[ \sum _ {i \in N} a _ i X _ i. \] How should we calculate each $X _ i$ in short time? The idea is as follows. We use $\circ$ to denote a number less than $a _ i$ and $\times$ to denote a number greater than $a _ i$. We look around $a _ i$. There should be as follows. Here, we exclude some exceptions. We discuss those later. \[ \dots \circ, \circ, \times, \circ, \circ, \circ, \circ, \times _ l, \circ, \circ, \circ, a _ i, \circ, \circ, \circ, \circ, \circ, \circ, \times _ r, \circ, \times, \circ, \dots \] In this case, we choose $l$ and $r$ so that the conditions above follows. How many choices are there? There is two patterns.
- $[l, r]$ contains $\times _ l$: In this case, we have to choose $l$ from $\circ, \circ, \circ, \circ, \times _ l$ and $r$ from $a _ i, \circ, \circ, \circ, \circ, \circ, \circ$. There are $5 \times 7 = 35$ ranges.
- $[l, r]$ contains $\times _ r$: In this case, we have to choose $l$ from $\circ, \circ, \circ, a _ i$ and $r$ from $\times _ r, \circ$. There are $4 \times 2 = 8$ ranges.
We can make this argument generalized: the sum is $l _ 1 r _ 0 + l _ 0 r _ 1$.
Exceptions
We have to check exceptional patterns. The left side and the right side are similar. We write the left side.
- If we have no $\times$ to the left of $a _ i$: the first pattern cannot be occurred. $l _ 1 = 0$ and $l _ 0 = i$.
- If we have only one $\times$ to the left of $a _ i$: the first pattern will be consecutive up to $0$. Therefore, we compute $l _ 1$ by a different way.
We can compute $l _ 0$, $l _ 1$, $r _ 0$ and $r _ 1$ by using set in $O(\log N)$-time. So the entire time complexity is $O(N \log N)$.
Implementation on YouTube Live
We focus on how to use set effectively.
LandRis initialized by $\{ -1, -1 \}$ and $\{ N, N \}$, respectively. This is because we overcome the difficulties from the exceptional patterns discussed above.- In this code, we insert each index $i$ into set $S$ and then find $i$ from $S$. This code works well.
set<ll> S;
for (auto x = N - 1; x >= 0; x--)
{
ll i{ind[x]};
S.insert(i);
vector<ll> L(2, -1), R(2, N);
auto it{S.find(i)};
for (auto j = 0; j < 2; j++)
{
if (it == S.begin())
{
break;
}
--it;
L[j] = *it;
}
it = S.find(i);
for (auto j = 0; j < 2; j++)
{
++it;
if (it == S.end())
{
break;
}
R[j] = *it;
}
vector<ll> ls{i - L[0], L[0] - L[1]};
vector<ll> rs{R[0] - i, R[1] - R[0]};
ll c{ls[0] * rs[1] + ls[1] * rs[0]};
ans += c * (x + 1);
}
Other implementation using multiset
To avoid the out-of-range problem, we can use sentinels and multiset<int> S;. In this problem, we insert two $-1$ and two $N$ into $S$.
multiset<ll> S;
S.insert(-1);
S.insert(-1);
S.insert(N);
S.insert(N);
ll ans{0};
for (auto x = N - 1; x >= 0; --x)
{
ll ind{to_ind[x]};
S.insert(ind);
auto it{S.find(ind)};
--it;
auto l0{*it};
--it;
auto l1{*it};
it = S.find(ind);
++it;
auto r0{*it};
++it;
auto r1{*it};
ans += (x + 1) * ((l0 - l1) * (r0 - ind) + (r1 - r0) * (ind - l0));
}
F - Many Slimes
Solution
We say a slime is in $k$-th generation if it is produced at the time $T = k$. The initial slime is $0$-th generation.
We can solve this problem the following greedy algorithm.
First, we set the biggest slime as the initial slime. We hold produced slimes in a vector $V$. We sort $V$ in descending order by each time. For each $T = 1, 2, \dots, N$, We make another $2 ^ {T - 1}$ slimes by $2 ^ {T - 1}$ slimes in $V$. We choose slimes whose number is as big as we can. If we can choose $2 ^ {N - 1}$ slimes, we continue to the next step. If not, the answer is "No". If we finish choosing $2 ^ N$ slimes, the answer is "Yes" of course.
This solution works in $O(N 2 ^ N \log 2 ^ N) = O(N ^ 2 2 ^ N)$-time.
How to write codes
The implementation is very simple.
for (auto i = 0LL; i < N; i++)
{
ll const T{1LL << i};
ll k{0};
for (auto j = 0; j < M; j++)
{
if (!B[j] && A[j] < S[k])
{
S.push_back(A[j]);
B[j] = true;
++k;
if (k == T)
{
break;
}
}
}
if (k < T)
{
No();
}
sort(S.rbegin(), S.rend());
}
Yes();
Question
Why do we need sort by each time $T = 1, \dots, N$? There is a example:
10
-> 10, 9
-> 10, 9, 9, 8
-> 10, 9, 9, 8, 9, 8, 8, 7
-> 10, 9, 9, 8, 9, 8, 8, 7, 9, 8, 8, 7, 8, 7, 7, 6
Reasoning
Let’s explain why the greedy algorithm above works well.
We use the pedigree table to denote the tree that connect the parent and its children.
First, we see that the answer is "No" if we cannot simulate by our algorithm. This is because, when the algorithm is interrupted, there must be so big a slime $X$ that we cannot make by slimes in $V$. If the answer were "Yes", we must have had the valid pedigree table that are not greedy. Suppose $X$ is in $k$-th generation in this table and interrupted in $l$-th. If $k = l$, it is a contradiction. If $k > l$, we don’t have to stop algorithm, which implies contradiction. If $k < l$, we can find a slime $Y$ in less-than-or-equal-to-$k$-th generation in this algorithm that can be swapped by $X$, which implies the number of $X$ is greater than $Y$. The greedy algorithm implies the number of $X$ is less than $Y$. This is a contradiction. This is what we want to show.
Second, we prove that, if the answer is "Yes", this greedy succeeds. Suppose we can construct a valid pedigree table that is not greedy, which means we passed the number $x$ to use $y$ with $y < x$. Suppose that $x$ is in $k$-th and $y$ is in $l$-th. We have $k \geq l$. If $k = l$, it means nothing. Assume $k > l$. Let $T _ x$ be the tree that contains all the grandchildren of $x$. Then, we have the tree $T _ y$ which contains the following slimes.
- $y$ itself.
- the slimes that was a grandchild of $y$ produced at the time $T \geq k$.
We can swap $T _ x$ and $T _ y$. The validness still follows after the swap. We do this finite times to get the greedy pedigree table.
Others
Review: 2020-06-04
A - sample: 2, tle: 2.000, time: 03:21, from_submit: 54:56
B - sample: 3, tle: 2.000, time: 03:26, from_submit: 51:30
C - sample: 3, tle: 2.000, time: 04:26, from_submit: 47:04
D - sample: 4, tle: 2.000, time: 09:23, from_submit: 37:41
E - sample: 3, tle: 2.000, time: 21:57, from_submit: 15:44
F - sample: 4, tle: 2.000, time: 15:44, from_submit: 00:00