### chokudai's blog

By chokudai, history, 4 weeks ago,

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!

• +61

 » 4 weeks ago, # |   -27 Thank you, sir, for making this contest.
 » 4 weeks ago, # |   +7 How to solve today's D ?
•  » » 4 weeks ago, # ^ |   +3 I have uploaded a video solution for the D problem (DP and Game Theory): https://www.youtube.com/watch?v=4YvP747OUUk&t=5s
•  » » » 4 weeks ago, # ^ |   +3 Thank you, but I dont know about minimax, how can I learn it from basic ?
•  » » » » 4 weeks ago, # ^ |   0 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.
•  » » » » » 4 weeks ago, # ^ |   0 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/
•  » » » » » » 4 weeks ago, # ^ |   +3 Thank you with much respect !
 » 4 weeks ago, # | ← Rev. 3 →   0 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, # ^ |   0 I think you meant problem E.
•  » » 4 weeks ago, # ^ |   +8
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 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, # ^ |   0 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, # ^ |   0 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, # |   +16 Thanks for that TL on E. Reminded yet again how dangerously slow vector push_back can be smh
•  » » 4 weeks ago, # ^ |   +11 I got three TLE because of this.
•  » » 4 weeks ago, # ^ |   +3 what we have to use instead.?
•  » » » 4 weeks ago, # ^ |   0 Reserve vector space by using vector.reserve() since you already know the capacity of them.
•  » » 4 weeks ago, # ^ |   0 Were you working with many small vectors?
 » 4 weeks ago, # | ← Rev. 7 →   +1 How to solve D ? Could only do A,B,C,E :(Here are my solutions, A//Think simple yet elegant. #include using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define all(v) v.begin(),v.end() #define ff first #define ss second #define pb push_back #define mp make_pair #define pi pair #define REP(i,n) for(int i=0;i> a[i]; sort(a,a+3); if(a[0]+a[2]==2*a[1]) cout<<"Yes"; else cout<<"No"; } int main(){ fast; int t; t=1; while(t--){ run_case(); } }  B//Think simple yet elegant. #include using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define all(v) v.begin(),v.end() #define F first #define S second #define ll long long #define pb push_back #define mp make_pair #define pi pair #define REP(i,n) for(int i=0;i v; string s; int t; int i,n; cin >> n; for(i=0;i> s >> t; v.pb({t,s}); } sort(all(v)); cout< using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define all(v) v.begin(),v.end() #define F first #define S second #define pb push_back #define mp make_pair #define pi pair #define REP(i,n) for(int i=0;i have,pos,no; int cnt=0; vector now; void rec(vector a){ if(a.size()==4){ set haves; bool ok=true; for(int j=0;j<4;j++){ if(have.count(a[j])) haves.insert(a[j]); if(no.count(a[j])) ok=false; } if((int)haves.size()==(int)have.size() and ok) ++cnt; return; } for(int i=0;i<=9;i++){ a.pb(i); rec(a); a.pop_back(); } } void run_case(){ string s; cin >> s; int i,n=s.length(); for(i=0;i using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define all(v) v.begin(),v.end() #define F first #define S second #define pb push_back #define mp make_pair #define pi pair #define REP(i,n) for(int i=0;i>> g(N); vector d(N,0); void df(int v,int p){ for(auto [to,wei] : g[v]){ if(to!=p){ d[to]=d[v]^wei; df(to,v); } } } ll add(ll a,ll b){ return (a%mod + b%mod)%mod; } ll mul(ll a,ll b){ return ((a%mod)*(b%mod))%mod; } ll bin(ll a, ll b) { a%=mod; ll res = 1; while (b > 0) { if (b & 1) res = res * a % mod; //mod a = a * a % mod; //mod b >>= 1; } return res; } void run_case(){ ll i,j,n,u,v,w; cin >> n; for(i=0;i> u >> v >> w; --u,--v; g[u].pb({v,w}); g[v].pb({u,w}); } df(0,-1); vector cnt(60,0); for(i=0;i
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 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, # ^ |   0 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 →   0 Ddp[i][j]: max{score of first — score of second } starting from (i,j)
•  » » » 4 weeks ago, # ^ |   0 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, # ^ |   0 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
•  » » 4 weeks ago, # ^ |   0 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 winand if you get negative value it' Aoki winelse if you got zero it's a Drawyou can check my submission of recursive dp [Recursive dp sol.]You can ask me if you have any doubt, though my code is self-explanatory and easily written
•  » » » 4 weeks ago, # ^ |   0 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//Think simple yet elegant. #include using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define all(v) v.begin(),v.end() #define ff first #define ss second #define pb push_back #define mp make_pair #define pi pair #define REP(i,n) for(int i=0;i> h >> w; for(i=0;i> g[i][j]; } //Game ends at (h-1,w-1). //dp[i][j] = (TS-AS) value we can get if game starts from cell (i,j). //T will try to maximize difference in their turn. //A will try to minimize difference in their turn. //dp[0][0]>0 then T wins. vector> dp(h,vector(w)); dp[h-1][w-1] = 0; for(i=h-1;i>=0;--i){ for(j=w-1;j>=0;--j){ if(i==h-1 and j==w-1) continue; if((i+j)%2){ //A dp[i][j]=1e9; if(i+10) cout<<"Takahashi"; else if(dp[0][0]<0) cout<<"Aoki"; else cout<<"Draw"; } int main(){ fast; int t; t=1; while(t--){ run_case(); } } 
 » 4 weeks ago, # |   +19 Can E be solved using Centroid Decomposition?Also, E was available online. Link
 » 4 weeks ago, # | ← Rev. 2 →   +5 Thanx got the mistake.
•  » » 4 weeks ago, # ^ |   +3 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, # ^ |   +3 thank you.Its a very bad mistake.
 » 4 weeks ago, # | ← Rev. 2 →   0 Where I am doing mistake? Someone, please help me figuring that out My Solution Atcoder ABC 201 C?
•  » » 4 weeks ago, # ^ |   0 You haven't initialized factorial[10] in your code. Try defining it and then try this test case: ?????????? . Answer is 10000.
•  » » » 4 weeks ago, # ^ |   0 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, # |   0 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, # |   0 Can someone tell me why my D is wrong? linkHere's a brief description of what I thought — We know who will be the person to place the token on every square. (in particular the last square). 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 →   +3 Can someone tell me Why I am getting WA on E? I had used same approach as Editorial. SubmissionEdit: 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, # |   0 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, # |   0 how to solve C using Permutations and combinations?
•  » » 4 weeks ago, # ^ |   +4 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, # ^ |   -8 same, I tried an hour to make a formula but failed :(
 » 4 weeks ago, # |   0 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 > f(h, vector (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 > dp(h, vector (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, # |   0 PLEASE CHECK MY SUBMISSION FOR D https://atcoder.jp/contests/abc201/submissions/22645087
 » 4 weeks ago, # | ← Rev. 2 →   0 .
 » 4 weeks ago, # |   0 How to solve F?
 » 2 weeks ago, # |   0 Did anyone manage to pass TL in problem E with Centroid Decomposition?