chokudai's blog

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

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

Thank you, sir, for making this contest.

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

How to solve today's D ?

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

    I think you meant problem E.

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

      Oh man it is exactly same. I spent much time in finally getting the transitions of distribution of bits in paths from a node to any other in its subtree.

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

    Note that $$$dist[u, v] = dist[root, u] \text{ xor } dist[root, v]$$$. (This works because the weights are on edges rather than vertices. The LCA term cancels out in the process).

    Hence, if we compute an array $$$pref\_xor$$$, where $$$pref\_xor[i]$$$ is the prefix xor from the root to the $$$i-th$$$ vertex, we just need to compute the sum of all pairiwise XOR of this arrray.

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

      Yeah this is O($$$n^2$$$). I wanted to know how to do better. Read the editorial so now it's clear.

»
4 weeks 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 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I got three TLE because of this.

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

    what we have to use instead.?

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

      Reserve vector space by using vector.reserve() since you already know the capacity of them.

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

    Were you working with many small vectors?

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

      Thanks, couldn't decide on a proper DP definition (whether $$$dp[i][j]$$$ should represent a winning state boolean value or the maximum score of the first/second player, etc). Keeping it as the maximum difference is a great approach.

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

      Can you please help me as why my dp solution for D doesn't work?

      Logic-
      $$$dp[i][j][0]$$$ -> score of 1st player at $$$(i,j)$$$ travelling from (0,0)
      $$$dp[i][j][1]$$$ -> score of 2nd player at $$$(i,j)$$$ travelling from (0,0)

      now each time when $$$(i+j)$$$%2 == 1 means it is the turn of 1st player to arrive at $$$(i,j)$$$, now he can come at $$$(i,j)$$$ either from $$$(i-1,j)$$$ or $$$(i,j-1)$$$ but he will come from path where difference between scores of players is minimum since 2nd player would have played before him and 2nd player wants to minimize the difference.

      if $$$(i+j)$$$%2 == 0 it means it is the turn of 2nd player to arrive at $$$(i,j)$$$, now he can come at $$$(i,j)$$$ either from $$$(i-1,j)$$$ or $$$(i,j-1)$$$ but he will come from path where difference between scores of players is maximum since 1st player would have played before him and 1st player wants to maximize the difference.

      Here's my submission it fails in only 3 test cases ;(

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

    D can be solved by taking the difference between max score of both the player. if the difference is +ve takahashi wins. we can have state, dp[i][j][k] where 0<=i<row , <=0 j < col and 0 <= k <= 1 for rounds

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

      Please read my comment above you. I tried something similar, can you please help?

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

    A very good approach of D is using dp,

    go both down and side if possible and take max of them,

    but in calculating the transition, don't add the value from next transition, instead subtract it and do this recursively.

    If you get the value as positive it's takahaski win

    and if you get negative value it' Aoki win

    else if you got zero it's a Draw

    you can check my submission of recursive dp [Recursive dp sol.]

    (https://atcoder.jp/contests/abc201/submissions/22653906)

    You can ask me if you have any doubt, though my code is self-explanatory and easily written

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

      I upsolved it and got AC yesterday but thanks for drawing out a recursive implementation, If you are interested in a non recursive one, check this out its really simple,

      D
»
4 weeks 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 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Thanx got the mistake.

  • »
    »
    4 weeks 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 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Where I am doing mistake? Someone, please help me figuring that out My Solution Atcoder ABC 201 C?

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

    You haven't initialized factorial[10] in your code. Try defining it and then try this test case: ?????????? . Answer is 10000.

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

      I did initialise the factorial[10] but my answer is different than yours. There must be something wrong with my logic :(. BTW, thanks for helping.

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

Can someone tell me why my D is wrong? link
Here's a brief description of what I thought —

  1. We know who will be the person to place the token on every square. (in particular the last square).
  2. So I defined 2 dp's — dp1[i][j]: max score(difference of scores) that P1 gets when on (i,j).
    We play the game in a reversed manner.
    dp2[i][j]: max score(difference of scores) that P2 gets when on (i,j).

So the transitions are basically what is the best path to arrive at that square(in reverse). The recurrence and transitions are in the code.

I don't know why this gave WA for 3 test cases. What am I missing?? Is the DP wrong or have I made some mistake in transitions or base cases??
Help would be appreciated

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

how to solve C using Permutations and combinations?

  • »
    »
    4 weeks 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 weeks ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      same, I tried an hour to make a formula but failed :(

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

Can somebody tell me what's wrong with my code for D. I am not building array from [h-1, w-1] but from [0, 0].

int h, w;
cin >> h >> w;
vector<vector<int> > f(h, vector<int> (w));

for (int i = 0; i < h; i++)
    for (int j = 0; j < w; j++) {
        char ch;
        cin >> ch;
        f[i][j] = ch == '+' ? 1 : -1;
    }

vector<vector<int> > dp(h, vector<int> (w));

for (int i = 1; i < h; i++) {
    dp[i][0] = dp[i-1][0] + (i % 2 ? f[i][0] : -1 * f[i][0]);
}

for (int i = 1; i < w; i++) {
    dp[0][i] = dp[0][i-1] + (i % 2 ? f[0][i] : -1 *  f[0][i]);
}

for (int i = 1; i < h;  i++) {
    for (int j = 1; j < w; j++) {
        if ((i + j) % 2) {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + f[i][j];
        } else {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) - f[i][j];
        }
    }
}

string ans = "Draw";
if (dp[h-1][w-1] > 0)
    ans = "Takahashi";
else if (dp[h-1][w-1] < 0)
    ans = "Aoki";

cout << ans << "\n";
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

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

How to solve F?

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

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