I like the education field

Skill issue

Would you care to explain how?

When you use n<<1 instead of n*2

int n=1;
n=n+n*2;
cout<<n; // 3

int n=1;
n=n+n<<1;
cout<<n; // 4

warning. and wrong answer

good luck!

You didnt give me CM :(

And E&F are much more difficult than D...

I just can't find my mistake in C. Also having invested too much time in C, I don't want to try D.

Nice round. But C was definitely harder than D.

Yeah. I'm curious to see the editorial for problem C.

I imagine the problem as a trie of height $$$n$$$. A multiset of strings is then an assignment, assigning a weight to each leaf of the trie (the number of strings in the multiset corresponding to that path in the trie). You get to set a limit $$$c[s]$$$ to each non-root vertex denoting the maximum sum of weights in that subtree. However, the actual limit of maximum sum of weights in that subtree is smaller, namely $$$d[s] = \min(c[s], d[u] + d[v])$$$, where $$$u$$$ and $$$v$$$ are the children of that vertex.

Let $$$\mathrm{dp}[i][x]$$$ be the number of ways to assign $$$c$$$-s in a subtree of height $$$i$$$ such that the true limit is exactly $$$x$$$. Clearly $$$\mathrm{dp}[0][x] = 1$$$ for $$$1 \le x \le k$$$ and $$$0$$$ otherwise. In the general case, for $$$1 \le i < n$$$ and $$$1 \le x \le k$$$:

The first term corresponds to the case where the sum of limits in the children is $$$x$$$ and we pick a higher limit at the vertex; the second term corresponds to the case where the sum of limits in the children is at least $$$x$$$ and we pick $$$x$$$ as the limit at the vertex. For $$$i = n$$$ it is a bit different because you don't get to pick a $$$c$$$ there.

The convolutions in the formula above can be calculated using FFT: you calculate a layer of the DP, then use FFT to "square" it and calculate the new one, and so on. The answer is $$$\mathrm{dp}[n][f]$$$.

y1 can be bigger than y2

Got the same bug during contest:(

You need to notice that y1 is no need smaller than y2, and you should query the segment tree from min(y1,y2) to max(y1,y2) instead of y1 to y2.

This bug just delay me 30 mintues from getting accepted.

y1 can be greater than y2. One small change and you would've got AC :_) 165216733

maybe it is dp and stack

cin >> n; vll a(3); for (int i = 0; i < n; i++) { cin >> a[i]; }

in this part n is not the size of array.

the size is always 3.

n is the number on the key in your hands.

it's called x in the problem statement.

I couldn't even get that far lol.
Just totally baffled me.

Arrrrggggghhhh — same for me....

In this problem we have $$$m + 5q = 2 \cdot 10^5 + 10^6$$$ input numbers, pretty big input.

Exactly this is ridiculous my wrong submission was because of this thing. Even the second test does not include hacks for that bug.

today's B and D did feel weirdly lazy/obfuscated...

Root tree from any node. Let val[v] = XOR of values from root to v. XOR of path (x, y) will be val[x] XOR val[y] XOR a[lca(x, y)]. Now if XOR of path is zero you need to change value at lca(x, y). Doing dfs if there is a path in subtree with XOR 0 you can just delete it. Answer is number of deleted subtrees.

There are few observations. The first one was that if we change a value for a vertex, we can ensure that any paths going through that vertex is never zero as there are only $$$n^2$$$ possible different xorpath values versus infinite choices for the value. The second observation was that let's say we know the optimal connected subset of vertices in subtree of root $$$t$$$ that are good, let $$$S_t$$$ denote this set. If we iterate over the children of vertex u and merge all $$$S_{c_i}$$$, where $$$c_i$$$ is the ith children of $$$u$$$ and if there is a bad path in the resulting set, we remove u. We can simulate this via small-to-large with sets which gives us $$$O(nlog^2(n))$$$.

EDIT: Oops, I messed up the details for the first observation.

Swapping same type of bracket makes no difference.

If you try to swap any two brackets of different types, the prefix sum over all these must be >= 2 at all points.

Swapping the last '(' and the first ')' is equivalent to checking if min_range(last '(', first ')') is greater than 2. For all other swaps, they all include this subsequence in this swap, so you only need to check this subsequence.

Like if any other swap work then this will work for example for checking whether a string of parenthesis is correct or not we create a array and do +1 for ( and -1 for ) if we find negative anywhere then it is not allowed string so you already know one solution exist and now what can you try to avoid negative number in array you keep on delaying ) so that the chances for negative number is least

that swap is the most likely swap to be successfull except the ((()))) last ( comes before first ) sequence for a sequence to be valid a) the numbers of '(' and')' have to be equal b) counting from the first, the number of '(' has to be equal or greater than the number of ')' by b) that swap creates the sequence most likely to be valid

number of '?' can be less than 2

I had the same idea. Here is my reasoning why it should work: let a be your first BS. Say we have constructed a greedily. a is an RBS. Say there is another RBS b and let i be the first index where it differs from a. Consider the BS c which is equal to b up to i and constructed greedily after. You can see that if b satisfies RBS conditions, then so does c, then so does your BS with the swap.

Turned out simple bug: f[s[i]=='(']++; assuming f[0] is the number of open brackets :/

You can see the test cases(as yours is wrong at small test case) and run on your local to debug

:(

Me:(

your global arrays are too large. it's basically an MLE for when you have statically allocated arrays

probably templates generate too much code?

Take a look at Ticket 15896 from CF Stress for a counter example.

Found it.Forgot that when all ? are left brackets the array goes to a point that is a undefined zero

as you are a red name, I think it's quite natural for you to have no difficulty of thinking in edu contest.

Also, edu contest is usually implementation based, not so much observation.

what's the smart observation for C?

The input if fairly big, up to 1e6 numbers, so reading input unoptimized takes relevant time.

I had WA8 for a different reason: I thought the problem only cares about leaf node.

It is edu contest, that is usually implementation based. In this sense, reversing the usual orientation actually spices up the problem.

Also they made statement of B stupid irritating to make it more thrilling.

Add this line: ios_base::sync_with_stdio(false); cin.tie(NULL);

well, I have failed C and solved D on previous 2 contests, so I just move to D if I don't get the idea for C within 10 minutes. I think that D problems can be solved methodically, while C problems are a "you either know it or you don't" style.

Consider that logic, then prepend "()" to the input. Obviously that prefix does not change the answer, but you might get another answer with your algo.

agreed

I got wa three times for this

Samee man, bro, same. Too sad, I realised this just after the contest

I had learnt about this pre-built(partial_sum) method to create prefix sums yesterday, unfortunately I was not prepared for custom operations.

Its simple in case of addition. You can read about it here: https://en.cppreference.com/w/cpp/algorithm/partial_sum

After 12 hours seccion of hacking ratings would update

Notice that changing the weight is equivalent to removing that vertex.

One approach is to remove the centroid and solve the remaining trees recursively and then remove the centroid if there still exists a zero path going through the centroid.

It can also be solved using dfs and small to large merging.

no

The code only seems to cover the simple YES-instances, where the number of ? is exactly equal to the number of ( needed, or the number of ) needed after ensuring the first and last characters are correct. However, there are other YES-instances that your code doesn't cover, like this example of ?)?(??. The only valid RBS here is ()(()). No other RBS fits, so the answer is YES.

For the correct approach, I advise checking the editorial. Basically, you figure out how many hidden ( and hidden ) there are. Here, there are an equal number of visible ( and ), while there are four ?, so this means there are two hidden ( and two hidden ). Then we fill up the ?s, first with all ( until one, then one ), then one (, then the rest of the ). For the example of ?)?(??, the result is ())((). We then check if this is valid or not; in this case, it is not valid, because the prefix ()) has more ) than (. Therefore, the RBS must be unique, i.e., only valid choice is all (s, then all )s.

Note that a valid RBS requires that the total number of ( and ) are equal, and that there is no prefix with more ) than (.

Prob D was such a good intro to segment tree though. But yes C was too much of an ad-hoc problem to be considered educational. (although bracket sequence problems are very standard)