Can we solve G using segment-tree ? (we search for the minimum value then we query on the second minimum on all intervals containing the first value and we update the interval that contain the maximum number of minimums and so on until we run out of reserve archers..)

Can we solve I using KMP?

Nitpick: complexity of the problem D solution is rather O(n²).

Prob H: Can someone explain how to calculate dp(h, k) values

Can someone explain the solution of E in a bit more detail.

There is no need for binary search on E.

Take the taps that are hotter than T, and the taps colder than T separately. Sort the first set in increasing order, and the second in decreasing order.

Then just greedily turn on the coldest hot taps, and hottest cold taps, while keeping the temperature balanced at T.

The complexity is still O(NlogN) because of sorting, but the actual computation is O(N).

Problem D can be solved in O(m)

hint: for a 'x'-distant node from s, find the nodes which are less than D-x-2 away from t. It can be done using prefix sum. Then cancel nodes which already has edges with current node. details here

Thanks a lot

I don't understand how calculating the convolution helps in Problem I. Could someone elaborate?

Can someone please explain what does problem G (castle defense) wants us to find? I have read the problem over and over again but I just can't get it. Can someone please explain the problem (problem only)?

Can someone please tell me what is wrong in my submission for D ? 38697308

Why WA on test case 8 ?

https://mirror.codeforces.com/contest/954/submission/57313165

Regarding problem number I, how does this solution of _shanky pass the time limit of 4 seconds?

In my calculation this solution runs in almost length(a)*length(b) time, or I'm missing something? awoo, _shanky

It is possible to solve (read: cheese) H with arbitrary-mod FFT. My solution uses the observation in the first part of the editorial, that is, for each $$$d$$$, count the number of paths with depth of LCA equal to $$$d$$$.

It is not hard to think of a FFT-based solution; let's look at the subtree of the LCA and reassign depths so that depth of LCA = 0.

The first case is that both endpoints of the path are in different subtrees of the children of the LCA, in which the answer for paths of length $$$k$$$ is the coefficient of $$$x^k$$$ in $$${c\choose 2}(\text{cnt}_1x + \text{cnt}_2x^2 + \text{cnt}_3x^3 + ...)^2$$$, where $$$\text{cnt}_i$$$ is the number of nodes of depth $$$i$$$ in a LCA-child's subtree, and $$$c$$$ is the number of children of the LCA. This can be done with FFT in $$$O(n\log{n})$$$.

The second case is when the LCA is an endpoint of the path, which means that the answer for paths of length k is $$$c \cdot \text{cnt}_k$$$.

Summing both cases up and multiplying by the number of nodes at each depth, we can get the answer for all path lengths in $$$O(n^2 \log n)$$$.

I used KACTL's template for arbitrary-mod FFT which is reasonably fast, but even then my submission barely squeezed into the time limit.