WaterColor2037's blog

By WaterColor2037, history, 5 months ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it
  • +45
  • Vote: I do not like it

By WaterColor2037, history, 5 months ago, In English,

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) {
		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.

Read more »

 
 
 
 
  • Vote: I like it
  • +101
  • Vote: I do not like it

By WaterColor2037, history, 6 months ago, In English,

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:

  1. Adding event $$$(t, 1, x)$$$ — Add x into the set.
  2. 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:

  1. Adding event $$$(S_i-X_i, 1, X_i)$$$
  2. 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.

Read more »

 
 
 
 
  • Vote: I like it
  • +150
  • Vote: I do not like it