K: Make a graph with $$$N + K$$$ nodes, where $$$K$$$ nodes correspond to trams, and $$$N$$$ other nodes correspond to stops. The edges are (1) stop to tram, weight 0, if tram are connected to stop, and (2) tram to tram, weight 1, if these two trams share any stop.

Now it should be classic. Instead of removing trams, add them backwards, and do Floyd shortest path with the added tram as the intermediate node.

K: Consider bipartite graph with $$$n+k$$$ nodes. $$$n$$$ nodes on the left are graph nodes, and $$$k$$$ nodes on the right represent the cliques. For every clique node connect it to every node in its list by an edge of weight $$$0.5$$$. Now length of shortest path between any two graph nodes is preserved, so run BFS $$$n$$$ times to compute all pair shortest paths. For every new added clique (perform queries backwards), first compute $$$\text{minDist}[u]$$$ — the shortest distance from $$$u$$$ to any node in the new clique. Then the shortest path between any pair of nodes $$$(u,v)$$$ should be relaxed with $$$\text{minDist}[u] +1+\text{minDist}[v]$$$.

Another solution: increment $$$A$$$ 26 times, and check each one to see if it works.

I also got PE2 on F, but my solution looks very same as MidoriFuse described. I don't understand why PE? https://ideone.com/vWTnO5

We did. Just a nasty stroke of bad luck (mistake in test generator, giving one test case too many + mistake in the validator, not checking EOF + two verifying people missing that as well + nobody used while (read()) solve(); before, so this did not come out earlier). Sorry for that.

Here's my code, which runs in 3.2s. I copy-pasted SAIS from Yosupo judge because mine was too slow ><

https://ideone.com/karLpl is my solution in $$$O(n + K^2)$$$ (it doesn't compile because ideone doesn't have C++17). See my comment below for an explanation. It looks about the same as maroonrk's, and it passed in 2.8s. I used my own SAIS; I think slower suffix arrays might be too slow?

A: Recall the standard DP for edit distance: for a given prefix of $$$A$$$ and a given prefix of $$$B$$$, what's the minimum number of moves to transform the first prefix into the second? Note that one move changes the difference between the lengths of the prefix by at most 1, so we can restrict ourselves to pairs of prefixes with offset at most $$$\pm K$$$. Now, we'll simply swap the values and indices of this DP: for a given number of moves and a given offset, what's the maximum length of prefixes of $$$A$$$ and $$$B$$$ with this offset which can be made using this many moves? The key to the transition in this DP is that after doing an operation, we can greedily jump forwards in $$$A$$$ and in $$$B$$$ by the LCP of the remaining suffix. Thus, we precompute the suffix array (using some fast suffix array code), and then we can do the rest of the DP in $$$O(K^2)$$$.

D: We're given a tournament graph, and we want to flip some edges with minimum total weight to make it a single SCC. First, if $$$N = 1$$$, this is vacuously true, and if $$$N = 2$$$, this is impossible, because the graph is acyclic/too sparse. Otherwise, consider the existing SCC structure; we essentially want to flip some number of edges so that the bottommost SCC can reach the topmost SCC. The minimal set of flipped edges should never flip an edge within an existing SCC, so it must look like some sequence of flips $$$(a_1, b_1), \ldots, (a_k, b_k)$$$ with $$$a_1$$$ is a vertex in the topmost SCC, and $$$b_k$$$ is a vertex in the bottommost SCC, $$$a_i$$$ is above $$$b_i$$$, and $$$a_{i+1}$$$ is in the same SCC or above $$$b_k$$$. This can be made into a DP which should work, but there's an easier simplification: find the shortest path from a vertex in the bottommost SCC (e.g. the one with minimum outdegree) and a vertex in the topmost SCC (e.g. the one with the maximum outdegree) where going from $$$i$$$ to $$$j$$$ costs exactly $$$D_{ij}$$$, i.e. $$$0$$$ if the edges originally exists and $$$D_{ij}$$$ if the edge is a flipped edge. It's easy to see that the flipped edges in this path will be a correct sequence, and that any set of minimal flips can be extended into such a path. Thus, we just run $$$O(V^2)$$$ Dijkstra using the given adjacency matrix and print out all flipped edges along the shortest path.

H: First, note that operations are reversible, so we only need to describe a sequence of operations which move each given set of students into a "canonical position", check if they match, and then output $$$move_1 + reverse(move_2)$$$. There are 2 main ideas to do this.

(1) Consider any vertex $$$v$$$ which is adjacent to at most one non-leaf (e.g. the parent of the deepest leaf). Then, this vertex and its leaves can fit at most one student at any time, and if we put a student into a leaf, it won't block any other useful vertices or paths. Thus, we might as well move a student into a leaf if possible, and then forget about $$$v$$$ and its adjacent leaves. This will be the basis of our canonical form: iterate through the vertices in decreasing depth; if possible, move a student to this vertex and then delete its parent and all siblings, otherwise delete this vertex.

(2) Now, it just remains to identify whether we can move a student into this target vertex. This can be done using just a tree DP. Reroot the tree at the target. The key insight is that, because all students are indistinguishable, if a path is blocked, we might as well just move one of the blocking students to the target. In particular, consider the minimal vertices that are blocked; then, if it is blocked by $$$k$$$ children, we need to move $$$k-1$$$ of them downwards before this vertex is accessible, and then we can move the last one upwards to the target. Furthermore, to move the $$$k-1$$$ downwards, the subtrees are independent because the top vertex is still necessarily blocked. Detecting whether we can move a vertex downwards is once again a simple tree DP on whether your children/grandchildren can move downwards.

Using these primitives, we can build up the canonical form in at most $$$n$$$ moves per vertex, so we will use at most $$$2n^2$$$ moves for the two directions. The runtime is also $$$O(n^2)$$$.

L: First, note that the winding number around $$$(0,0)$$$ cannot change when doing these operations. This is also sufficient. We will also use a "canonical form" and bring both the starting sequence and the target sequence to the canonical form using operations/reversed operations. First, adjust each cycle so it starts at $$$(1,1)$$$ instead of $$$(x_0, y_0)$$$, by prepending a path from $$$(1,1)$$$ to $$$(x_0, y_0)$$$ and appending its inverse. In the forward direction, this is just repeatedly inserting a direction and then '-'; in the reverse direction, you need to repeatedly walk around nearly the entire loop and then use 'R'. Now, we will reduce each cycle to the minimum perimeter cycle starting/ending at $$$(1,1)$$$ (i.e. taking exactly 8 * |winding number| steps to keep circling the origin). To do this, we will find some substring (*not* a cyclic substring) of the form $$$NE^*S$$$ or symmetric and convert it to $$$E^*$$$, provided it doesn't go through the origin. It's easy to convince yourself this is always possible by considering the extremeal points of your path. To do this conversion, walk to the location with '-'s, and in the forwards direction, use "C-C-C-...R" to delete the "N" and "S", and in the reverse direction, use "N-C-C-...C-C--" to insert the "N" and "S", then finish the cycle and walk back to $$$(1,1)$$$ with more '-'s.

In the end, this walks 1 full cycle and uses $$$O(p)$$$ operations to decrease the perimeter by $$$1$$$, and the perimeter is $$$O(n + x_{max} + y_{max})$$$, so it is not too many ops.

Do you mean you got WA on the implementation which used rational numbers with int64? Or that you had WA before switching to it?

OpenCup (opencup.ru) is an ICPC-style contest series, generally used for training by top ICPC teams. ICPC contests don't have problems sorted by difficulty, hence why A is sometimes hard. OpenCup is probably also the most difficult contest in general, it's typically harder than World Finals (maybe some onsites final rounds or AGCs are harder).

Observe that the answer is 100% when n>2. Thus you only need to solve for n=1 and n=2.

If $$$n\geq 3$$$ then it's always possible to cover the whole plane (there are either two parallel lines or a triangle and you can choose appropriate sides from them). So you're left with $$$n\leq 2$$$, in which case you can brute force all possibilities. I couldn't quickly think of an elegant way to do it so I just plugged in a halfplane intersection library (a square is the intersection of four halfplanes).

Is there a quick and elegant way to do the $$$n\leq 2$$$ part?