Codeforces Enhancer in Chrome Web Store donsn't seems to work.

Those "Multi rating graph for Codeforces" in Greasy Fork donsn't seems to work, either.

Hello there, here's an unofficial editorial for 1136D. Yui and Mahjong Set by a tester PinkRabbitAFO.

Observation: Focus on the differential of triplets/straights before and after an operation.

By doing an operation on $$$a_i$$$, you'll find that the differential of triplets equals $$$x (x - 1) / 2$$$, where $$$x$$$ equals $$$a_i$$$ before the operation.

So if we did a single operation on $$$a_i$$$, we can get the exact value of initial $$$a_i$$$ iff initial $$$a_i \ge 2$$$, otherwise initial $$$a_i$$$ must be equal to $$$0$$$ or $$$1$$$.

If we did two (or more, but unnecessary?) operation on $$$a_i$$$, we can now get the exact value of initial $$$a_i$$$ no matter whether $$$a_i$$$ is less than $$$2$$$ or not.

One of the most natural ideas is to perform operation in the order of $$$1, 2, \ldots, n$$$, it works like this:

• Now, assume we get the exact value of $$$a_1 \sim a_i$$$, and we want to determine $$$a_{i + 1}$$$.

• If $$$a_{i + 1} \ge 2$$$, done. Just consider the case $$$a_{i + 1} = 0$$$ or $$$1$$$.

• Consider the differential of straights when doing the operation on $$$a_i$$$, let it be $$$d_i$$$ for convenience.

• We have $$$d_i = [(a_{i - 2} + 1) (a_{i - 1} + 1) + (a_{i - 1} + 1) a_{i + 1} + a_{i + 1} a_{i + 2}]$$$ (if any indices out of bounds, just ignore that term).

• If $$$a_{i + 1} = 0$$$, then $$$d_i = (a_{i - 2} + 1) (a_{i - 1} + 1)$$$.

• If $$$a_{i + 1} = 1$$$, then $$$d_i = [(a_{i - 2} + 1) (a_{i - 1} + 1) + (a_{i - 1} + 1) + a_{i + 2}] > (a_{i - 2} + 1) (a_{i - 1} + 1)$$$ (because $$$a_{i - 1} + 1 > 0$$$).

• So we can determine $$$a_{i + 1}$$$ by comparing $$$d_i$$$ and $$$(a_{i - 2} + 1) (a_{i - 1} + 1)$$$.

Note that you cannot use $$$d_{i - 1} = [(a_{i - 3} + 1) (a_{i - 2} + 1) + (a_{i - 2} + 1) * a_i + a_i * a_{i + 1}]$$$, because when $$$a_i = 0$$$ it's impossible to solve $$$a_{i + 1}$$$ (dividing by zero).

It's easy to see that only when $$$i \ge 2$$$, the method will work, so we need to get $$$a_1$$$ and $$$a_2$$$.

But it seems so hard to get any information of them.

Why not brute force? Try all possibilities of $$$a_1$$$ and $$$a_2$$$ (not many, $$$2^2 = 4$$$ at most) and run solution above.

I came up with this idea when testing the round, and got a verdict of WA on test 11.

Unfortunately, it cannot distinguish between $$$a = [1, 0, 0, 0]$$$ and $$$a = [0, 0, 0, 1]$$$.

More optimization needed.

First, notice that we don't need to do an operation on $$$a_n$$$. Why?

When $$$i = n - 1$$$, $$$d_i = [(a_{n - 3} + 1) (a_{n - 2} + 1) + (a_{n - 2} + 1)a_ n]$$$, thanks to the disappearance of the third term, and the coefficient $$$(a_{n - 2} + 1) \ne 0$$$, now can use division to solve $$$a_n$$$.

So we saved a move, where can it be added to?

It turns out if you add the operation to $$$a_1$$$ once more, you'll have a chance to find the correct solution.

That is, ask $$$1, 2, \ldots, (n - 1)$$$ and then $$$1$$$, in total $$$n$$$ operations.

Focus on the new operation, from it we can get $$$a_1$$$ at once.

Don't forget to use $$$d$$$, here $$$d = (a_2 + 1) (a_3 + 1)$$$.

Compare with the first $$$d_1 = a_2 a_3$$$, do a subtraction, we can get the value of $$$a_2 + a_3$$$.

Now the classification comes:

1. If $$$a_2 \ge 2$$$ or $$$a_3 \ge 2$$$, we can immediately get both $$$a_2$$$ and $$$a_3$$$.

2. Else if $$$a_2 + a_3 = 0$$$, $$$a_2 = a_3 = 0$$$.

3. Else if $$$a_2 + a_3 = 2$$$, $$$a_2 = a_3 = 1$$$.

4. Now exactly one of $$$a_2$$$ and $$$a_3$$$ is $$$1$$$ and the other is $$$0$$$.
   Consider $$$d_2 = (a_1 + 1) a_3 + a_3 a_4$$$.
   If $$$a_3 = 0$$$, then $$$d_2 = 0$$$.
   If $$$a_3 = 1$$$, then $$$d_2 > 0$$$.
   So, just check whether $$$d_2$$$ is equal to $$$0$$$ or not.

Now $$$a_{1, 2, 3}$$$ are known, use the method above, problem solved.

#include <cstdio>

const int MN = 105;

int N, lstv1, lstv2, v1, v2;
int dv1[MN], dv2[MN], Tag[MN], Ans[MN];

int main() {
	scanf("%d", &N);
	scanf("%d%d", &lstv1, &lstv2);
	for (int i = 1; i < N; ++i) {
		printf("+ %d\n", i), fflush(stdout);
		scanf("%d%d", &v1, &v2);
		dv1[i] = v1 - lstv1, dv2[i] = v2 - lstv2;
		if (dv1[i] > 0)
			for (int x = 2; x <= N; ++x)
				if (x * (x - 1) / 2 == dv1[i]) {
					Tag[i] = x; break;
				}
		lstv1 = v1, lstv2 = v2;
	}
	printf("+ 1\n"), fflush(stdout);
	scanf("%d%d", &v1, &v2);
	int ndv1 = v1 - lstv1, ndv2 = v2 - lstv2;
	for (int x = 0; x <= N; ++x)
		if (x * (x + 1) / 2 == ndv1) {
			Ans[1] = x; break;
		}
	int delta = ndv2 - dv2[1] - 1; // delta = a[2] + a[3]
	if (Tag[2] >= 2) Ans[2] = Tag[2], Ans[3] = delta - Ans[2];
	else if (Tag[3] >= 2) Ans[3] = Tag[3], Ans[2] = delta - Ans[3];
	else if (delta == 0) Ans[3] = Ans[2] = 0;
	else if (delta == 2) Ans[3] = Ans[2] = 1;
	else if (dv2[2] > 0) Ans[2] = 0, Ans[3] = 1;
	else Ans[2] = 1, Ans[3] = 0;
	for (int i = 3; i <= N - 2; ++i) {
		if (Tag[i + 1] >= 2) {
			Ans[i + 1] = Tag[i + 1];
			continue;
		}
		if ((Ans[i - 2] + 1) * (Ans[i - 1] + 1) == dv2[i]) Ans[i + 1] = 0;
		else Ans[i + 1] = 1;
	}
	Ans[N] = (dv2[N - 1] - (Ans[N - 3] + 1) * (Ans[N - 2] + 1)) / (Ans[N - 2] + 1);
	printf("!");
	for (int i = 1; i <= N; ++i) printf(" %d", Ans[i]);
	puts(""), fflush(stdout);
	return 0;
}

As I mentioned before, until the contest ends (tester round), I didn't realize "$$$1, 2, \ldots, n$$$" is not gonna work.

After communicating with Sulfox about the main solution, I made up my mind to discover a different solution.

After hours of "thinking" (chatting online) I found this solution.

Coincidentally, many participants came up with the same idea, and I'm very glad to see that.

Said too much.
Sorry for bad English expression (didn't check) (hopefully ouuan and Sulfox will fix them in the official editorial).
Questions welcomed.
Gonna sleep (almost 6 AM here).

Hello! I have a problem solving problem 150E — Freezing with Style.

It can be solved by Binary Search & Centroid Decomposition & a bit data structure in $$$\mathcal{O}(n\log^2 n)$$$.

But I'm wondering is there an $$$\mathcal{O}(n\log n)$$$ solution?

I suppose Binary Search should be preserved, so here is a $$$\log n$$$. So the problem is : given a tree with it's edge's weights are either $$$1$$$ or $$$-1$$$, determine whether there is a simple path with non-negative total weight and it's length is in $$$[l,r]$$$.

My idea is to use high-low decomposition, you can learn it here (solution of 1009F — Dominant Indices), it looks like DSU on tree but focus on depth of the subtree instead of size. Because this problem also have something to do with depth, I think this method may help.

I can't go any further this way. So I write this blog and hope someone can help me with this problem, thanks!