About problem G

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

Problem A

In the question Arena of Greed, let us say that we have 4k coins. If we pick 2k coins, what is the guarantee that the opponent will pick k coins? Since the opponent also plays optimally, is it guaranteed that from 2k coins, his optimal strategy is to pick k coins? Can someone explain this?

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.

5 3
1 1000000 1 1 1
1000000 1 1000000 1000000 1000000

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

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

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?

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.

#include <vector>  
using namespace std;

int N, Q, A;
vector<int> par;
vector<int> dep;
vector<bool> isleaf;

void buildtree(int& nxt, int p) {
	if (nxt == N) return;
	int at = nxt++;
	par[at] = p;
	dep[at] = par[at] == -1 ? 0 : 1 + dep[par[at]];
	isleaf[at] = true;
	if (par[at] != -1) isleaf[par[at]] = false;
	if (dep[at] == 10) return;
	for (int i = 0; i < 3; ++i) buildtree(nxt, at);
}

int main() {
	N = 50000;
	Q = 50000;
	A = 3;
	par = vector<int>(N);
	dep = vector<int>(N);
	isleaf = vector<bool>(N);
	int nxt = 0;
	buildtree(nxt, -1);
	vector<int> leafs; for (int i = 0; i < N; ++i) if (isleaf[i]) leafs.push_back(i);

	int root = 0, at = 0, wait = leafs.back(); leafs.pop_back();
	vector<int> visit;
	while ((int)visit.size() < Q) {
		int cnt = at == 0 ? A - 1 : A - 2;
		for (int i = 0; i < cnt; ++i)
			if (at < (int)leafs.size() && (int)visit.size() < Q)
				visit.push_back(leafs[at++]);
		if (at >= (int)leafs.size()) break;
		if ((int)visit.size() < Q) visit.push_back(root);
		for (int i = 0; i < A - 2; ++i) if ((int)visit.size() < Q) visit.push_back(wait);
		if ((int)visit.size() < Q) visit.push_back(root);
	}

	printf("%d %d\n", N, (int)visit.size());
	for (int i = 0; i < N; ++i) { if (i != 0) printf(" "); printf("%d", A); } puts("");
	for (int i = 1; i < N; ++i) { if (i != 1) printf(" "); printf("%d", par[i] + 1); } puts("");
	for (int i = 0; i < (int)visit.size(); ++i) printf("%d\n", visit[i] + 1);
	return 0;
}

As 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.

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.

Input
13 15
8 1
1 5
6 11
13 2
11 13
10 12
6 9
1 5
9 3
2 1
4 1
7 1
7 10
8 4
3 12

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