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)

Can anyone explain why did this Code gave WA for problem D on 15 test cases?

int 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;
}

Wrote a huge if-else code on A. I feel dumb.

Nice problems. Appreciate E and F.

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.

My G Submission is failing exactly 1 test set. Anybody knows what might be the problem?

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

i didnt check A1=1

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-=4

1 7 code prints 5 answer should be 7

I used BFS to solve C — https://atcoder.jp/contests/abc270/submissions/35127928. I don't see the error. Someone please help me out

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?