chokudai's blog

By chokudai, history, 4 years ago, In English

We will hold Mynavi Programming Contest 2021(AtCoder Beginner Contest 201).

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

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

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

How to solve today's D ?

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

How to solve E in faster than O($$$n^2$$$)? If LCA is intended, why ask dist to be calculated as XOR?

Edit: Thanks Matua, Corrected the error

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

Thanks for that TL on E. Reminded yet again how dangerously slow vector push_back can be smh

»
4 years ago, # |
Rev. 7   Vote: I like it +1 Vote: I do not like it

How to solve D ? Could only do A,B,C,E :(

Here are my solutions,

A
B
C
E

UPD: I was getting DM's to explain my approach in E here it is,

Notice that there is only 1 path from u to v in a tree.

Next this path is passes through the LCA of u,v in that tree.

So $$$d(u,v)$$$ $$$=$$$ $$$d(u,ROOT)$$$ $$$\oplus$$$ $$$d(LCA(u,v),ROOT))$$$ $$$\oplus$$$ $$$d(v,ROOT)$$$ $$$\oplus$$$ $$$d(LCA(u,v),ROOT)$$$

The LCA term gets xorred twice and becomes 0 and we are left with only ROOT distances which can be precomputed.

So essentially we have to find :

$$$res$$$ $$$=$$$ $$$\sum\limits_{i=1}^{n}\sum\limits_{i=1}^{n}{{d[i]}\oplus{d[j]}}$$$

Which is a standard contribution technique problem.

Notice that it will count pairs (d[i],d[j]) and (d[j],d[i]) twice so in the end multiply $$$res$$$ by modular inverse of 2.

For D I thought of some dp of pairs but could not get it to work.

UPD : Thanks for sharing your approaches in D :D

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

    D is a dp problem. Try to think with states row and column where you start and dp[row][col] stores the maximum difference you can get from there. This can be easily correlated to maximum differences from the row+ 1,col and row, col + 1.

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

    D

    dp[i][j]: max{score of first — score of second } starting from (i,j)

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

Can E be solved using Centroid Decomposition?

Also, E was available online. Link

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

Thanx got the mistake.

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

    Probably overflow on line 117. The term $$$aa$$$ could go upto $$$10^{10}$$$ (when half the bits are zero, half are odd). You are multiplying $$$10^{10}$$$ with $$$2^{60}$$$ without applying modulo first.

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

I took a much longer route for E. I used dp. Calculated the number of times a bit can occur and not occur in the paths from node to other node in its subtree. This can be related to the bit distributions from child. Using this, here I calculated the number of times a bit occurs if we consider one node from two different child subtree. Also, the contribution if we consider the present root and any other node in its subtree.
and then adding the contribution from each node, will give the ans. Submission

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

Can someone tell me Why I am getting WA on E? I had used same approach as Editorial. Submission

Edit: got it. Changed "ans=(ans+z*(dp[i]*dp1[i])%mod)%mod;" to ans=(ans+(((z*dp[i])%mod)*dp1[i])%mod)%mod; to get AC, Overflow maybe happening

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

Can anyone tells what's wrong with my solution with problem D,I think that the idea is similar to the editorial,I fail even I change the direction of iterating. My submission's link:https://atcoder.jp/contests/abc201/submissions/22620773

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

how to solve C using Permutations and combinations?

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

    I tried it with PNC and was getting many cases. I guess this problem was meant to bait with PNC and the solution was brute force instead.

    If there is a PNC solution , please tell

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

.

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

Did anyone manage to pass TL in problem E with Centroid Decomposition?