Note that [3..7] should always be next to each other in sorted array. Try every 2 in increasing order and maintain the set of valid positions of [3..7]. Each time pick the highest valid position and then binary search for 1.

My solution: sort the values. We always pick consecutive $$$P_7, P_6, P_5, P_4, P_3$$$, so first decide $$$i$$$ and let $$$P_7 = A[i], P_6 = A[i+1], \dots, P_3 = A[i+4]$$$.

Then, we want to pick the maximum $$$j$$$ s.t. $$$A[j] < P_7 + P_6 + P_5 + P_4 - P_3$$$, and such that some $$$P_1$$$ can still be selected, which holds IFF $$$A[j+1] - A[j] < P_3$$$.

The first condition gives an upper bound on $$$j$$$, and we can find the last position satisfying the second condition before it with a range minimum segment tree.

If you observe that 3,4,5,6,7 should be consecutive, then it's easy to come up with $$$O(n^3)$$$ solution. Then you can simply take top-500 participants and run the $$$O(n^3)$$$ solution. The testers failed to prove or disprove this — I believe it's correct.

F

Brief explanation: consider cycles as a xor vector space, sufficient cycles would be the ones u can get with backedges in DFS tree, because u can take a cycle independently of anything else, by traversing to a cycle, going around the cycle, and traversing back the same path, define D(u,v) as max xor path from u to v, then D(u,v) consists of any path from u to v and some set of cycles. We can take the path from u to v as the one from the DFS tree, define that path as P(u,v). Define R(u) as xor on the path from root to u, then P(u,v)=R(u)^R(v). Now we have to maximize our P(u,v) by xoring it with some cycles. Construct a base for ur xor space, reduce it to reduced row echelon form, then we can greedily starting from the highest bit, if our answer doesnt have that bit, and our base has a vector with that MSB, we can xor our answer with that vector. We can see that only bits we actually care about are the MSB of the vectors from the base. We can see that xoring our answer with a vector from the base doesnt change any other bit that we care about(becaused our base is in reduced row echelon form). So our answer only depends on the base and R(u)^R(v). Going back to the original queries, we only have to count for every bit that is a MSB of a vector from our base, parity of number of pairs of R(u)^R(v) which have that bit set, l<=u,v<=r, if the parity is odd, we add that vector from the base to our query answer, and we have to add to our answer R(u) l<=u<=r if (r-l+1) is even.

Let's set vertex 1 as the root. Each edge's contribution to the answer is either (sum of $$$A_i$$$ in it's subtree) or (sum of all $$$A_i$$$)-(sum of $$$A_i$$$ in it's subtree): later case only happens when the edge is in the path from query vertex to the root. We can maintain the sum of $$$A_i$$$ in each edge's subtree with some path updates and subtree updates, so dfs ordering+HLD is enough.

It seems that A is a standard task with top trees. Top tree is by no means "nice clean" solution, but if you have a good book code, then things will be different.

Nobody involved with the preparation was aware of the fact. It sounds like a high time to learn new technology :) The complexity is $$$O(Q \log N)$$$ in that case.

Model solution of L simply implements this paper. I failed to find any ad-hoc solutions exploiting the structure of graph, and hoped it doesn't exist cause that was the point. But there are ad-hoc solutions as well and I think they are interesting.

You can see some good implementation of Epp98 here. And it is surely a fun read. (I think sufficiently strong competitors can simply come up this from scratch.) I can explain my implementation in detail.

For K, there is a 20-liner solution submitted by Ptz teams, but I doubt the author was aware of it.

D: If we can not cross over two sides, then the problem is easy. You can consider clauses for each wire, and run 2-SAT (which is actually bipartite coloring).

Now the key idea is to consider clauses for each endpoint of the wire, not the wire. If some wire is fully contained in another wire (two endpoints of the interval is contained in another interval), then the two endpoints should lie on the same side. If some wire crosses another wire (exactly one endpoint of the interval is contained in another interval) then we can find two pair of endpoints that should not lie in same side.

You can see that these two cases are sufficient, and we can run the identical 2-SAT with that problem. Time complexity is $$$O(N^2)$$$ and you can optimize this to $$$O(N \log N)$$$ with some typical DS tricks.

If you have a planarity test that outputs an embedding then that's a no-brainer in $$$O(n)$$$

Hint: figure out the condition for answer to be 1, then 2 and so on.

The locality of a sequence is always either monotonically increasing or monotonically decreasing. Our target is to make the whole sequence ascending. So the question turns into decreasing the complexity of the so called 'up-down vector'(UDV) of a sequence. UDV decribes the rise and fall of the sequence. For example:sequence:1 4 3 2 5,and its UDV is 1 0 1 if we use 1 for rise and use 0 for fall. In this case, the rise and fall of the sequence is :1->4 rise!; 4->3->2 fall!; 2->5 rise!

A vital lemma:During the shuffle as the problem decribed,we can eliminate the front and the back elements of the A's UDV (if the length of it is even) and push_back the front element into the sequence B. Since the front and the back elements of the A's UDV is surely different and we can artificially arrange the first rise and the last fall to make it a rise(amuse the front element of A's UDV is 1 here, see the following example!)

Example:The sequence is 6 5 4 5 4 7 8 whose UDV is 0101 and during the shuffle I can successively push 8 7 6 5 4 4 5 in the new sequence which change the new UDV to 01. (In fact, for 0101, I eliminate the first 1 and the last 0 to turn them into a 0,and then for the rest 10 I turn them into a 1.Finally, the new UDV become 01)

I am afraid this is too long to explain the solution. So at last, I only state a conclusion: after a shuffle ,the UDV of the sequence reduce to half and round up. Please write down some sequences, write their UDV, try to eliminate the element to half the UDV and find the law!

Several details are not memtioned above but I think if you master the UDV, it is fun to find out the law in your own! Good luck!

I am a Chinese and I have wrote a blog in Chinese about a month ago. I am afraid and sorry that I can't post the blog here. Any questions, please contact me!

Relevant paper for K.

Relevant paper for H.

Brief explanation: The optimal solution can be partitioned into a chain of circles where the first / last circle have a maximum possible radius and the others simply follow it. This gives an $$$n^2$$$ solution: You enumerate the one with maximum possible radius, and move left/right to find the possible radius for other circle, giving $$$O(n)$$$ candidates of radius for each.

Let $$$D_i = X_i - X_{i - 1}$$$. You can find the maximal increasing / decreasing subarray of "gaps", like $$$D_i < D_{i + 1} < D_{i + 2} ... $$$, In this case, it is not optimal for $$$i, i + 1$$$ point to have maximum radius. This reduces the number of candidates.

Also, you can't move beyond the subarray of gaps (it will make the radius at most 0), so you can just try $$$O(1)$$$ candidate of radius or each circles.

Let $$$dp[l][r]$$$ be answer in segment $$$[l,r]$$$. For calculation we need to choose some $$$i$$$ from that segment to be maximum. For $$$i$$$ it is optimal $$$-C[i][j] + V[i][j] * q[l][r][i] + dp[l][i - 1] + dp[i + 1][r]$$$ to be maximal, where $$$q[l][r][i]$$$ is number of queries from the segment $$$[l,r]$$$ containing $$$i$$$. We can pre-calculate $$$q$$$ and optimal $$$-C[i][j] + V[i][j] * q[l][r][i]$$$ for all possible $$$l,r,i$$$ with convex hull.

Binsearch the answer and do line sweeping with lazy segtrees and std::set.

TL is 4-5x model solution, but suboptimal implementation is easier and tempting. We did not want to block it, but there were other issues when we gave more than 5s.

https://github.com/koosaga/olympiad/blob/master/Library/vimrc.vim

Let's root this random tree at vertex $$$1$$$.

Note that $$$dist(u,v)=dist(1,u)+dist(1,v)-2dist(1,lca(u,v))$$$, we could precalculate the expected distance between $$$u$$$ and root by standard dp(denoted by $$$f_u$$$). Therefore, the remaining stuff is the expected distance between the root and lca of $$$u$$$ and $$$v$$$.

Suppose we have generated a tree according to the procedure described in the statement, we could find the lca of $$$u$$$ and $$$v$$$ ($$$u<v$$$) in the following approach:

• If the parent of $$$v$$$ (denoted by $$$p_v$$$) is exactly $$$u$$$, we are done. Otherwise, $$$lca(u,v)=lca(u,p_v)$$$.

Note that once given the information that $$$i=lca(u,v)$$$, the expected distance of $$$i$$$ and root is exactly $$$f_i$$$ as chosen parents for vertex $$$j \le i$$$ and vertex $$$j>i$$$ are independent. Therefore, we can rephrase procedure generating distribution of distance between $$$lca(u,v)$$$ and root in a handy way:

• Pick an integer $$$x \in [1,v-1]$$$ with probability propotional to $$$a_x$$$;
• If $$$x > u$$$, replace $$$v=x$$$ and goto step 1;
• If $$$x = u$$$, return $$$f_u$$$ (independence needed here);
• Otherwise, set $$$v=u, u=x$$$ and goto step 1;

The last thing is to observe that we could indeed replace all $$$a_x$$$ with $$$0$$$ for all $$$u < x \le v$$$ as $$$x>u$$$ case is just reroll a random number (which is to say that the expected distance is independent with $$$v$$$ and we may denote $$$g_u$$$ the expected distance).

Therefore, we have $$$g_u=\sum_{i=1}^{u-1}\frac{a_ig_i}{S_u}+\frac{a_u}{S_u}f_u$$$, where $$$S_u=\sum_{i=1}^u a_i$$$ (which is similar to previous one).