### chokudai's blog

By chokudai, history, 3 years 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

| Write comment?
 » 3 years ago, # |   +7 How to solve today's D ?
•  » » 3 years 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
•  » » » 3 years ago, # ^ |   +3 Thank you, but I dont know about minimax, how can I learn it from basic ?
•  » » » » 3 years 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.
•  » » » » » 3 years 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/
•  » » » » » » 3 years ago, # ^ |   +3 Thank you with much respect !
 » 3 years 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
•  » » 3 years ago, # ^ |   +8
•  » » » 3 years 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.
 » 3 years ago, # |   +16 Thanks for that TL on E. Reminded yet again how dangerously slow vector push_back can be smh
•  » » 3 years ago, # ^ |   +11 I got three TLE because of this.
•  » » 3 years ago, # ^ |   +3 what we have to use instead.?
•  » » 3 years ago, # ^ |   0 Were you working with many small vectors?
 » 3 years 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
•  » » 3 years 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.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Ddp[i][j]: max{score of first — score of second } starting from (i,j)
 » 3 years ago, # |   +19 Can E be solved using Centroid Decomposition?Also, E was available online. Link
 » 3 years ago, # | ← Rev. 2 →   +5 Thanx got the mistake.
•  » » 3 years 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.
•  » » » 3 years ago, # ^ |   +3 thank you.Its a very bad mistake.
 » 3 years 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
 » 3 years 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
 » 3 years 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
 » 3 years ago, # |   0 how to solve C using Permutations and combinations?
•  » » 3 years 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
 » 3 years ago, # | ← Rev. 2 →   0 .
 » 3 years ago, # |   0 Did anyone manage to pass TL in problem E with Centroid Decomposition?