### chokudai's blog

By chokudai, history, 2 months ago,

We will hold KYOCERA Programming Contest 2022（AtCoder Beginner Contest 271）.

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

We are looking forward to your participation!

• +30

 » 2 months ago, # |   +9
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Also about D:If I am not wrong, then I think I have seen it on topcoder (in recent SRMs)Edit: Problem D
•  » » » 2 months ago, # ^ |   0 yeah, I realized as well.. that I have seen similar problem before!
 » 2 months ago, # |   0 How to solve G?
 » 2 months ago, # |   0 In problem D. can anyone point out my mistake please... Your code here... int dp[105][10005]; void myfunc() { int n, s; cin >> n >> s; vectorfi(n), se(n); for(int i=0; i> fi[i] >> se[i]; memset(dp, -1, sizeof dp); string ans; function sldp = [&](int i, int sum) { if(i==n) { return (sum==s? 1ll: 0ll); } int &res = dp[i][sum]; if(res!=-1)return res; res = 0; int c1 = sldp(i+1, sum+fi[i]); if(c1) { ans.push_back('T'); return res = true; } int c2 = sldp(i+1, sum+se[i]); if(c2) { ans.push_back('H'); return res = true; } return res = false; }; if(sldp(0, 0)==0) { cout << "No" << endl; return; } cout << "Yes" << endl; reverse(all(ans)); cout << ans << endl; } 
•  » » 2 months ago, # ^ |   0 It looks fine. help pls
•  » » 2 months ago, # ^ |   0 in Output section: be H if the i-th card should be placed with its front side visible, and T with its back.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 :((Thanks i wasted more than 1 hour thinking what's wrong here.
 » 2 months ago, # |   -28 Don't think it proper to put such a problem at Ex. All it requires is careful drawings. Maybe it's better to put it at E or F.
 » 2 months ago, # | ← Rev. 2 →   0 Can anyone find a counter test for my solution?My solution
 » 2 months ago, # |   0 C, why this complecated rules to implement.Why not read volumes in order if exist, else sell the two with higest volume numbers?Tried to implement it, but WA. Why?
•  » » 2 months ago, # ^ |   +1 actually ono should use duplicate volumes first
•  » » » 2 months ago, # ^ |   0 Yes, I did read this in the tutorial. Why?
•  » » » » 2 months ago, # ^ |   0 because they are useless, we just read each volume once.take this as an example: currently 1, 1, 2, 2, 4, 5. and you finish reading volume 2. what should you do next?
•  » » 2 months ago, # ^ |   0 The following input should result in answer of 5, not 4. Spoiler7 1 2 4 1 6 7 271 
•  » » 2 months ago, # ^ |   0 try that case : 6 1 5 4 3 2 1answer : 5
•  » » 2 months ago, # ^ |   +3 Counter test: 5 1 2 2 3 5 Actually, I just used binary search. It is easy to implement and not easy to get wrong. Here is the implementation, in case anyone is interested.
•  » » » 2 months ago, # ^ |   0 Same, thought i overkilled it lol
•  » » » 2 months ago, # ^ |   0 Yeah, tried greedy and failed thrice, switched to BS implemented it in one go T_T rank so low only because of this
 » 2 months ago, # |   +17 E was a nice dp problem
 » 2 months ago, # |   +3 Could someone help me figure out that one test case this implementation for problem C fails on.
•  » » 2 months ago, # ^ |   +6 Counter example: Spoiler42 2 2 3
•  » » » 2 months ago, # ^ |   0 Thanks.
 » 2 months ago, # |   0 D seemed easier than C. My submission is giving WA on 6 cases. Can someone provide a counter? Thanks in advance.
•  » » 2 months ago, # ^ |   0 10 2 5 9 10 10 13 13 13 16 16 Expected: 6 Received: 5
•  » » » 2 months ago, # ^ |   +3 Just a minor bug, thanks for this counter tc.
 » 2 months ago, # |   0 For problem F, it took me a long time to come up with the idea of meet-in-the-middle, but it was a pity that I didn't finish coding in time. Anyway, great problems, and hope next time I could do better.
•  » » 2 months ago, # ^ |   +3 Same here. Next time we'll do better!
 » 2 months ago, # |   +5 Problem D and F are exact questions which was asked to me in a Google OA.
 » 2 months ago, # |   0 Why this logic didn't work in F?Divide the square matrix into 2 equal triangles then start from $(1, 1)$ and calculate for every cell $(i, i)$ in the diagonal of the triangle, the no of ways to reach with xor sum as $k$ (say $dp[i][k]$, when $i = j$). Then do a dfs from $(n, n)$ [with $(i - 1, j)$ and $(i, j - 1)$ moves], when reaching to cell $(i, i)$, say we have current xor sum as $k$ add $dp[i][k$ xor $val[i][i]]$ to the answer.implementation
 » 2 months ago, # |   +3 E was nice, tried heavy dfs implementations, only to realise that a simple dp array will suffice
 » 2 months ago, # | ← Rev. 2 →   +8 In editorial of G, I don't understand the O(N) solution part. Can someone explain please?In O(logN) part, how are we getting this formula for DP
 » 2 months ago, # |   0 The simplest editorial for problem C: https://atcoder.jp/contests/abc271/editorial/4937
 » 2 months ago, # |   0 Problem F's same and a bit harder version https://www.geeksforgeeks.org/count-of-possible-paths-of-given-matrix-having-bitwise-xor-equal-to-k/
 » 2 months ago, # |   +13 How to solve G,I can not understand it.
•  » » 2 months ago, # ^ |   +3 I am assuming that you understood infinite sum part. Take a dp matrix of size 24*24, dp[i][j] = probability that next move is at jth hour if last move was at ith hour. The probability of 1st move at jth hour is dp[23][i], i.e, setting 23 as the last move. So we can get the 1*24 matrix which would store the probability of getting at ith hour after 1st move by multiplying matrix initialState(it is of size 1*24, all values except 23 is 0 and initialState[0][23] = 1) by dp matrixNow let dp[i][j][k] (NOTICE: this is different state from editorial for simplification purpose first) = probability of ending at kth hour on ith move if last move was at jth hour. Now to get the probability of getting (i+1)th move on kth hour, let's assume that we are at xth hour on ith move and now we need to go on kth hour in next move, the conditional probability will be dp[1][x][k], so total probability will be dp[i][j][x]*dp[1][x][k]. So, dp[i+1][j][k] = $\sum_{x=0} ^{k-1} dp[i][j][x]*dp[1][x][k]$. So dp[i+1] can be written as dp[i]*dp[1], note that dp[i] and dp[1] are matrices of size 24*24So dp[i] = $(dp[1])^{i}$You can solve the above matrix with matrix exponentiation method and for getting probabilities you can multiply with matrix discussed in paragraph 1
 » 2 months ago, # | ← Rev. 2 →   0 In problem E, if we can choose the edges in sequence $E$ arbitrarily (not sequentially). Then how to find the shortest path? Do we have to use some classic algorithm (like Bellman-Ford) on sequence $E$?
 » 2 months ago, # |   +3 m_99, the English version of the editorial of G is completely broken and doesn't deliver your message. Could you please take a look and rectify the errors? Thanks.I was only able to understand the solution after putting the Japanese editorial into a translator...