Hello Codeforces! Did you enjoy the AtCoder Beginner Contest 129? As usual, there was only Japanese editorial published, so I translated it into English again.
Disclaimer. Note that this is an unofficial editorial and AtCoder has no responsibility for this. Also, I didn't do proofreading at all, so it might contain many typos. Moreover, this is the second experience I write such kind of editorial, so the English may not be clear, may be confusing, or even contain mistakes. Any minor corrections (including grammatical one) or improvement suggestions are welcome. Please do not hesitate posting a comment about it.
A: Airplane
There are 6 orders to visit the airports, so you can try all of them and look for the minimum value. However, if you realized that each cost of a route is equal to the sum of two integers out of the given three, you could also obtain an answer by subtracting the maximum of the three from the sum of all three integers.
An example code is shown in List 1:
Listing 1. Example Code
#include <bits/stdc++.h>
using namespace std;
int main() {
int P, Q, R;
cin >> P >> Q >> R;
cout << P + Q + R - max({P, Q, R}) << endl;
return 0;
}
B: Balance
Let's try all $$$1 \leq T < N$$$. Then you can get the minimum value by calculating the sum of each group. If you implemented it naively, the time complexity will be $$$\mathcal{O}(N^2)$$$, so it will got accepted. However, the difference between the sum of two groups is equal to that between the sum from the beginning to the specific place and the total sum subtracted by the sum, so if you traverse from the beginning to the end while retaining the calculated sum, you can solve the problem in $$$\mathcal{O}(N)$$$.
An example code is shown in List 1:
Listing 1. B Example Code
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> a(N);
int sum = 0;
for (int i = 0; i < N; ++i) {
cin >> a[i];
sum += a[i];
}
int mini = sum;
int prefix_sum = 0;
for (int i = 0; i < N; ++i) {
cin >> a[i];
prefix_sum += a[i];
mini = min(mini, abs(prefix_sum - (sum - prefix_sum)));
}
cout << mini << endl;
return 0;
}
C: Typical Stairs
Let's first think about the case without any broken steps. Let $$$f_x$$$ be the number of the ways to climb up to the $$$x$$$-th step.
For each $$$x \geq 2$$$, suppose that you have climbed up to the $$$x$$$-th step. Then there are the following two possibilities:
- you have set foot on the $$$x-2$$$-th step right before that, or
- you have set foot on the $$$x-1$$$-th step right before that.
This means that $$$f_x = f_{x-1} + f_{x-2}$$$. This formula is equal to that of the fibonacci numbers. By using DP (Dynamic Programming), you can solve it in $$$O(N)$$$.
If you came up with this idea, you could also solve the problem with some broken steps by adapting this method. Specifically, you could modify the recurrence relation so that you would never go to $$$f_{a_i}$$$.
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
int main(){
int N,M;
cin>>N>>M;
vector<int>oks(N+1,true);
for(int i=0;i<M;++i){
int a;cin>>a;
oks[a]=false;
}
vector<long long int>dp(N+1);
dp[0]=1;
for(int now=0;now<N;++now){
for(int next=now+1;next<=min(N,now+2);++next){
if(oks[next]){
dp[next]+=dp[now];
dp[next]%=mod;
}
}
}
cout<<dp[N]<<endl;
return 0;
}
D: Lamp
If you try to count the lighted squares for each square not occupied by an obstacle using for-loop, the worst time complexity would be $$$O(HW(H+W))$$$ when there are no obstacles, so you cannot solve this within the time limit.
However, if you make use of some supplemental precalculations to count the lighted square, you can count the lighted squares for each square the lamp is placed in constant time, thus obtaining the answer in $$$O(HW)$$$.
Let $$$(i, j)$$$ denote the square at the $$$i$$$-th row from the top and the $$$j$$$-th column from the left. You will need the following four precalculations:
- $$$L[i][j]$$$: The number of the lighted cells in the left of square $$$(i, j)$$$ when the light is placed there (including the square $$$(i, j)$$$ itself)
- $$$R[i][j]$$$: The number of the lighted cells in the right of square $$$(i, j)$$$ when the light is placed there (including the square $$$(i, j)$$$ itself)
- $$$D[i][j]$$$: The number of the lighted cells above square $$$(i, j)$$$ when the light is placed there (including the square $$$(i, j)$$$ itself)
- $$$U[i][j]$$$: The number of the lighted cells below square $$$(i, j)$$$ when the light is placed there (including the square $$$(i, j)$$$ itself)
For example, $$$L[i][j]$$$ can be calculated as follows.
- If there are an obstacles in $$$(i, j)$$$, $$$L[i][j]=0$$$.
- Otherwise, if $$$j=1$$$, $$$L[i][j]=1$$$.
- Otherwise, if $$$j>1$$$, $$$L[i][j]=L[i][j-1]+1$$$.
After calculating them for each directions, the number of the lighted square when you put the lamp at square $$$(i, j)$$$ is equal to $$$L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3$$$. (These four values all include the square $$$(i, j)$$$ itself, so to remove the duplicates, you have to subtract by 3.)
E: Sum Equals Xor
Generally, $$$A+B$$$ is equal to or greater than $$$A \mathrm{XOR} B$$$. These two values are equal if there doesn't exist a digit where both $$$A$$$ and $$$B$$$ is 1 in binary notation. Conversely, if there exists such a digit, $$$A+B$$$ cause a carry at the digit while XOR doesn't, so $$$A+B$$$ will be strictly greater (and you cannot cancel the difference).
Using this fact, let's define a digit-DP as follows:
- $$$\mathrm{dp1}[k] := $$$ The number of pair $$$(A, B)$$$ where you have already determined the first $$$k$$$ digits of $$$A$$$ and $$$B$$$, and where you already know that $$$A+B$$$ is equal or less than $$$L$$$
- $$$\mathrm{dp2}[k] := $$$ The number of pair $$$(A, B)$$$ where you have already determined the first $$$k$$$ digits of $$$A$$$ and $$$B$$$, and where you still don't know whether $$$A+B$$$ is equal or less than $$$L$$$
In order to calculate $$$\mathrm{dp*}[k]$$$ from $$$\mathrm{dp*}[k-1]$$$, you have to think of two transition whether the $$$k$$$-th digit would be 0 or 1. If the $$$k$$$-th digit is 0, the $$$k$$$-th digit of both $$$A$$$ and $$$B$$$ should be 0. If the $$$k$$$-th digit is 1, there are two transition: $$$(0, 1)$$$ and $$$(1, 0)$$$. In this case, you have to calculate dp2 carefully so that $$$A+B$$$ would not exceed $$$L$$$ after deciding the $$$k$$$-th digit.
In this way, regarding $$$L$$$ as a string, this problem could be solved in $$$O(|L|)$$$.
F: Takahashi's Basics in Education and Learning
Let's rephrase the problem statement to as follows:
- Consider a string $$$X$$$ and an integer $$$s$$$. First, $$$X = "0", s=A$$$.
- In one operation, concat $$$s$$$ to the bottom of $$$X$$$ and increase $$$s$$$ by $$$B$$$.
- Find the value of $$$X \mod M$$$ after making $$$N$$$ operations.
Let the number of $$$d$$$-digit terms be $$$C_d$$$, then you can easily calculate them by subtracting the number of terms equal or less than $$$\underbrace{99\ldots9}_{d-1}$$$ from the number of terms equal or less than $$$\underbrace{99\ldots9}_{d}$$$. The operations of concatting $$$d$$$-digit terms for $$$C_d$$$ times is equivalent to repeating the operation of $$$(X, s) \mapsto (X \times 10^d + s, s+B)$$$ for $$$C_d$$$ times. This operation can be represent as the following matrix:
\begin{equation} (X, s, 1) \begin{pmatrix} 10^d & 0 & 0 \ 1 & 1 & 0 \ 0 & B & 1 \end{pmatrix} = (X \times 10^d + s, s + B, 1) \end{equation} (Note: the 3x3 matrix is broken. Does anybody know how to fix it?)
Therefore, all you have to do is calculating $$$C_d$$$-th power of this $$$3 \times 3$$$ matrix, and this could be achieved in $$$O(\log C_d)$$$ by means of Fast Matrix Exponentiation.
You can obtain the ultimate $$$X \mod M$$$ fast enough by operating the calculation above for $$$d = 1, 2, \ldots, 18$$$ in this order. Be very careful of overflow.
