A. Ring road

This problem gives us a ring with n nodes and n directed edges, while aksing to reverse several edges to build a strongly connected ring (graph) at the minimum cost. We use Sr to denote the minimum cost. Without loss of generality, we can start with node 1, and implement a DFS. During this process, we may meet such a situation that no further nodes can be visited, if the currently being visited edge is not directed to the next node. Whenever this occurs, we just reverse the edge so that we can move on to the next node, while adding the cost of this edge to Sr.

The above DFS in fact only provides one feasible way to build a strongly connected graph with a total cost of Sr. If we keep the edges reversed above as what their original directions are, but reverse the other edges instead, we will obtain another strongly connected graph (recall that this is a ring) with a total cost of St-Sr, where St denotes the sum of the cost of all the directed edges. Therefore, the final step is to select the minimum one of {Sr, St-Sr} as the answer.

B. F1 Champions

This problem is not quite difficult but a little bit complicated. One may adopt a "struct" (C/C++) to denote each player, which consists of an integer storing the scores, an array storing the number of each rank, and a string denoting the player's name. In each race, whenever we deal with a player, we first check whether the name of this player has been recorded in the "struct". If he or she is a new one, we store him or her in a new "struct" and update the corresponding results; otherwise, we find the index of this player and update the results. Finally, output the answer as the problem asks.

C. Sequence of points

For simplicity, we first focus on the 1-dimension case. It is straightforward to find that M[1]=2A[0]-M[0], M[2]=2A[1]-M[1],....,M[n]=2A[n-1]-M[n-1]. By some careful calculation, we have M[n]=2A[n-1]-2A[n-2]+2A[n-3]-...-2A[1]+2A[0]-M[0], and we further write A=2A[n-1]-2A[n-2]+2A[n-3]-...-2A[1]+2A[0]. Then, we have M[n+1]=2A[n mod n]-M[n]=2A[0]-M[n], M[n+2]=2A[n+1 mod n]-M[n+1]=2A[1]-M[n+1],...,M[2n]=2A[n-1]-M[2n-1]. By some careful compution, we can obtain M[2n]=2A[n-1]-2A[n-2]+2A[n-3]-...-2A[1]+2A[0]-M[n]=A-M[n]=A-(A-M[0])=M[0]. Therefore, M[2n]=M[0], i.e., M[j]=M[j mod 2n]. Thus, we can directly calculate M[j mod 2n] instead of M[j]. As n is of order 10^5, it is sufficient to calculate from M[1] to M[j mod 2n] one by one. For 2-dimension case, the above arguments still hold.

E. Berland collider

I learned a lot from this problem!

I think we should implement some preprocessing first. We enumerate the particles from left to right and denote the position of the first particle that moves to the right as PoR. Similarly, we enumerate from right to left and find the position of the first particle moving to the left as PoL. Obviously, if PoR>PoL, it implies that no particles wil collide. On the other hand, PoR<PoL means that we only need to take the particles between PoR and PoL into consideration.

The key idea of the solution is to implement a binary serach in terms of time. Suppose that collision occurs before some time T (an upper bound). It is then sufficient to run a binary search in the time interval [0 T]. An appropriate value of T can be found by computing the time when the particles at positions PoR and PoL will collide. For each time interval [TL TR], we test that at time Tm=(TL+TR)/2, whether collision have occurred or not. This can be done by enumerating the particles from left to right one by one. When we meet a particle moving to the right, we update the maximum position Pmax that can be reached at time Tm. On the other hand, whenever a particle moving to the left is met, we denote the position it can reach at time Tm as Pleft, and compare it with Pmax. If Pleft>Pmax, it means that there is still no collision, and we move on to the deal with the next particle; otherwise, collision has occurred. Then, if collision occurs, the time interval used for the next binary search should be [TL Tm]; otherwise we should set it as [Tm TR].

Finally, it it necessary to consider the precision problem, due to the "float type" calculation involved in the binary search, since otherwise we might get stuck in infinite loop. A general idea is to limit the times of binary search up to some value M. This value M in fact determines the resolution of time. For the first search, we have one single potential point to check, while for the second search we will have two possible points. By some simple induction, we have 2^(M-1) potential points to check at the M-th search. This in fact has generated 2^0+2^1+...+2^(M-1)=2^M-1 points and they satisfy a uniform distribution. In other words, for a given time interval [0 T], it has been discretized into about 2^M sub-intervals with the same length T/2^M (approximately), and the resolution is 1/2^M. To achieve the requested precision 10^(-9), as 10^(-9)=1/10^9>1/16^9=1/2^36, it is thus sufficient to use binary search for only 36 times.