Hello Codeforces! Did you enjoy the AtCoder Beginner Contest 128? A Japanese editorial is already out, but unfortunately there is no English editorial, so I translated it into English experimentally. Note that this is an unofficial one; AtCoder has no responsibility for this editorial. Also, I didn't do proofreading at all, so it might contain many typos. Moreover, this is the first 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: Apple Pie
For simplicity, you can cut all the apples into pieces in advance. As a result, you will have $$$3A+P$$$ pieces of apple. By using all these pieces as much as you can make apple pie, you will get maximum number of apple pies. The maximum number is $$$\displaystyle \frac{3A+P}{2}$$$ when $$$3A+P$$$ is even, and $$$\displaystyle \frac{3A+P-1}{2}$$$ when it is odd. The following is an example for C++ implementation:
# include <bits/stdc++.h>
using namespace std;
int main() {
int A , P;
cin >> A >> P ;
cout << (3 * A + P) / 2 << endl;
return 0;
}
B: Guidebook
In most programming languages, you can sort array of string in lexicographical order by means of sorting function standard library (e.g. std::sort in C++).
When reordering the restaurants in accordance with the problem statement, you can implement it easily if you use "pair" type in C++. Specifically, first prepare an array of pair<pair<string, int>,int> and put the parameters of restaurants. When putting information, put its city name into first.first (which would be the first key of sorting), its score multiplied by $$$-1$$$ into first.second (which would be the second), and its index into second (which would be the third).
After sorting this array of pairs, the second of $$$i$$$-th elements of the array would be the identification number of the restaurants that should be introduced $$$i$$$-th in the book.
If you are using a language without pair, you can solve this problem by repeating following operations $$$n$$$ times: among the restaurants that are not yet selected, look for the restaurants with the most early lexicographical order, and among them choose the restaurants with the highest score. In this case the time complexity would be $$$O(n^2)$$$, which is still enough.
The following is an example for C++ implementation (without includes etc):
char in[120];
pair<pair<string,int>,int> p[110];
int main(){
int a;scanf("%d",&a);
for(int i=0;i<a;i++){
int t;scanf("%s%d",in,&t);
string tmp=in;
p[i]=make_pair(make_pair(in,-t),i);
}
std::sort(p,p+a);
for(int i=0;i<a;i++)printf("%d\n",p[i].second+1);
}
C: Switches
First, if you ignore the conditions, there are $$$2^N$$$ combinations of on/off of switches. It is difficult to directly count the number of combinations, so let's think about one fixed combination. Then you can judge if the combination is valid by asserting that checking each bulb is lighted. The time complexity for this algorithm is $$$\mathcal{O}(MN * 2^N)$$$.
When looping through each combination of switches' states, you can use DFS or encode the state into $$$N$$$ bits of integer.
This time, the constrains were small enough that you could solve just iterating through all possibility, but this problem can be regarded as counting the number of solutions of a system of linear equations on mod $$$2$$$, so by using rank, you can solve this more fast.
Source Code: https://atcoder.jp/contests/abc128/submissions/5640467
D: equeue
You can perform operation C and D at very last. Then these two operations are both equivalent to "discarding a jewel."
Let's assume that you will perform $$$A$$$ times of Operation A and $$$B$$$ times of Operation B. Then $$$A+B \leq \min\lbrace N, K \rbrace$$$. Here, you will obtain the $$$A$$$ leftmost jewels and $$$B$$$ rightmost jewels. Discarding a jewel with negative values results in increasing the total score by its absolute value, so discarding at most $$$K-(A+B)$$$ jewels which has least values. However you don't have to discard the jewels with non-negative values.
By looping through all possible $$$A$$$ and $$$B$$$, the time complexity would be $$$O(R^3 log R)$$$ where $$$R=\min \lbrace N, K \rbrace$$$.
By the way, you can speed up this solution so that the complexity would be $$$O(R^2 log R)$$$. (Hint: you can use the fact that by changing $$$B$$$ by $$$1$$$, the number of jewel you have to discard changes by no more than $$$2$$$.)
E: Roadwork
All $$$Q$$$ people will start moving at integer time, so the block from time $$$S_i-0.5$$$ to time $$$S_i-0.5$$$ can be regarded as a block during a time interval $$$[S_i, T_i)$$$ (for simplicity).
The $$$i$$$-th roadwork blocks the point at coordinate $$$X_i$$$ during $$$[S_i, T_i)$$$. Then it holds that only those who start the coordinate $$$0$$$ during time $$$[S_i-X_i, T_i-X_i)$$$ could be affected by this roadwork (those who didn't start during that interval would never run into that road construction.)
If you try to judge for each $$$Q$$$ people if $$$N$$$ roadworks affect them, the time complexity would be $$$O(NQ)$$$ which would result in TLE. Here, you can use event sorting. Specifically, prepare "an array to store events" and "a set of coordinates which are currently blocked." Here we define the following two events:
- Adding event $$$(t, 1, x)$$$ — Add x into the set.
- Removing event $$$(t, -1, x)$$$ — Remove x from the set.
For each $$$N$$$ roadwork, add the following event that corresponds to the $$$i$$$-th roadwork:
- Adding event $$$(S_i-X_i, 1, X_i)$$$
- Removing event $$$(T_i-X_i, -1, X_i)$$$
into the array.
Sort the array in accordance of value $$$t$$$ of the event, which are to be processed one by one. After processing all the events with the value $$$t$$$ no more than $$$D_i$$$, you can find the answer for $$$i$$$-th person by looking at the minimum value in the set.
By this algorithm, you can sort the events in $$$O(N \log N)$$$, process the set in $$$O(\log N)$$$ for each event, and look for the minimum value in $$$O(\log N)$$$ for each $$$Q$$$ people, so you can solve this problem in $$$O((N+Q) \log N)$$$ overall.
F: Frog Jump
First, apparently you will get a higher score if you reach at coordinate $$$N-1$$$ (hereinafter called "Goal") without drowning than you drown, so you don't have to care about the route in which you will reach a coordinate less than $$$0$$$ or more than $$$N-1$$$. Therefore you can assume that $$$0<B<A<=N-1$$$.
If you try to loop through all possible $$$A$$$ and $$$B$$$, it would be $$$O(N^2 log N)$$$ which results in a TLE. There are so many ways of optimization, but here we will introduce the solution by using the constrain that "you should end up in reach the Goal."
You will reach the Goal after you made odd times of move. If you reached the Goal after moving $$$2k+1$$$ times (where $$$k$$$ is a non-negative integer) for some $$$A$$$ and $$$B$$$, the route will be like:
\begin{equation} 0, A, A-B, 2A-B, 2A-2B, 3A-2B, \cdots, kA-(k-1)B, kA-kB, (k+1)A-kB. \end{equation}
It's a bit confusing, so here let $$$C = A-B (>0)$$$. Then
\begin{equation} 0, A, C, A+C, 2*C, A+2C, \cdots, A+(k-1)C, kC, A+kC \end{equation}
$$$A+kC = N-1$$$ holds, so after deformation, you will get
\begin{equation} 0, (N-1)-kC, C, (N-1)-(k-1)C, 2C, (N-1)-(k-2)C, \cdots, N-1-C, kC, N-1 \end{equation}
If you fix some $$$k$$$ and $$$C$$$, the route would be uniquely decided. Let f(k, C) be the score for the route. Then it holds that
\begin{equation} f(k+1, C) = f(k, C) + S_{N-1-kC} + S_{kC} (k>=0), \end{equation}
so by using DP, you can calculate $$$f(k, C)$$$ for each $$$k$$$, $$$C$$$ in $$$O(1)$$$. Also, $$$kC < N-1$$$ should hold, so the number of pair of $$$k$$$, $$$C$$$ is $$$O(N log N)$$$. Therefore, this problem could be solved in $$$O(N log N)$$$. Note that you mustn't visit the same coordinate more than twice in order not to drown midway.
