Yes, top $$$3$$$ teams will be given certificates and coupons from AlgoZenith

how to solve team rocket and jiggly puff. Help Us...god will help u :D

We thought of BLAZE via suffix automaton and small to large merging. Think it like this, for a node in automaton, it corresponds to a set of continuous suffixes with set of endpos. Also for a unique string from that set, the power is achieved from closest 2 indices in it's endpos set. So we can maintain the closest pair of indices using small to large merging on the suffix link tree of the automaton. And from there, it's basic math.

I think BLAZA can be done this way (I might be wrong), I ran out of time implementing it.

First we build suffix automaton for the given string and get the tree of links. For each node (state) we can maintain index where that suffix ends and occurences of the string at that state.

Also for each node of the tree, we have to find the two closest indices considering all nodes in its subtree (which can be done using DSU on trees).

Finally, for each node we know the length of the 2 closest occurences, the lengths of strings that appear at that node and number of times it appears in string.

First, notice that if the peak is to be at an index $$$i$$$, each element to the left and to the right must be strictly decreasing from $$$i$$$. We can greedily select two adjacent elements, say $$$a[j]$$$ and $$$a[j + 1]$$$, and make $$$a[j]\ <\ a[j\ +\ 1]$$$ (given $$$j$$$ is to the left of $$$i$$$): if $$$a[j]$$$ is already less than $$$a[j\ +\ 1]$$$, you need $$$0$$$ operations, otherwise you need to make $$$a[j\ +\ 1]\ =\ a[j]\ +\ 1$$$ operations, which requires $$$a[j]\ +\ 1\ -\ a[j\ +\ 1]$$$. But since, we cannot traverse all the way in the left and right, we will keep a prefix sum array that tells you the number of operations you need to make a prefix strictly increasing; similarly we will keep a suffix sum array that tells you the number of operations you need to make a suffix strictly decreasing. Now, to make index i a peak, the total number of operations is just $$$min(p[i]\ +\ s[i\ +\ 1]$$$, $$$p[i\ -\ 1]\ +\ s[i])$$$. The minimum over all indices is the answer.

We will contact you as soon as possible.

It can be solved using centroid decomposition and some hardcoding but we don't have enough time to finish the solution.

Its wrong

I didn't take the round, but is there any reason this solution doesn't work?

Let a state consist of the current vertex and the last vertex on the path (or $$$-1$$$, if no such vertex exists). Note that there are $$$O(N)$$$ possible states. Then, using a BBST, we maintain a list of processed states in increasing lexicographic order of their strings. To insert a new state, we take the minimal letter on any outgoing edge and, if multiple edges share that letter, we take the edge to the lexicographically minimal string. A naive implementation of this approach would be $$$O(N)$$$ per state in the worst case, but I believe it can be implemented efficiently using rerooting DP.

From here, we know which edge we'll take out of each state. The rest of the problem can be solved using binary lifting.

We will solve all the queries offline. The topics which we will require are centroid decomposition, rolling hash, lca and binary lifting. Lets say we have a node $$$u$$$ and there is some query whose starting node is $$$u$$$. Then we can check all the paths(In given tree) whose one end is $$$u$$$ using the ancestors of $$$u$$$ in centroid tree(These ancestors will be internal nodes of paths in given tree). This can be done by maintaining an array for each path_length (Of paths in given tree) from current root (current root is root of subtree while traversing a subtree of decomposed tree) which will have least lexicographic "path" and we do updates everytime we go to a node.

After each update we need least lexicographic answer possible. So for update, we use binary search on hashes (which we can store in $$$O(N)$$$ and query them in $$$O(1)$$$ time) and binary lifting to find the first node / character between two candidate "path" to get the first mismatch and we compare them accordingly.

The final time complexity is $$$O((N + Q) * log^3N)$$$ in which $$$O(N*logN)$$$ is from travelling each subtree of centroid tree, $$$O(Q*logN)$$$ is from getting the final path for each query. Also, every time we perform an update it takes $$$O(log^2N)$$$ (Because of my implementation).

If any one has other approach / solution then do mention them here. Hope every one liked the problemset :P

solution