We will hold TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginner Contest 270).

- Contest URL: https://atcoder.jp/contests/abc270
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220924T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: kyopro_friends, math957963, Nyaan
- Rated range: ~ 1999

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

We are looking forward to your participation!

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

WAfor problem D on 15 test cases?CodeGreedy 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?

My F Solution is more case-workish than editorial. UPD: They're both similar lol.

Basically, there are 4 cases:

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?

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

getOrderfunction. Silly Mistake :DI 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?

i didnt check A1=1

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.

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:

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

afterthe 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: Link

It 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 is

dp1[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 turn

Then $$$dp2[n]=max(a[i] + dp2[n-dp1[n-a[i]]])$$$

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[0] = 1$$$).

Why A[0]=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.