Codeforces Round #418 (Div. 2) Editorial

The statement laid emphasis on the constraint that the elements are pairwise distinct. How is this important?

In fact, this implies that if the resulting sequence is increasing, then swapping any two of its elements will result in another sequence which is not increasing.

And we're able to perform a swap on any resulting sequence if and only if k ≥ 2. Thus if k ≥ 2, the answer would always be "Yes". For cases where k = 1, we replace the only zero in sequence a with the only element in b, and check the whole sequence. Hackable solutions include those only checking the replaced element and its neighbours, and those missing the replaced element.

Bonus. Figure out why solution 2 is not hackable.

Permutating directly no longer works here. Let's try to dig something out from the constraints.

Imagine that we take a permutation p1... n, and change one of its elements to a different integer in [1, n], resulting in the sequence p'1... n. There are exactly 2 positions i, j (i ≠ j) such that p'i = p'j, while the other n - 2 elements are kept untouched. This is actually what a and b satisfy.

Find out these two positions in a, and the two candidates for them — that is, the only two numbers not present in the remaining n - 2 elements. Iterate over their two possible orders, and check the validity against sequence b.

Of course you can solve this with casework if you like.

The first thing to notice is that we are only changing other colours to Koyomi's favourite one. Furthermore, we won't create disconnected segments of that colour, for that's no better than painting just around the longest among them.

This leads us to a straightforward approach: when faced with a query (m, c), we check each segment [l, r] and determine whether it's possible to fill this segment with letter c, within at most m replacements. This can be done by finding the number of times c occurs in that segment (denote it by tc), and checking whether (r - l + 1) - t ≤ m. But this O(n2·q) solution would be too slow.

Since the number of different queries is 26n, we can calculate all answers beforehand. For each letter c and a segment [l, r], we'll be able to fill the whole segment with c within (r - l + 1) - tc moves. Use this information to update the answers, and employing a "prefix max" method gives us a time complexity of O(n2·|Σ| + q), where |Σ| equals 26. Refer to the code for a possible implementation.

Bonus. Find out the O(n2  +  n·|Σ|  +  q) solutions and the O(nq) solutions (some of them may get TLE — remember to check against maximum data next time!).

Circles' borders do not intersect, that is, each circle is "directly" contained in another circle, or is among the outermost ones. Can you see a tree/forest structure out of this?

We create a node for each of the circles Ci, with weight equal to its area π ri2. Its parent is the circle which "directly" contains it, namely the one with smallest radius among those circles containing Ci. If a circle is an outermost one, then it's made a root. This tree structure can be found in O(n2) time.

Consider what happens if there's only one group: the spaciousness equals the sum of weights of all nodes whose depths are even, minus the sum of weights of all nodes whose depths are odd.

Now we are to split the original tree/forest into two disjoint groups. This inspires us to think of a DP approach — consider a vertex u, and the parity (oddness/evenness) of number of nodes in its ancestors from the first and the second group. Under this state, let f[u][0 / 1][0 / 1] be the largest achievable answer in u's subtree.

The recursion can be done from bottom to top in O(1), and the answer we need is the sum of f[u][0][0] for all u being roots. Time complexity is O(n2) for the tree part and O(n) for the DP part. See the code for the complete recursion.

Bonus. Build the tree in time.

Bonus. Find different greedy solutions for this problem and try to prove their correctness.

Let's make it intuitive: the graph looks like this.

Formally, if we find out the BFS levels of the graph, it will look like a tree with extra edges among vertices of the same level, and indices of vertices in the same level form a consecutive interval. Therefore we can add vertices from number 1 to number n to the graph, without missing or violating anything.

Consider the case when we want to add vertex u to a graph formed by the first u - 1 vertices. The state only depend on the current and the previous level (We can't start level l + 1 without finishing level l - 1, thus there are only two unfinished levels).

The whole thing is described by four parameters: the number of "1-plug" (having one outgoing edge that is not determined) and "2-plug" (similar definition) vertices in the previous and the current level. Let f[u][p1][p2][c1][c2] be the number of ways to build the graph with the first u vertices, with p1 "1-plug" vertices and p2 "2-plug" vertices in the previous level, and c1 and c2 in the current one respectively.

For vertex u, we must choose one vertex v in the previous layer and connect u to it. For the remaining degree(s) of u, we can choose either to connect them to vertices in the same layer, or simply leave them for future. Also, we may start a new level if p1 = p2 = 0. This gives us an O(1) recursion.

There are O(n5) states, giving us a time complexity of O(n5) and a space complexity of O(n4) if the first dimension is reused. The constant factor can be rather small (since p1 + p2 + c1 + c2 ≤ n). See solution 1 for detailed recursion.

Let's try to improve this a bit. Instead of adding one vertex at a time, we consider the layer as a whole. Let f[c0][c1][c2] be the number of ways to build a single level with c0 vertices (their "plugs" don't matter), and connect it to the previous layer which has c1 "1-plug" vertices and c2 "2-plug" ones. Recursion over f can be done in O(1). Then let g[l][r] be the number of ways to build the graph with vertices from l to n, while vertices from l to r form the first level — note that this level should be connected to another previous one. The recursion over g can be done in O(n). The final answer should be g[2][d1] since the capital must be directly connected to vertices from 2 to d1. The overall time complexity is O(n3). Huge thanks to Nikolay Kalinin (KAN) for this!

Bonus. Figure out the O(n4) solution :P