Hi everyone, sorry for the considerable delay. It turns out, we were exhausted yesterday from supervising two contests back-to-back. We are surprised by the number of participants in the online mirror. And I hope you enjoy the problems :)

Our big surprise was problem B. We were setting it to be a medium problem. Turns out, maybe the observation is not that obvious.

**fun fact:** Initially, we don't plan to have any particular naming theme other than the obligatory first letter matches the problem order. However, when naming 6 out of 9 problems, one of my committee member noticed that **5 problems** have A of B theme. So, we decided to continue using this theme.

Here are the authors and first solvers for all problems:

**A — Arena of Greed**

Author: JulianFernando

Expected difficulty: Medium

Tag: greedy

First solver: kotamanegi

**B — Blue and Red of Our Faculty!**

Author: dewa251202, hiddentesla

Expected difficulty: Medium-hard

Tag: dynamic programming

First solver: team NeedHelpPls: MiricaMatei, AlexLuchianov, Gioto

**C — Captain of Knights**

Author: AMnu

Expected difficulty: Very hard

Tag: math

First solver: team Extra Registration: LJC00118, xay5421, Sooke

**D — Danger of Mad Snakes**

Author: hiddentesla

Expected difficulty: medium

Tag: Inclusion-exclusion, DP prefix sum.

First solver: team hsy-DD: Yukikaze_, Fuyuki, xzx34

**E — Excitation of Atoms**

Author: hiddentesla

Expected difficulty: easy-medium

tag: Adhoc, casework.

First solver: jiangly

**F — Flamingoes of Mystery**

Author: hocky

Expected Difficulty: easy

Tag: Adhoc

First solver: Team LCA on Cactus: shart23, Dart-Xeyter, sevlll

**H — Huge Boxes of Animal Toys**

Author: hocky

Expected Difficulty: easy

Tag: Adhoc

First solver: idea guy, snake wrangler, and deep learner: oof_ouch_owie, epicxtroll, WolfBlue.

**I — Impressive Harvest of The Orchad**

Author: hocky, hiddentesla

Expected Difficulty: Hard

Tags: SQRT algorithms, Segment tree beats.

First solver: IIT Patna: ravik1, Sixpathsguy, darklight13

Code: 94148836

$$$O(N^2 \sqrt{N})$$$ code: 94149019

$$$O(N^2)$$$ code: 94149066

code: 94149150

code: 94149327

code: 93947185

code: 94151055

code: 94151563

Code (without lazy propagation): 94152055

Code (with lazy propagation): 94152123

**Honorable mention:** the fastest $$$O(NQ)$$$ solution during the contest: 93941953

# About problem G

Problem G was really saddening. We had a cool solution using convex hulls. The solution idea is for we find all connected components of "#". For each CC, we push to a set all non-"#" squares connected in the top, right, left, and down of each '#' and then build a \textbf{convex hull} from the set. The convex hull is then marked the safe zone. If the thief can reach one of these safe zones, the answer is "lolos".

However, after the contest, one participant found the counter case on solutions like this:

```
5 5
M....
.....
..#..
...C.
.....
```

The distance from the thief to each safe zone is not less than Mr. Chanek. However, the thief can move to bottom-right, which can then react to Mr. Chanek's next move. (output is "lolos", jury will print "tertangkap").

We are sad and are currently finding the correct answer. We have also taken down the problem (for now). We manually verify every test case during the test generation of this problem, so they are correct. During the contest (official and mirror), nobody managed to pass the test cases (except jiangly), so it does not affect the standings. However, broken is still broken. We hope it does not reduce the enjoyment of the other problems that much :(.

Can anyone explain if 2*k — 2 > k why we should go for second case?

Problem A

Because then we get the same number of coins as the first case, but there are more coins left in the chess. This is of course better, since we can collect more coins on the long run.

Shouldn't it be considered as the profit I'm making over the other user? In one turn I get 2*k, while my opponent gets 2, Hence 2*k-2(For the first case) For the second case, I get 2*k, while my opponent gets K. Hence he diff 2*k-k=k

Yep, that's another way of seeing it. Also you can read my explanation replying to gameface_123

In the question Arena of Greed, let us say that we have

4kcoins. If we pick2kcoins, what is the guarantee that the opponent will pickkcoins? Since the opponent also plays optimally, is it guaranteed that from2kcoins, his optimal strategy is to pickkcoins? Can someone explain this?Yeah, the opponent may have a manuver. However, no matter what move the opponent makes, us picking 1 coins when having 4k (k > 1) coins always guarantees us having the same (or more) coins that taking n/2 coins, while there are more coins left on the board (which is better, since we can get more coins overal)

A different perspective:

Lets say we take the first case. We have 2k coins. The maximum number of coins we can get from the following moves is less than k-1. Because obviously the opponent wants to minimize our score, and a possible move is to take k coins which results in us having at most k/2 + k/4 + ... which the sum cannot be greater than k-1 coins.

However, if we take the second case. We get 2k coins while there are 2k — 2 coins remaining. Just by halving again, we already get k — 1 coins. Which is better than the maximum coins we get from the first case.

How to think of "4k" intuitionally?

I think intuition comes with practice and experience. For me the intution is, as explained in the editorial, to minimize the number of coin that the opponent get. When solving, it's also a good idea to brute force by hand for small test cases, and see if you can find any observation.

In E, what do you mean by "toggling bonds" when K>2?

UPD: Oh I see it now.

Hi, for problem E, it is said that for K >= 2, we can basically excite all atoms starting from anywhere by exciting only 1 atom.

But I want to give a counter TC.

For that TC, clearly we should start from index 2, right? because

`d[2]`

is the smallest among all`d`

. But somehow I couldn't figure out the way to excite all atoms by only exciting one atom, i.e. the second atom using K = 3. So I think for this case, the answer should be`1000002`

instead of`1000003`

. But jury's solution gives`1000003`

. CMIIW.Please help me to point out the way to achieve

`1000003`

in case I miss something.Thanks

Hello, you can change $$$E_2$$$ to $$$1$$$ and then change $$$E_1$$$ to $$$3$$$. So, when you excite atom $$$2$$$, it will excite all atoms.

EDIT: sorry, i misread your $$$K$$$. I thought you wrote $$$K = 2$$$. Ok, minor change: First change $$$E_2$$$ to $$$4$$$. Then change $$$E_2$$$ to $$$1$$$, then change $$$E_1$$$ to $$$3$$$. Same configuration as written above.

Hi, that is for K = 2, right? My case is for K = 3. If we change some bonds 3 times, can we excite all atoms by exciting atom 2 only?

Thanks

yeah misread that, I updated my comment. I updated it the same time you posted this comment xD.

Oh damn, you're right. Thanks a lot! :D

First change E2 to 4. Then change E2 to 1.but what about "You must first change exactly K bonds before you can start exciting atoms."?

That's indeed what we do, right? E2 to 4..then E2 to 1..then E1 to 3. We have changed exactly K bonds (K = 3 here), only then we start exciting atoms. In this case we can just excite 1 atom from atom 2.

Thanks

I used segment tree with two-dimensional tag (A,B) (which means v=max(v+A,B)) instead of segment tree beats and got AC . but I can not analyze its efficiency well , is it O（nlogn）too ？ My Submission: 94211700

For problem I

this break condition:

and this tag condition

Isn't this the same break & tag condition proposed by the editorial? except you implemented it in a different way. Correct me if im wrong.

Yes，this's right !

Yeah that should yield the same complexity. The important thing is that the segment tree should visit the highest vertex which all of its child is harvestable. The implementation details on how to know that information can vary, but it will all give $$$O(Q log n)$$$ complexity since the analysis is not dependant on the implementation details.

Ok I get it. Appreciating your help !

For anyone looking for an easy way to understand problem-A, this is for you.

Let's take an example first, n = 12;

0 has the opportunity take 1 coin or 6 coins, if he takes 6 coins then remaining coins are also 6 and the other person can take 3 coins.

But here's the trick. Take n/2 coins if and only if n/2 is odd and you force the opponent to take the least no.of coins, i.e, 1 coin since n/2 is odd.

Following this approach, we have as below;

0th person: 1 + 5 + 2 + 1 = 9;

1st person: 1 + 1 + 1 = 3

I think you are missing something. For n=12, according to your theory there will come a point where n will be equal to four for the 0th person. According to your theory we should substract one from it since 4/2 is even, but you have taken 2 for the 0th person. Clearly you are contradicting yourself.

In statement of problem B said: "The game ends when Blue or Red can no longer move. That is, there is no two distinct gray routes they can choose to continue moving." Why can't we get situation, when there's one gray edge between red and blue parts of loop?

Yes, lets say we have a cycle like this: 1 -> 2, 2 -> 3, 3 -> 1. Its possible that red takes path 1 -> 2, blue takes 1->3. Now both of them can no longer move because there remains only one edge both of them can choose.

This is handled in the DP, since we can determine red and blue's final position in our fixed cycle uniquely by the difference in the number of edges they took.

The complexity analysis of the solution in the editorial for problem I is wrong. The problem with the proof is that the claim 'each nonzero mark can appear at most once at any given time' is false; multiple siblings of ancestors of node X can gain an 'old mark' when we query X.

In fact, the solution for one $$$A_i$$$ is not $$$\mathcal{O}(Q\log(N))$$$, but actually $$$\Omega(QN)$$$, as the generator below demonstrates. For the generated testcase, the segment tree beats solution 'harvests' about $$$\frac{1}{12}QN$$$ nodes when $$$A_i$$$ is $$$3$$$ (assuming $$$Q$$$ is allowed to be $$$\frac{8}{3}N$$$). The codes in the editorial take around 30 and around 50 seconds respectively on this case on my local machine, so would probably give TLE on the codeforces platform.

GeneratorAs an aside, personally I find segment tree beats solutions quite tricky to prove, but I also find it quite difficult to create testcases that causes them to become slow. So I don't blame the authors; I am just a little disappointed that what first looked like a cool application of segment tree beats turns out to be wrong.

Can anyone check the below code for problem A for 2nd test case:

## include <bits/stdc++.h>

using namespace std;

int main(){

}

Problem B. Can anyone explain why the jury's answer is 22 (test 6)? As I unterstand, there are 2 ways to get stuck in A, 6 ways to stuck in B and 18 ways to stuck in C.

Test 6My answer: 26

Jury's answer: 22

can someone explain me about prefix sum 2d in problem D?

Has anyone else also solved A using DP?