BledDest's blog

By BledDest, 4 weeks 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  

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

In solution for E it should be ax + 1

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
4 weeks 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)?

  • »
    »
    4 weeks 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. :)

»
4 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Proof of complexity of F?

  • »
    »
    2 days 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.

»
4 weeks 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

»
4 weeks 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 ?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks 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.com/contest/1051/submission/43232839

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the Question D. Thanks!

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 weeks 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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I can see, there are total of 1200 Submission to this problem. But after reading tutorial, It seems hard to me.Any good explanation?

  • »
    »
    4 weeks 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

»
4 weeks 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.com/contest/1051/submission/43270735 thanks in advance.....

»
4 weeks 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

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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.

»
4 weeks 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.com/contest/1051/submission/43280760

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i didn't understand the last part(last for loop ) of c problem.. can anyone help me through this.. i am beginner to codeforces..