### chokudai's blog

By chokudai, history, 2 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!

• +21

 » 2 months ago, # |   +12 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)
•  » » 2 months ago, # ^ |   +6 DP starts appearing frequently from D
•  » » » 2 months ago, # ^ |   +3 Games are harder than normal DPs though.
 » 2 months ago, # |   0 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; } 
•  » » 2 months ago, # ^ |   0 Greedy strategy doesn't work here, check out the editorial.
•  » » » 2 months ago, # ^ |   0 Yeah, I got it. Thanks.
 » 2 months ago, # |   +6 Wrote a huge if-else code on A. I feel dumb.Nice problems. Appreciate E and F.
•  » » 2 months ago, # ^ |   0 can you please tell me your logic for problem F?
•  » » 2 months ago, # ^ |   0 True..XD
•  » » 2 months ago, # ^ |   0 Happy to see that even experts are doing dumb things like me.
 » 2 months ago, # |   0 Q.1) why greedy does not work in D? please give me a test case.Q.2) how to solve F? please tell
•  » » 2 months ago, # ^ |   0 check the editorial. 10 3 1 3 4 ans = 6
 » 2 months ago, # | ← Rev. 2 →   0 Great contest!!.Felt D,E could have been swapped.
•  » » 2 months ago, # ^ |   0 B was most confusing for me.i wrote too many if else if to solve that problem
•  » » » 2 months ago, # ^ |   0 Yeah took 3 penalties in it
•  » » 2 months ago, # ^ |   0 same
 » 2 months ago, # | ← Rev. 3 →   0 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.
•  » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # |   0 My G Submission is failing exactly 1 test set. Anybody knows what might be the problem?
•  » » 2 months ago, # ^ |   +3 I can take a guess but i am not sure, B=0 case?
•  » » » 2 months ago, # ^ | ← Rev. 3 →   +8 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
 » 2 months ago, # |   0 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.
 » 2 months ago, # |   +1 E should have been in place of D
 » 2 months ago, # |   0 I have solved E with nlogn
•  » » 2 months ago, # ^ |   0 Yeah same, I solved it with a multiset of pairs.Btw did anyone try overkilling it with segment tree lazy propagation?
•  » » » 2 months ago, # ^ |   0 why multiset of pairs ?? you could just take the non-zero numbers in a vector and sort it then iterate skipping the duplicates value or or just take an integer set
 » 2 months ago, # | ← Rev. 2 →   0 i didnt check A1=1
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 You wasted too much time writing that blog
•  » » 2 months ago, # ^ |   +3 I think your idea is reasonable as far as I consider.However, the original problem states that a[1]=1. Thus, I think, on one hand, your case is not valid input, and the tutorial is correct under this constraint (if a[1]=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.
 » 2 months ago, # |   0 problem A has weak testcases https://atcoder.jp/contests/abc270/submissions/35095730 my code passed even tho i typoed i did b=-4 instead of b-=41 7 code prints 5 answer should be 7
•  » » 2 months ago, # ^ |   -8 It's nothing new in atcoder
 » 2 months ago, # |   0 I used BFS to solve C — https://atcoder.jp/contests/abc270/submissions/35127928. I don't see the error. Someone please help me out
•  » » 2 months ago, # ^ |   0 Try this input: Spoiler15 2 13 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15Your output treats "12" as "1" and "2".
•  » » » 2 months ago, # ^ |   0 Thank you
 » 2 months ago, # | ← Rev. 2 →   0 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?
•  » » 2 months ago, # ^ |   +1 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.
•  » » 2 months ago, # ^ |   0 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]]])$
•  » » 2 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » » 2 months ago, # ^ |   0 "Sum of the stones removed by both players is always n."Why is that?
•  » » » » 2 months ago, # ^ |   0 I meant, if there are $i$ stones in the pile, then overall $i$ stones are removed (since $A[0] = 1$).
•  » » » » » 2 months ago, # ^ |   0 Why A[0]=1 ?Cannot find that in the problem statement.
•  » » » » » » 2 months ago, # ^ |   0 Read carefully, even I didn't see it during the contest.
•  » » » » » » » 2 months ago, # ^ |   +1 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.