WaterColor2037's blog

By WaterColor2037, history, 5 years 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.

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

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it +31 Vote: I do not like it

The whole codeforces community and most important, atcoder community should thank you for your priceless efforts. Its very hard to translate those editorials. Great thanks to you.

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Thanks for the editorial, great work!

But, if somebody wants to explain E again, that would be nice. I still have no idea how to "calculate dp2 carefully", or whats the basic idea of the transition.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    I totally agree with you. Actually, I didn't understand the editorial so much, but I persisted on translating it literally :)

    Anyway, after thinking "carefully" for five minutes, I understood what the editorial meant. First, "is equal or less than" in the dp definitions should, maybe, actually be "is less than." Then let's think about the transition. Let $$$s_i$$$ be the $$$i$$$-th letter of $$$L$$$ (1-indexed, counted from left to right).

    First, apparently, after you decided $$$0$$$ digits of $$$A$$$ and $$$B$$$, of course you don't know whether $$$A+B$$$ is less than $$$L$$$, so $$$\mathrm{dp1}[0]=0$$$ and $$$\mathrm{dp2}[0]=1$$$ holds. For each $$$1 \leq k \leq N$$$, let's determine the $$$k$$$-th digit of $$$A$$$ and $$$B$$$.

    If your are convinced that sum of predetermined $$$k-1$$$ digits is already less than $$$L$$$, you don't have to worry about anything and set the $$$k$$$-th digits to $$$(0, 0)$$$, $$$(0, 1)$$$ or $$$(1, 0)$$$. However, if you are not convinced yet, your action depends on $$$s_k$$$. If $$$s_k = 0$$$, you can only set the both digits to $$$(0, 0)$$$, otherwise $$$A+B$$$ would exceed $$$L$$$. If $$$s_k = 1$$$, you have two choices: set the digits to $$$(0, 0)$$$ to make sure that $$$A + B$$$ is strictly less than $$$L$$$, or set the digits to $$$(0, 1)$$$ or $$$(1, 0)$$$ with possibility that $$$A+B$$$ may exceed $$$L$$$ if you decided bad digits afterward.

    Therefore, the recurrence relation would be like this:

    $$$ \begin{cases} \begin{cases} \mathrm{dp}1[k] = 3 \cdot \mathrm{dp}1[k-1] \\ \mathrm{dp}2[k] = 1 \cdot \mathrm{dp}2[k-1] \end{cases} & (s_k = 0) \\ \begin{cases} \mathrm{dp}1[k] = 3 \cdot \mathrm{dp}1[k-1] + 1 \cdot \mathrm{dp}2[k-1] \\ \mathrm{dp}2[k] = 2 \cdot \mathrm{dp}2[k-1] \end{cases} & (s_k = 1) \end{cases} $$$

    The answer is $$$dp1[n] + dp2[n]$$$.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    I think the approach mentioned above might be a bit confusing. Let $$$L_k$$$ be the k-th bit (from the left) of L.

    • $$$L_k = 0$$$: you will have to pick $$$(0, 0)$$$ for $$$dp2$$$, which means $$$dp2[k + 1]$$$ += $$$dp2[k]$$$ and any combinations for $$$dp1$$$
    • $$$L_k = 1$$$: if you pick $$$(0, 1)$$$ or $$$(1, 0)$$$, we will still have the same transitions as the first case. However if you pick $$$(0, 0)$$$, we will need an additional $$$dp1[k + 1] $$$ += $$$dp2[k]$$$ because we already know $$$A + B < L$$$ from now on.
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      But what is the exact definition of dp1 and dp2

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        • $$$dp1[i]$$$ is the number of pairs $$$\{a, b\}$$$ of length $$$i$$$ $$$([1..i])$$$ that have sum $$$a + b < L $$$. (Of course the way we choose '0', '1' at each step guarantee $$$a + b = a\ xor\ b$$$.
        • $$$dp2[i]$$$ is the number of pairs $$$\{a, b\}$$$ of length $$$i$$$ $$$([1..i])$$$ that have sum $$$a + b = L$$$ up to now.

        So the transition will be:

        • if $$$L[i] = 0$$$:
        $$$\begin{cases}dp1[i] = 3dp1[i-1] \\dp2[i] = dp2[i-1] \end{cases}$$$
        • if $$$L[i] = 1$$$:
        $$$\begin{cases}dp1[i] = 3dp1[i-1] + dp2[i-1]\\dp2[i] = 2dp2[i-1] \end{cases}$$$

        Base case:
        + $$$dp1[0] = 0$$$
        + $$$dp2[0] = 1$$$
        And the answer is $$$dp1[n] + dp2[n]$$$.

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    My solution for E:

      string s;
      cin >> s;
      ll ans = 1, n = s.size(), nb = 0;
      for(ll i = 0; i < n; ++i){
        if(s[i] == '1') ++nb,ans = (3*ans)%MOD;
        else ans = (3*ans - 2^{nb+1})%MOD;
      }
      cout << (ans+MOD)%MOD;
    

    Here is the link : https://atcoder.jp/contests/abc129/submissions/5851108

  • »
    »
    5 years ago, # ^ |
    Rev. 7   Vote: I like it +12 Vote: I do not like it

    Alternative Explanation [doesn't require DP]:

    $$$a+b = L$$$ and $$$a$$$ XOR $$$b = L$$$ $$$=>$$$ $$$a ≤ L$$$, $$$b ≤ L$$$, $$$a$$$ xor $$$b ≤ L$$$, $$$a & b = 0$$$ (bitwise and must be 0)

    Suppose $$$L = 111..1 (n$$$ $$$times)$$$, Now we can choose any $$$k$$$ bit number for $$$k ≤ n$$$ as $$$a$$$ and obviously it will be $$$≤ L$$$. Let's say $$$L = 1111, a = 1010$$$. Since $$$a & b = 0$$$, $$$b$$$ can only have $$$0$$$ in those positons where $$$a$$$ has $$$1$$$ and for others, we will have two option $$${0,1}$$$ for $$$b$$$. For the above case we have total $$$4$$$ options. In other words if $$$a$$$ has $$$x$$$ number of zeroes in it's binary, then $$$b$$$ will have $$$2^x$$$ options.

    Total number of pairs $$$(a,b) :=$$$ (count of $$$a$$$ with $$$x=0$$$)$$$*2^0$$$ + (count of $$$a$$$ with $$$x=1$$$)$$$*2^1$$$ + .. + (count of $$$a$$$ with $$$x=n$$$)$$$*2^n$$$

    $$$C(n,0) * 2^0$$$ + $$$C(n,1) * 2^1$$$ + ... + $$$C(n,n) * 2^n = 3^n$$$ [binomial theorem].

    How to solve for an arbitary L?

    $$$L = 100101$$$

    • We will iterate on all numbers $$$≤ L$$$ starting from MSB. If $$$n^{th}$$$ bit is $$$0$$$ in $$$a$$$, then definitely all $$$a$$$ with $$$n-1$$$ bits are $$$≤ L$$$. So $$$ans += 3^{n-1}$$$. Note that all these pairs will have $$$n^{th}$$$ bit unset in both $$$a$$$ and $$$b$$$ and so $$$a$$$ XOR $$$b$$$ will have 0 in MSB. If $$$n^{th}$$$ bit is set $$$a$$$ then we have to consider next bit of $$$L$$$.

    • Move to the next set bit of $$$L$$$. As explained above, $$$ans += 3^{l-1}$$$ [where l is length of remaining string after this bit], by unsetting this current bit in both $$$a,b$$$. However, now the first bit (MSB) of $$$a$$$ can be $$$0$$$ as well by keeping the MSB of $$$b$$$ as 1. So there are two options for $$$a$$$. Hence $$$ans += 2 * 3^{l-1}$$$. These cases are mutually exclusive from previous case because here $$$a$$$ XOR $$$b$$$ will have $$$1$$$ in MSB.

    • Similary, for next set bit $$$ans += 2^2 * 3^{l-1}$$$.

    Try it with few examples of L, you'll understand better. Basically, the idea is to iterate over a prefix of L and consider it as prefix of $$$a$$$ XOR $$$b$$$ and calculate how such pairs exist and add it to the ans.

    p2:= powers of 2, p3:= powers of 3
    for(i = 0, cnt = 0; i < n; i++){ 
    		if(L[i] == '1') {
    			ans = ans + p2[cnt] * p3[n-i-1];
    			cnt++;
    		}
    	}
    ans += p2[cnt]
    

    Take care of mod in the above code.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Why do we have to consider nth bit unset in b as well in condition 1 While in the second case u r saying msb of b can be 1.

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        We have to count all pairs of $$$a,b$$$ which satisfy the given constraints. In those pairs, some will have $$$a \oplus b$$$ in MSB = 1 and some will have MSB=0. If MSB = 0, then both $$$a,b$$$ have 0 and for other case, we will consider both when $$$b=1,a=0$$$ and $$$b=0, a=1$$$.

        In point 1, I considered only those cases where MSB of $$$a,b$$$ were 0 only. In point 2, those were considered where either of them have $$$1$$$ in MSB

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

already good explanations for problem E on here

but i wanna leave my visualization approach :D

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    What's the time.complexity of your approach. Can you give your submission How are you comparing two binary numbers

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      All the solutions explained here have time complexity proportional to the number of bits in L, $$$O(|L|)$$$

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        but, Why do we have to consider nth bit unset in b as well in condition 1 While in the second case u r saying msb of b can be 1. why its so ?

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          In point 1, the MSB cannot be 1 because in case we make it 1, then we will have MSB set in $$$a \oplus b$$$ which might result in those cases where $$$a \oplus b > L$$$ which we don't want.

          In point 2, since we have unset the next bit of $$$L$$$, we can safely put $$$n^{th}$$$ bit of b or a = 1, because now $$$a \oplus b$$$ will be less than L.

          So it is ok to put the current bit as set when we are considering some bit which is next to this one, but not ok when we are considering this bit. It must be unset and then the cases should be counted.

          Try with a few examples

»
5 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Can anyone explain the matrix part in problem F again [concat operation]. How you got that matrix ?

WaterColor2037

And does anyone have an alternate explanation, like I considered finding the sum $$$(s)*10^d + (s+B)*10^{2d}+...(s+k.B)*10^{k.B}$$$ using geometric progression, but I am stuck because the denominator will be $$$10^d-1$$$ and it might not have inverse mod m

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The matrix is just a representation of the mapping $$$(X, s) \mapsto (X \times 10^d + s, s+B)$$$. Also, I think there's no way to divide with $$$10^d-1$$$ modulo $$$m$$$, so if you want to calculate the sum directly, you have to avoid any divisions.

  • »
    »
    5 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Instead of using modulo $$$m$$$, you can compute the sum using modulo $$$m \times (10^d - 1) )$$$. The result is then divided by $$$10^d -1$$$ and modulo $$$m$$$ after that.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice Editorial.

My approach to E was slightly different and I'd like to share my solution with everybody. I didn't use DP. Rather, I used a few observations.

I was wondering if anybody came up with the solution to F by noticing that at most 10 digits needs to be computed and then doing some kind of brute force to find out the last 10 digits of the sequence.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What i did was i divided the problem into 2 cases. Case 1 : a + b = L, answer would be 2^(number of ones)

    Case 2 : a + b < L For 2nd case, you at least need one 0 at the position where L[i] = '1'. so, iterate from 0 to L-1, if L[i] = '1' make it '0', total ways from the right will be 3 ^ (n-1-i) total ways from the left = 2^(number of ones to the left of i excluding i) hence ways = product of both.

    ways = case 1 + case 2.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, you can say my solution was to make L = L + 1, and then treat the entire problem like Case 2.

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Problem B I think you are trying to get array of number twice.

for (int i = 0; i < N; ++i) {
		cin >> a[i];   //here
		sum += a[i];
	}
	
	int mini = sum;
	int prefix_sum = 0;
	for (int i = 0; i < N; ++i) {
		cin >> a[i];  // and here this line should be removed.
                prefix_sum += a[i];
		mini = min(mini, abs(prefix_sum - (sum - prefix_sum)));
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes you're right. I'll fix this and also try asking to the author of Japanese editorial.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But somehow the code gets AC. It seems that reading from cin after the EOF has no effect and a[i] is not overwritten.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by WaterColor2037 (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you so much for translating. However, i was not able to find a link to the Japanese editorials on atcoder.jp . I was able to find the original (Japanese) editorial through this alternate Link, but when i see the ABC page on atcoder.jp, i can't see a link to the editorial, can you tell me where to look for the editorial on the contest page on atcoder.jp.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There seems to be no link to the Japanese editorial on the English AtCoder page (maybe in order to prevent non-Japanese user from clicking editorial page only to find there's only Japanese editorial). If you set the language to Japanese you'll find a "解説" (means editorial) tab, in which you will find a link to the PDF. Also the first paragraph in my post contains the link to the Japanese editorial anyway.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Atcoder should pay you. And thank you very much