We will hold Mynavi Programming Contest 2021（AtCoder Beginner Contest 201）.

- Contest URL: https://atcoder.jp/contests/abc201
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210515T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: chokudai, kyopro_friends, penguinman, QCFium
- Tester: kyopro_friends, tatyam
- Rated range: ~ 1999

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

We are looking forward to your participation!

Thank you, sir, for making this contest.

How to solve today's D ?

I have uploaded a video solution for the D problem (DP and Game Theory): https://www.youtube.com/watch?v=4YvP747OUUk&t=5s

Thank you, but I dont know about minimax, how can I learn it from basic ?

Minimax is just a type of problem in Game Theory and the best way to learn it would be to solve problems related to it. (A lot of Minimax problems are also Dynamic Programming.)

You can solve LeetCode problems on Minimax first — https://leetcode.com/tag/minimax/

The above list also includes the problem "Predict the Winner" which I mentioned in the video.

There are also a few Geeks for Geeks articles which you can read on Minimax starting from this one — https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-1-introduction/

Thank you with much respect !

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

I think you meant problem E.

Same problem

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.

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.

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

Thanks for that TL on E. Reminded yet again how dangerously slow

vector push_backcan be smhI got three TLE because of this.

what we have to use instead.?

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

Were you working with many small vectors?

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

Here are my solutions,

ABCEUPD: 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 :DD 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.

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.

D

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

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 ;(

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

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

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

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,

DCan E be solved using Centroid Decomposition?

Also, E was available online. Link

Thanx got the mistake.

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.

thank you.

Its a very bad mistake.

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

You haven't initialized factorial[10] in your code.Try defining it and then try this test case:??????????. Answer is10000.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.

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

Can someone tell me why my D is wrong? link

Here's a brief description of what I thought —

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

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

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

how to solve C using Permutations and combinations?

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

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

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].

PLEASE CHECK MY SUBMISSION FOR D https://atcoder.jp/contests/abc201/submissions/22645087

.

How to solve F?

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