Hello Codeforces! Did you enjoy the AtCoder Beginner Contest 130? As usual, there was only Japanese editorial published, so I translated it into English. Um, actually it's already three days after the contest, it might be a bit late, but well, whatever?
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 third 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: Rounding
You can implement it straightforward: print $$$0$$$ if $$$X < A$$$, and print $$$10$$$ if $$$x >= A$$$.
An example code is shown in List 1:
Listing 1. Example Code of Rounding
#include <bits/stdc++.h>
using namespace std;
int main() {
int X, A; cin >> X >> A;
puts(X < A ? "0" : "10");
return 0;
}
B: Bounding
You can calculate all $$$D_1, D_2, \cdots, D _ {N+1}$$$ according to the recurrence formula, and judge if each element is less than or equal to $$$X$$$. The time complexity and the space complexity is $$$\mathcal{O}(N)$$$.
An example code is shown in List 2:
Listing 2. Example Code of Bounding
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, X; cin >> N >> X;
vector<int> D(N + 1);
D[0] = 0;
for (int i = 0; i < N; ++i) {
int x; cin >> x;
D[i + 1] = D[i] + x;
}
int ans = 0;
for (int i = 0; i <= N; ++i) {
if (D[i] <= X) {
ans++;
}
}
cout << ans << endl;
return 0;
}
C: Rectangle Cutting
When you cut the rectangle into two parts by a straight line passing through both given point $$$(x, y)$$$ and the center of the rectangle, the area of the part whose area is not larger than that of the other is half exactly half the are of the entire rectangle, and this is maximum. On the other hand, when line does not pass through the center, the area of the part which contains the center is larger.
Taking it into consideration, the way of cutting that satisfies the problems'condition can be uniformly determined if the given point is not the center of the rectangle. Otherwise, the areas of the two parts are equal regardless of the line, so you can get the answer by the following code:
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{
int a, b, x, y;
scanf("%d%d%d%d", &a, &b, &x, &y);
printf("%lf %d\n", double(a)*double(b) / 2, x + x == a&&y + y == b);
}
D: Enough Arrays(writer : yuma000)
If you iterate through all the possible left end and right end and check if each partial sum is greater than or equal to $$$K$$$, it takes $$$O(N^2)$$$ (you can calculate the partial sum in $$$O(1)$$$ using cumulative sums). So you have to look for more efficient way.
Let $$$S(l, r) = \sum_r^l A_k$$$, then it holds that
- $$$S(a, b) < S(a, b+1)$$$
- $$$S(a, b) > S(a+1, b)$$$.
Consequently, the following fact holds:
- If $$$S(l, r) >= K$$$ for some $$$l, r$$$, then for all $$$x (x <= r)$$$, $$$S(l, x)>=K$$$.
This means that if you fix a left end $$$l$$$ of some subsequence, if you could find the minimum possible $$$r$$$ where $$$S(l, r) >= K$$$, you can calculate the number of the subsequence whose left end is $$$l$$$. (Concretely, it's $$$N-r+1$$$.)
Specifically, you can find $$$r$$$ by using
- "two pointers" technique (O(N)), or
- binary search (O(NlogN)),
so you can implement it in either way. (Personally speaking, two-pointers is preferable because it's faster and easy to implement)
The following is the code of two pointers:
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;long long int K;
cin>>N>>K;
vector<long long int>A(N);
for(int i=0;i<N;++i){
cin>>A[i];
}
long long int answer=0;
long long int sum=0;
int r=0;
for(int l=0;l<N;++l){
while(sum<K){
if(r==N)break;
else{
sum+=A[r];
r++;
}
}
if(sum<K)break;
answer+=N-r+1;
sum-=A[l];
}
cout<<answer<<endl;
return 0;
}
E: Common Subsequence
In this problem you have to count the number of index sets $$$1 \leq i_1 < i_2 < \cdots < i_k \leq N$$$ and $$$1 \leq j_1 < j_2 < \cdots < j_k \leq M$$$ so that $$$S_{i_1} = T_{j_1}, \cdots, S_{i_k}=T_{j_k}$$$. First, one possible naive dp is that $$$dp\mathrm{[i][j]}$$$ : the number of ways of choosing alphabets from the first $$$i$$$ alphabets of $$$S$$$ and from the first $$$j$$$ alphabets of $$$T$$$ while $$$i$$$-th letter of $$$S$$$ and the $$$j$$$-th letter of $$$T$$$ is paired. Then $$$dp\mathrm{[i][j]} = (\sum_{k=1}^{i-1} \sum_{l=1}^{j-1} dp\mathrm{[k][l]}) + 1$$$ if $$$S_i = T_j$$$ and otherwise $$$0$$$, but the time complexity is $$$\mathcal{O}(N^2 \ast M^2)$$$. In fact, you can calculate the double sum by means of two-dimensional cumulative sum, so that the time complexity will be $$$O(NM)$$$. Specifically, let $$$sum\mathrm{[i][j]} = \sum_{k=1}^{i} \sum_{l=1}^{j} dp\mathrm{[k][l]}$$$, then $$$sum\mathrm{[i][j]} = sum\mathrm{[i-1][j]} + sum\mathrm{[i][j-1]} - sum\mathrm{[i-1][j-1]} + dp\mathrm{[i][j]}$$$ holds.
F: Minimum Bounding Box
Henceforward $$$(x_{max} - x_{min}) \times (y_{max} - y_{min})$$$ will be referred to as "bounding box".
After each point starts moving, $$$x _ {max}$$$ decreases, then stays constant, and then increases (some of which may be skipped). You can find the boundary of the differential by binary search, making use of its monotony. The similar property holds in $$$x_{min}$$$, $$$y_{max}$$$ and $$$y _ {min}$$$.
Therefore, you can split the timeline of point's movement into segments so that the differentials of each maximum and minimum value is constant within each segment. And in fact, the bounding box can be minimum only at some boundary time of these segments.
Here is a proof.
Let $$$dx = x_{max} - x_{min}, dy = y_{max} - y_{min}$$$. In a segment where $$$dx$$$ and $$$dy$$$ are weakly increasing monotonously, the bounding box also increases. Within such segment, the bounding box is minimum at the beginning point of the segment. Similarly, in a segment where $$$dx$$$ and $$$dy$$$ are weakly decreasing monotonously, the bounding box is minimum at the last point of the segment.
Next, let's consider a segment where $$$dx$$$ is strictly increasing while $$$dy$$$ is strictly decreasing monotonously (the reverse is also true). Here, the differential of bounding box depends on the proportion of $$$dx$$$ and $$$dy$$$. While $$$dx$$$ is less enough than $$$dy$$$, the bounding box increases. After $$$dx$$$ increases to some extent (or possibly, from the beginning), the decreasing effect becomes dominant and the bounding box starts to decrease. After all, within such segment the bounding box is always convex upward, and it's minimum at the either end point.
Hence the statement has been proved.
