Sadly this is not a game, but you reminded me of Jellyfish Can't Swim in the Night.

so it's star rail

Ok I know its Arknights.

Translation: Hi (maybe Russian), Codeforces! I'm Serval (Japanese) and I speak Servalish (Chinese). Good Luck & Have Fun! (English, obviously)

They probably don't have money. From Last round didn't come money

Are you his alt account ? 😂

As an author, Saule_ is handsome too.

I think its hp's fault, they should equip a better camera on laptop lol

kinda sus!

It was supposed to be codeton I think that’s why

Fire in the hole

Bruh I'm his classmate

Actually he's in NOI2024 Sichuan Provincial Team. He just has no time to take part in CF rounds cuz he usually lives in school

me too

As a fan of Dominater069 I would like to say this.

This round is clashing with Al Ahly vs ES Tunis match — CAF Champions League Final

Ohh boy and here I was thinking why many of the solutions for task C looked very familiar with each other. Even some experts have cheated from the GFG code. Hope that they will be severely punished when the system testings are being done to find copied codes. I would like to draw the attention of the moderators to make sure that the solution codes for problem C are checked against this particular code to prevent any mass cheating

so you tried to cheat?

Suppose $$$v[0] = \lbrace 0 \rbrace$$$, so that it is of length $$$2^n$$$.

Solve recursively, on a given $$$v$$$ of length $$$2^m$$$:

• If $$$m = 0$$$, then it is solveable only if $$$0 \in v[0]$$$.

• If $$$m - 1 \in S$$$, then you can reduce to a new vector $$$u$$$ such that $$$u[i] = v[i] \cap (v[i + 2^{m-1}] - 1)$$$.

• Else, reduce to $$$u[i] = v[i] \cap v[i + 2^{m-1}]$$$.

Then solve recursively for both $$$u$$$'s (both of length $$$2^{m-1}$$$), while carrying your decision. While this may seem naive, the time complexity is $$$O(n2^n)$$$.

u can try merging the constraints as u fix one bit at a time, eg if you fix the 0th bit to be on, then u can combine all x with x+1 (since both of them share all other bits so the other bits must satisfy both their constraints), thus at each level, the array shrinks by 2, while the number of calls double by 2, so in the end the complexity is n2^n

How to solve E without TLE you mean?

My logic: You only need two things no of connected components if we only consider the black nodes in the tree .We only need to check further if the components is 1.

Now to know if the conn comp is a chain you only need to see if the distance between the 2 farthest nodes in the conn comp is equal to the number of black nodes in the tree, in a chain these two farthest nodes are leafs i.e. nodes connected to only 1 black node.

To maintain both conn comp and leafs, you only need the number of black neighbours of a node. Now i did this using segment tree on bfs ordering, since changing the colour of a node only affects its children and parent. My sol is $O(q log^2(n)) but there might be a better way.

Passed it after i changed my compiler ffs

A little bit of DP, but the main idea is adhoc anyway

No, you use DFS to calculate the distance from node A to node B — they should walk towards each other, and will first meet each other at some node C. After that they "travel together", and the number of steps is equal to the number of edges times two, minus the (distance from meeting point C to some furthest node D). Because it's best to "end" the trip in that node from which you don't have to return — so you make this ending node D the farthest one.

How to solve it ?

what was it?? I am still unable to find error in my code.262564497

Same, which got me TLE on pretest 13

after rooting the tree end points of the chain are the black nodes which dont have any black childs so you have keep track of all black nodes which have no black child

Connectivity can actually be checked in a much simpler way: The black nodes are connected iff there is exactly one black node that doesn't have a black parent.

you only have to care about black nodes which have no black child

Would be difficult to maintain. A single query can change up to N values (all neighbors).

I had the same idea during contest and managed to get $$$O(n\sqrt{n}log(n))$$$, complexity but it was to slow. You can maintain big/small vertices and recalculate "black-degree" for every vertex every $$$\sqrt{q}$$$ operations

I ended up with WA7 so I may be wrong, but I believe most of it is correct (and I probably have a bug):

• If none of the strings contain asterisks, then it is easy.

• If both contain asterisks, then check both prefixes and suffixes for equality, until you reach asterisks. If prefixes and suffixes were equal, then it should be "Yes".

Assume now that $$$s$$$ has no asterisks, and $$$t$$$ has at least one. Remove equal prefixes and suffixes, so that $$$t$$$ begins and ends with asterisk. If all of $$$t$$$ is asterisks, answer is "Yes".

Now, you need to take every substring of $$$t$$$ between a pair of asterisks, and match it to the first substring of $$$s$$$ that matches it, greedily.

It's a classical algorithm to determine whether a string can be anothers' substring, when both may contain '-' symbols, using fft in $$$O(n \log n)$$$ where $$$n$$$ is the larger of those lengths.

Now, to find the first position in which a substring of $$$t$$$, of length $$$m$$$, matches in $$$s$$$, starting from a given index $$$i$$$, you can do an exponential search:

Check if the substring appears in the substring of $$$s$$$, starting at $$$i$$$ of length $$$m$$$. If it isn't found, increase to length $$$2m$$$, and so on until it is found.

The total complexity should be $$$O(n \log^2 n)$$$.

I have the opposite opinion. In fact I found that D, F >> E.