Auto comment: topic has been translated by hochesh (original revision, translated revision, compare)

It is basically oeis problem — calculate ev of times a_i would be added to jth vertex if i is ancestor of j and path length between them is k. Turns out if this value is b_k, then b_k * k! is oeis sequence with linear recurrence. And as tree is random we can easily calculate the answer

Problem D is similar to task which was on Open Olympiad in Informatics last Friday/Saturday in Russia. Key idea is to notice that string A(Ar)A can be represented by two string A(Ar), and (Ar)A which are palindromes. So we need to calculate number of positions (i < j) such as exist palindrome in center i covering j and palindrome in j covering i.

We can precalculate by Manaker algorithm for each position pos val[pos] — maximal k that s[pos-k-1...pos+k] — is a palindrome. In these terms condition to (i, j) is the following: val[i] >= j — i

val[j] >= j — i

we can iterate overall positions i and we need to find out number of such i + val[i] >= j > i: val[j] >= j — i

val[j] — j >= i

j — val[j] <= i

so we need to calculate number of j in [i+1...i+val[i]] such as j — val[j] <= i.

It can be easily done by scanline with Fenwick Tree in O(NlogN) time.

I wonder if it exist linear solution. If somebody knows it — write please!

For Double Palindromes, I got the manacher array of even palindromes.

Now, for each index $$$i$$$, I want to check if it can be the start of $$$A^{r}$$$ part. This is equivalent to finding cardinality of set $$$ \{ l | 1 \le l \le d_2[i], d_2[i+l] >= l \} $$$ and adding for all $$$i$$$.

With some manipulation, you can make new array $$$ a[i] = d_2[i] - i $$$, and now, for each $$$i$$$ I want to count number of elements in $$$a$$$ from $$$i+1$$$ to $$$i+d_2[i]$$$ such that $$$a[j] \ge -i$$$. I used Merge Sort tree for this, but I got MLE.

In general, how to solve quickly ( implementing fast ) such problem: Given an array $$$A$$$, answer queries $$$L$$$, $$$R$$$, $$$X$$$ ( preferrably online ) where you need to find number of $$$ L \le j \le R $$$ such that $$$ A[j] >= X $$$.

Also, Is there a way to use the very versatile order statistics tree in this type of problems? Except for the Merge sort type of way, where you keep an order statistics tree in each node of segment tree.

I tried solving C using sparse table but got MLE, is there any easier way or any optimization suggestions https://ideone.com/Hxu5SO ?

what's the approach for problem C — the grid with queries problem ?

what's the approach for problem C -the grid with queries problem?

I'm wondering if there's an easier or more obvious solution to the problem C, Confused Robot.

My idea was to precalculate the end position after 1 full application of the instruction string $$$S$$$, for each possible starting position. This lets the robot "skip" every $$$|S|$$$ moves, but unfortunately it's not enough to get us under the time limit.

So the second idea is to precalculate $$$2, 4, 8, ..., 2^k$$$ applications of $$$S$$$. That's a matrix $$$N \times M \times log_2(Z) < 10^8$$$, which is OK.

After that, for each query $$$X, Y, Z$$$, take the starting position and find the largest $$$k$$$ so that $$$|S| \cdot 2^k \leq Z$$$: jump and set this as the new position. Repeat until $$$k$$$ goes to 0. The remaining $$$\leq 100$$$ moves after that can be trivially simulated.

To be clear, this works, but I'm not sure if that was the intended solution.