Thanks, I will update it immediately.

No div2 contest today?chenjb

In A got AC by building very long path (diagonal zigzag)

Funnily I've have had another solution which locally had better (33%) success rate but it couldn't get AC which is very weird

Strategy in D: call vertex bad if its degree is more than $$$n/2$$$. While there is an edge between bad vertices, delete such edges. It will not break graph connectivity. After that while there is an edge with one bad end which is not a bridge, delete it. After that if there is still a bad vertex, answer is "No", otherwise find any spanning tree.

plz someone write a map from A. i really tired very much because of this shit(

I didn't even know there was geometry. Reading all the statements is too hard.

Both Yuhao and I are very curious about this issue too. In the regional, only 1 team solved I while 14 teams solved J. And testers solved I in the early period of 5 hours.

At first read, we thought you'd have to do the plane-sweep interval expanding/merging thing, before we realized that there are easier solutions because of small bounds. Perhaps other teams had this mistake too?

And in my code I've just got $$$10^9$$$ xD

We had already made a Chinese version and I may make an english version and publish the contest onto gym as soon as I got out of hospital~

J: if the bitwise xor of all pile sizes is $$$X$$$, you want to compute number of values $$$v$$$ in range satisfying $$$v\oplus X \lt v$$$. This happens precisely when $$$v$$$ has a $$$1$$$ at the most significant bit position of $$$X$$$. So maintain bitwise xor and count of values with a $$$1$$$ for each bit position, handle the update with segment tree beats (you need to additionally maintain minimum, count of minimum, and second minimum).

C:

Let's assume you first move in the following order exhausting moves of each type: Right, Left, Up, Down.

Suppose you move initially $$$x_r$$$ units to the right. Let $$$y^r_{hi}$$$, $$$y^r_{lo}$$$ be the maximum/minimum $$$y$$$ coordinate of the points to the right of $$$x_r$$$. Then go to left up to $$$x_l$$$, and let $$$y^l_{hi}$$$, $$$y^l_{lo}$$$ be the highest/lowest $$$y$$$ coordinate of the points to the left of $$$x_l$$$.

The answer to the problem is: $$$2 \cdot x_r + |x_l| + 2 \cdot \max(y^r_{hi}, y^l_{hi}) + \max(|y^r_{lo}|, |y^l_{lo}|)$$$ [1]

To compute this efficiently, we should store for all coordinates $$$x_l \le 0$$$ the four values: $$$x_l + a \cdot 2 \cdot y^l_{hi} + b \cdot y^l_{lo}$$$ where $$$(a, b) \in (0, 1)^2$$$ in a data structure such as a segment tree to query for minimums.

Fix each $$$x_r$$$ and, and depending on the values of $$$y^r_{hi}$$$, $$$y^r_{lo}$$$ you can determine using binary search some intervals to the left where you know in the equation [1] which terms of the $$$max(\cdot, \cdot)$$$ will dominate, and query for minimum in that intervals on relevant segment tree.

Finally, since the order of the moves (LRDU) affects the answer, you should try the four of them, flipping $$$x$$$ and $$$y$$$ axis, and solving the problem multiple times.

Code

The intended solution goes with O(nlog^2n) or even O(nlogn) from zimpha. I got no idea with the TL on Yandex and all work are done by snark since I stayed in hospital for about a week :(

My solution was a pretty standard "merge smaller into bigger on suffix tree" idea.

The hard part of this problem is counting the number of $$$i$$$ so that $$$s[k \ldots n] \lt s[i \ldots n]$$$ but $$$r-k+1 \gt lcp(s[k\ldots n], s[i \ldots n]) \ge r-i+1 \ge 1$$$ (note in particular that this condition implies $$$k \lt i \le r$$$). (The other cases are simple rectangle queries on the set of points $$$(i,rank(s[i\ldots n]))$$$ from the suffix array of the whole string, though you could do smaller into bigger too if you wanted.)

To solve this case, we run merge-smaller-into-bigger on the suffix tree. For each node, we store a set of queries with $$$k$$$ in this subtree satisfying $$$r-k+1 \gt height$$$ sorted by $$$r$$$, and a sorted set of indices $$$i$$$ in this subtree. You can maintain these with smaller into bigger.

Then, we just need to handle all valid query/index pairs from 2 siblings being merged (queries from the left sibling and indices from the right). Once again, we use smaller into bigger. If there are fewer queries than indices, loop over the queries $$$r$$$ and count the number of indices with $$$r\ge i \gt r-height$$$ (so we should store the indices in an order statistic tree, I used PBDS). If there are fewer indices than queries, then for each index $$$i$$$, add one to all queries $$$i \le r \lt i+height$$$ (so we should store the queries in a BBST or compressed seg tree with lazy propagation, I used treap).

All of this is trivial to analyze as merge-smaller-into-bigger with O(log(n))-time data structures, so it naturally achieves O(n log^2(n)). In fact, splay trees and treaps and some other BBSTs can perform union of sets of size $$$m \lt n$$$ in $$$O(m \log(n/m))$$$, so if we use those for everything, we can get $$$O(n\log(n))$$$ runtime.

Solution of E: Contestants may solve it with a bunch of case analysis. But the intended solution is that there must be a permutation that doing all U,D,L,R together. So enumerate all 4! and check whether it is legal.

F (fixed point approach): As we want the minimum making optimal decisions, we can build a recursion:

note. $E_i$ is the expected time to rest with i unused fireworks.

Our main problem is that we need $$$E_0$$$ to solve the problem. If we take a closer look at the recursion, we can realize that:

We can notice that if the $E_0$ on the right is fixed, the function with respect to $$$i$$$ in the positive reals is convex. now we can solve the problem by noting that the resulting value minus the set value gives us the direction of our optimal value in the binary search (if I set a lower value, the minimum takes a higher value and closer to our solution, if I give it a higher value, the minimum takes a lower value.).

double lo = 0, hi = 1e12;
for (int i = 0; i <= 65; ++i) {
  double mid = (lo + hi) / 2;
  if (f(mid) - mid >= 0) lo = mid;
  else hi = mid;
}

To solve each subproblem in good time, note that the minimum value takes it in:

note. where $x$ is the fixed value and $$$\beta = (1 - \frac{p}{10000})$$$

This is the idea we initially had as well. I think you should be able to do this in $$$\tilde{O}(n \log(n))$$$ by maintaining events and whatnot, but I haven't worked out the details.

Regardless, this solution is faster by asymptotic runtime, but not by time to AC!