I think your algorithm runs in $$$O((n \log n)^{1.5})$$$ time, if the naive algorithm is written to run in $$$O(min(|S|, n / x \log n))$$$ time. This is a generous estimate, so in practice it should be faster. Unless we exploit some specific structure of suffix trees, I don't think we can claim $$$O(n^{1.5 - \epsilon})$$$ upper bound.

It doesn't seem to be accepting submissions currently, but some regionals get uploaded on Baekjoon or CF gyms.

Problems are now available for solving here.

For G, someone mentioned that this problem is similar and I'm guessing that it might be solved with the same ideas.

The official solution for the hardest few problems has been published yesterday. The solution for G follows the same steps as the paper, but simplifies the detail while keeping the solution fast enough. Most significantly, it avoids the usage of dynamic convex hulls.

Using the point-line duality, this problem is equivalent to finding the shortest $$$y$$$-distance between the upper $$$i$$$-level and the lower $$$(k+1-i)$$$-level for some $$$i$$$. This requires computing the $$$(\leq k)$$$-level, which is what the paper does.

We apply the duality again (i.e. come back to the same set of points), and first compute the convex layers. We're only interested in the first $$$k$$$ layers, so we simply compute the convex hull $$$k$$$ times in $$$O(nk \log n)$$$. Then we compute the $$$k$$$-level (not $$$(\leq k)$$$-level) by rotational sweeping. Every time we try to find the next point, we check all $$$O(k)$$$ candidates one by one (at most 2 per layer). Since the complexity of the $$$k$$$-level is $$$O(nk^{1/3})$$$, the sweep works in $$$O(nk^{4/3})$$$. Finally, we compute the $$$(\leq k)$$$-level using plane sweeping. Since the complexity of the $$$(\leq k)$$$-level is $$$O(nk)$$$ and we maintain $$$k$$$ lines every time, it works in $$$O(nk \log k)$$$. The total time complexity is thus $$$O(nk(\log n + k^{1/3}))$$$.

The problem reduces to finding two cycles of the same length. The lengths of cycles are bounded by $$$3$$$ and $$$n$$$, and there are at least $$$n - 2$$$ back edges when you consider any normal spanning forest (any DFS forest in particular). If there are two cycles of the same length containing exactly one back edge each, we're done. Else, all cycles have distinct lengths, and for every integer between $$$3$$$ and $$$n$$$ (both inclusive), there exists a cycle of that length with exactly one back edge. Consider two cycles of length $$$n$$$ and $$$n - 1$$$, and XOR them. Since there already exists a 3-cycle with exactly one back edge, and this new cycle has exactly 2 back edges, we are done.