### chokudai's blog

By chokudai, history, 12 months ago, We will hold TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginner Contest 270).

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

We are looking forward to your participation! Comments (27)
| Write comment?
 » I feel that ABCs are becoming more and more difficult. Last time I used 30 minutes on D and this time D is a problem using Dynamic Programming and Games.And also G is same as a Chinese team selection in province problem. The link is Here (in Chinese)
•  » » DP starts appearing frequently from D
•  » » » Games are harder than normal DPs though.
 » Can anyone explain why did this Code gave WA for problem D on 15 test cases? Codeint main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll t = 1; // cin >> t; while (t--) { ll n; cin >> n; ll k; cin >> k; ll arr[k]; for (ll i = 0; i < n; i++) { cin >> arr[i]; } ll takahasi = 0, aoki = 0, i = k - 1; while (n > 0) { if (arr[i] <= n) { takahasi += arr[i]; n -= arr[i]; } else { while (arr[i] > n && i > 0) { i--; } takahasi += arr[i]; n -= arr[i]; } if (arr[i] <= n) { aoki += arr[i]; n -= arr[i]; } else { while (arr[i] > n && i > 0) { i--; } aoki += arr[i]; n -= arr[i]; } } cout << takahasi << "\n"; } return 0; } 
•  » » Greedy strategy doesn't work here, check out the editorial.
 » Wrote a huge if-else code on A. I feel dumb.Nice problems. Appreciate E and F.
•  » » can you please tell me your logic for problem F?
 » 12 months ago, # | ← Rev. 3 →   My F Solution is more case-workish than editorial. UPD: They're both similar lol.Basically, there are 4 cases: Case 1: Use 0 airports and harbors: Just kruskal only on edges Case 2: Use >=1 airports and 0 harbors: It's best to build an airport as cheap as possible on 1 island. Let this island = 'A', then apply kruskal on old edges + new edges from A to other islands(with weight per island 'B' = X[B]), also add cost to build cheapest airport to answer Case 3: Use 0 airports and >=1 harbors: Similar to case 2 Case 4: Use both airports and harbors: Add new edges from both cases 2 and 3, then kruskal on all edges, also add cost to build cheapest harbor and airport.
•  » » Your idea is cool. I didn't realize that by adding two virtual nodes, we could simplify the problem. However, my idea is also to transform the cost among airports or harbors to the kruskal's pattern, but failed.Thanks for sharing your solution.
 » My G Submission is failing exactly 1 test set. Anybody knows what might be the problem?
•  » » I can take a guess but i am not sure, B=0 case?
•  » » » 12 months ago, # ^ | ← Rev. 3 →   You are right this might cause problems and I fixed it. However the 1 failing test case still failing and I asserted that in that test case both G and S are never 0.[EDIT]: Accepted. Turns out I was iterating until $\sqrt{A}$ instead of $\sqrt{P}$ in the getOrder function. Silly Mistake :D
 » I didn't come up with the idea of adding two extra virtual nodes so that the original problem could be reduced to somehow rather standard MST problem. I really struggled handling the cost of adding airports or harbors, but it turned out to be tough without the above idea.Nice problem F, and I have learned something again. Thank you, atcoder team.
 » E should have been in place of D
 » I have solved E with nlogn
•  » » Yeah same, I solved it with a multiset of pairs.Btw did anyone try overkilling it with segment tree lazy propagation?
 » 12 months ago, # | ← Rev. 2 →   i didnt check A1=1
•  » » I think your idea is reasonable as far as I consider.However, the original problem states that a=1. Thus, I think, on one hand, your case is not valid input, and the tutorial is correct under this constraint (if a=1, no stones will be left for sure). On the other hand, if a[i]>1, I agree that the solution does not apply for this case.
 » 12 months ago, # | ← Rev. 2 →   What is the intuition on D-Stones?First, both players try to maximize their own score, not the sum of both scores, right? Else it would not make sense to have two players.Editorial: DP[n]=max{Ai​+(n−Ai​)−DP[n−Ai​]∣Ai​≤n}. The semantics of this equation is: if the first player removes Ai​ stones, he will end up with removing Ai​+ (the number of stones that the second player can remove if the game starts with a pile with n−Ai​) stones, so the desired value is the maximum over all i. So how can this transition work? Here the the stones of both players are somehow "mixed up".Current player gets A[i] stones, plus dp[y] stones, when y is the number of stones available after the move of the other player. How to find that y?
•  » » Instead of bottom-up DP, I found memoized DFS easier to understand in this case. I just wrote one here: LinkIt turns out that maximizing Takahashi's score minus Aoki's score also gets the correct final answer.
•  » » Ok, I found a way to define the dp[] in a way I understand. That isdp1[n] is the number of stones player takes if its his turn at n stones,dp2[n] is the sum of stones player will end up if its his turnThen $dp2[n]=max(a[i] + dp2[n-dp1[n-a[i]]])$
•  » » 12 months ago, # ^ | ← Rev. 3 →   Sum of the stones removed by both players is always $n$. So, if the first player removes $A[j]$ stones, he will eventually end up with $(n-dp[n-A[j]])$ stones (Since the second player can remove $dp(n-A[j])$ stones at max). So, the first player should try to maximize $n-dp[n-A[j]]$ over all j.
•  » » » "Sum of the stones removed by both players is always n."Why is that?
•  » » » » I meant, if there are $i$ stones in the pile, then overall $i$ stones are removed (since $A = 1$).
•  » » » » » Why A=1 ?Cannot find that in the problem statement.
•  » » » » » » Read carefully, even I didn't see it during the contest.
•  » » » » » » » Specifically, look at the constraints. Also, problem statement says "the game is over when the pile is empty", not when the player cannot move (which is usually the case). So they had to make one of the A's 1 for consistent constraints.