BledDest's blog

By BledDest, 6 years ago, translation, In English

1051A - Vasya And Password

Tutorial
Solution (Ajosteen)

1051B - Relatively Prime Pairs

Tutorial
Solution (PikMike)

1051C - Vasya and Multisets

Tutorial
Solution (Ajosteen)

1051D - Bicolorings

Tutorial
Solution (PikMike)

1051E - Vasya and Big Integers

Tutorial
Solution (Ajosteen)

1051F - The Shortest Statement

Tutorial
Solution (Ajosteen)

1051G - Distinctification

Tutorial
Solution (BledDest)
  • Vote: I like it
  • +39
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

It should be "If k is odd" in editorial of problem C

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

    It will be fixed in a few minutes. Thank you!

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

In solution for E it should be ax + 1

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

Can anyone explain why the last coloumn won't contain the answer and how are we calculating final answer(why are we xoring with 3)?

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

    Hi there,

    I think you are talking about problem D.

    Well, the explanation skipped a step.

    BB — 00 BW — 01 WB — 10 WW — 11

    This is what the numbers mean.

    The number of new components can be easier to understand in my code here. Let me know if you have any doubts or require further explanation. :)

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

      please , would you like to explain with 1 ,2,3 test case

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

        NilakshiRocks thanks a lot ! I"m glad I could help :)

        9aminul Please read my explanation here and let me know if you have any doubts. :)

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

          thanks a lot

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          [user:ghoshsai5000]Can you please why for this case you are returning 1

          W B W B

          And for below case returning 0 W W W W

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

      Hi ghoshsai5000, Thanks for simplifyinh things.could you help me with one doubt on author's editorial:

      int get(int mask, int nmask){
      	int cnt = __builtin_popcount(mask ^ nmask);
      	if (cnt == 0) return 0;
      	if (cnt == 2) return (full(mask) ? 1 : 2);
              // Please explain this return statementt, based on your code, it should 
             //be: return (full(mask) ? 1 : 0);
      	return (full(mask) ? 0 : 1);
      }
      

      If you can explainn this by any example, that would be great. Thanks :)

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

        Hi,

        Being honest, I didn't understand the editorial code completely. That's why I clearly elaborated all 16 cases in my code with understandable variable names to make the logic extremely clear :)

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

        yes you are correct it would be :

        return (full(mask) ? 1 : 0);

        eg: 
        i i+1
        1 1
        0 0
        
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Proof of complexity of F?

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

    Assume M = O(N), since M <= N + 21. Then, the complexity will be something like O((21*N*lg N + Q * (lg N + 21)). Since the preprocessing part for LCA takes O(N lg N) time and no more than O(N) edges will be erased from the set. We run dijkstra (O(N lg N)) from no more than 21 vertices = O(21*N lg(N)) and for every query we find the lca in O(lg N) and then iterate over all atmost 21 bad vertices to compute each distance in a O(1) time.

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

Here's my code for problem F, I'm not sure why I get WA on test 3 everything seems ok to me. can someone please explain my mistake? 43225756

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

In problem C, i found test case 6 1 1 1 2 2 2 that your solution print A A A A A A, can you recheck it ?

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

Why didn't CodeForces evaluate the code? What's wrong?

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

We can use a type of mergeable segment tree to solve problem G, with O(nlogn) nodes created overall, so the time complexity is O(nlogn).

http://codeforces.net/contest/1051/submission/43232839

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

Can someone explain the Question D. Thanks!

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

Hard to understand Problem D. Can anyone Suggest me some good Editorial.

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

In problem D like the editorial says dp[i][j][mask] be the number of beautiful bicolorings of the first i columns such that j components are already created and can't be modified and the colors of the i-th column are determined by mask. I didn't understand what does mask mean, like what does dp[2][4][0] mean. I wanted to know that ,like dp[2][4][0] mean number of beautiful bicolorings of the first 2 coulmns such that 4 components are already visited , now what does 0 mean here. Someone please explain.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Set dp[n][k][mask] as the number of ways with n columns, k components, ending with mask in the n-th column. You can end up in 4 ways: white-white, white-black, black-white, black-black (that's the meaning of the mask having the values 00, 01, 10, 11). After this, try to figure it out the dp transitions by yourself. Good luck

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Video solution with explanation: https://youtu.be/lSyQQ1T6iQ8

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

hey can someone tell me what's the wrong with this code for problem C ? link — http://codeforces.net/contest/1051/submission/43270735 thanks in advance.....

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

Can someone help me out with what is test 67 on problem E or why my code is going wrong?

43274362

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

    Sorry, after thinking I realized I was just running into anti-hash tests. I was lazy and chose 998244353 as my hashing prime, and the same code AC with 1e9+9.

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

      I advise you to use double MODs because if this submission was in a contest anyone can hack you.

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

My submission in "E — Vasya and Big Integers" was TLE, can anyone help me?

http://codeforces.net/contest/1051/submission/43280760

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

There's an even faster solution for problem D.

Let $$$ww[i][j]$$$ denote the number of $$$2 \times i$$$ grids that end with a column of (two) white squares and have $$$j$$$ components. Define $$$wb[i][j]$$$, $$$bw[i][j]$$$ and $$$bb[i][j]$$$ analogously.

Now, suppose we have a random $$$2 \times (i-1)$$$ grid and we want to find out the value of $$$ww[i][j]$$$. Consider the possible arrangements of the $$$i-1$$$-th column in the random grids:

1) The $$$i-1$$$-th column contains two white squares. In this case, we add $$$ww[i-1][j]$$$ to $$$ww[i][j]$$$. We do this because every possible grid that ends with two white squares and has $$$j$$$ components generates another possible grid (which has one more column and keeps the same amount of components) by adding a column of white squares.

2) The $$$i-1$$$-th column contains two black squares. In this case, we add $$$bb[i-1][j-1]$$$ to $$$ww[i][j]$$$ (notice that we add one column and one component to the grid when we add a column of white squares).

3) The $$$i-1$$$-th column contains distinct squares. In this case, we add $$$wb[i-1][j]$$$ and $$$bw[i-1][j]$$$ to $$$ww[i][j]$$$. This happens because when we add a column of white squares, the number of components doesn't change (the white part of the $$$i-1$$$-th column touches the new column) and, obviously, the number of columns increases by 1.

This means that

$$$ww[i][j] = wb[i-1][j] + bw[i-1][j] + ww[i-1][j] + bb[i-1][j-1] $$$

The other recurrences are left as an exercise to the reader $\dots$

Obs.: Notice that $$$ww[i][j] = bb[i][j]$$$ and $$$wb[i][j] = bw[j][i]$$$ because of symmetry. I only used four distinct arrays in this comment because my reasoning can be expressed more clearly this way.

Therefore, you just need to run a double for loop to update the DP arrays. This can be achieved in $$$O(n \cdot k)$$$ time.

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

Question D java solution

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int mod=998244353;
        int n=sc.nextInt(),k=sc.nextInt();
        long ans[][][]=new long[n][4][k+5];
        //one number condition
        ans[0][0][1]=1;
        ans[0][1][2]=1;
        ans[0][2][2]=1;
        ans[0][3][1]=1;
        //then multiple number condition
        for(int i=1;i<n;i++){
            for(int j=1;j<=k;j++){
                ans[i][0][j]=(ans[i-1][0][j]+ans[i-1][1][j]+ans[i-1][2][j]+ans[i-1][3][j-1])%mod;
                ans[i][1][j]=(ans[i-1][0][j-1]+ans[i-1][1][j]+ans[i-1][3][j-1]+(j>1?ans[i-1][2][j-2]:0))%mod;
                ans[i][2][j]=(ans[i-1][0][j-1]+ans[i-1][3][j-1]+ans[i-1][2][j]+(j>1?ans[i-1][1][j-2]:0))%mod;
                ans[i][3][j]=(ans[i-1][3][j]+ans[i-1][1][j]+ans[i-1][2][j]+ans[i-1][0][j-1])%mod;
            }
        }
        System.out.print((ans[n-1][0][k]+ans[n-1][1][k]+ans[n-1][2][k]+ans[n-1][3][k])%mod);
    }
}