In one move, Milica can replace the whole string with $$$\texttt{AA} \ldots \texttt{A}$$$. In her second move, she can replace a prefix of length $$$k$$$ with $$$\texttt{BB} \ldots \texttt{B}$$$. The process takes no more than $$$2$$$ operations. The question remains — when can we do better?

In the hint section, we showed that the minimum number of operations is $$$0$$$, $$$1$$$, or $$$2$$$. We have $$$3$$$ cases:

1. No operations are needed if $$$s$$$ already contains $$$k$$$ characters $$$\texttt{B}$$$.

2. Else, we can use brute force to check if changing some prefix leads to $$$s$$$ having $$$k$$$ $$$\texttt{B}$$$s. If we find such a prefix, we print it as the answer, and use only one operation. There are $$$O(n)$$$ possibilities. Implementing them takes $$$O(n)$$$ or $$$O(n^2)$$$ time.

3. Else, we use the two operations described in the hint section.

A fun fact is that only one operation is enough. Can you prove it?

Try a greedy approach. That is, split each $$$a_i$$$ only as many times as necessary (and try to create almost equal parts).

We will iterate over the array from right to left. Then, as described in the hint section, we will split the current $$$a_i$$$ and create almost equal parts. For example, $$$5$$$ split into three parts forms the subarray $$$[1,2,2]$$$. Splitting $$$8$$$ into four parts forms the subarray $$$[2,2,2,2]$$$. Notice that the subarrays must be sorted. Because we want to perform as few splits as possible, the rightmost endpoint value should be as high as possible (as long as it is lower than or equal to the leftmost endpoint of the splitting of $$$a_{i+1}$$$ if it exists).

When we iterate over the array, it is enough to set the current $$$a_i$$$ to the leftmost endpoint of the splitting (the smallest current value). It will help to calculate the optimal splitting of $$$a_{i-1}$$$. For the current $$$a_i$$$, we want to find the least $$$k$$$ such that we can split $$$a_{i-1}$$$ into $$$k$$$ parts so the rightmost endpoint is less than or equal to $$$a_i$$$. More formally, we want $$$\lceil \frac{a_{i-1}}{k} \rceil \leq a_i$$$ to hold. Afterwards, we set $$$a_{i-1}$$$ to $$$\lfloor \frac{a_{i-1}}{k} \rfloor$$$ and continue with our algorithm. The simplest way to find the desired $$$k$$$ is to apply the following formula:

The answer is the sum over all $$$k-1$$$.

There are $$$q \leq 2\cdot 10^5$$$ queries: given an index $$$i$$$ and an integer $$$x>1$$$, set $$$a_i := \lceil \frac{a_i}{x} \rceil$$$. Modify the array and print the answer to the original problem. Please note that the queries stack.

The solution does not exist only for "small" $$$k$$$ or when $$$n+m-k$$$ is an odd integer. Try to find a construction otherwise.

Read the hint for the condition of the solution's existence. We present a single construction that solves the problem for each valid $$$k$$$.

One can verify that the pattern holds in general.

How would you write a checker? That is, how would you check that a valid walk of length $$$k+1$$$ exists in the given grid (with all the edges colored beforehand)?

If $$$a_i > b_i$$$, swap them. Imagine the pairs $$$(a_i,b_i)$$$ as intervals. How can we visualize the problem?

The pair $$$(a_i,b_i)$$$ represents some interval, and $$$|a_i - b_i|$$$ is its length. Let us try to maximize the sum of the intervals' lengths. We present three cases of what a swap does to two arbitrary intervals.

Notice how the sum of the lengths increases only in the first case. We want the distance between the first interval's right endpoint and the second interval's left endpoint to be as large as possible. So we choose integers $$$i$$$ and $$$j$$$ such that $$$i \neq j$$$ and $$$a_j - b_i$$$ is maximized. We add twice the value, if it is positive, to the original absolute beauty. If the value is $$$0$$$ or negative, we simply do nothing.

To quickly find the maximum of $$$a_j - b_i$$$ over all $$$i$$$ and $$$j$$$, we find the maximum of $$$a_1,a_2,\ldots a_n$$$ and the minimum of $$$b_1,b_2, \ldots b_n$$$. Subtracting the two extremum values produces the desired result.

How to handle point updates? (change a single value in either $$$a$$$ or $$$b$$$, and print the answer after each query.)

Notice how sorting only the substrings of length $$$2$$$ is enough. Try a greedy approach.

We sort only the substrings of length $$$2$$$. We can swap two adjacent characters if the first is greater than or equal to the second. Let us fix some character $$$s_i$$$ and presume we want to change its position to $$$j$$$. We have to perform the described swaps if they are possible. More formally:

• if $$$j<i$$$, then every character in the segment $$$s_j s_{j+1} \ldots s_{i-1}$$$ must be greater than or equal to $$$s_i$$$;
• if $$$i<j$$$, then every character in the segment $$$s_{i+1} s_{i+2} \ldots s_j$$$ must be smaller than or equal to $$$s_i$$$.

We want to reorder the string $$$s$$$ and get the string $$$s'$$$. Then, we check if we can delete some characters in $$$s'$$$ to achieve $$$t$$$. In other words, we want $$$t$$$ to be a subsequence of $$$s'$$$. A general algorithm that checks if the string $$$a$$$ is a subsequence of the string $$$b$$$ is as follows. We iterate through $$$a$$$, and for each character, we find its first next appearance in $$$b$$$. If such a character does not exist, we conclude that $$$a$$$ is not a subsequence of $$$b$$$. If we complete the iteration gracefully, then $$$a$$$ is a subsequence of $$$b$$$. We will try to check if $$$t$$$ is a subsequence of $$$s$$$, but we allow ourselves to modify $$$s$$$ along the way.

We maintain $$$26$$$ queues for positions of each lowercase English letter in the string $$$s$$$. We iterate through the string $$$t$$$, and for every character $$$t_i$$$, we try to move the first available equivalent character in $$$s$$$ to position $$$i$$$. In other words, at every moment, the prefix of string $$$s$$$ is equal to the prefix of string $$$t$$$ (if possible). For the current character $$$t_i$$$ and the corresponding $$$s_j$$$, prefixes $$$t_1t_2\dots t_{i-1}$$$ and $$$s_1s_2\dots s_{i-1}$$$ are the same, which means that $$$j\geq i$$$. To move $$$s_j$$$ to position $$$i$$$, we need to delete all characters between $$$s_i$$$ and $$$s_j$$$ that are smaller than $$$s_j$$$. We will delete them and all characters from the current prefix $$$s_1s_2\dots s_{i-1}$$$ from the queues because they are no longer candidates for $$$s_j$$$. By doing so, $$$s_j$$$ will be the first character in the corresponding queue. If at some moment in our greedy algorithm, the queue we are looking for becomes empty, then the answer is "NO". Otherwise, we will make the prefix $$$s_1s_2\dots s_m$$$ equal to the $$$t$$$ and delete the remaining characters from $$$s$$$.

Why is this greedy approach optimal? Let's suppose for some character $$$t_{i_1}$$$ we chose $$$s_{j_1}$$$ and for $$$t_{i_2}$$$ we chose $$$s_{j_2}$$$, such that $$$i_1< i_2$$$, $$$j_1>j_2$$$ and $$$t_{i_1}=t_{i_2}=s_{j_1}=s_{j_2}$$$. We need to prove that if we can move $$$s_{j_1}$$$ to position $$$i_1$$$ and $$$t_{i_2}$$$ to position $$$i_2$$$, when we can move $$$s_{j_2}$$$ to $$$i_1$$$ and $$$s_{j_1}$$$ to $$$i_2$$$. In the moment when we chose $$$s_{j_1}$$$, prefixes $$$t_1t_2\dots t_{i_1-1}$$$ and $$$s_1s_2\dots s_{i_1-1}$$$ are the same, so $$$j_1\geq i_1$$$. Similarly, $$$j_2\geq i_2$$$, which means the only possibility is $$$i_1<i_2\leq j_2<j_1$$$.

If we can move $$$s_{j_1}$$$ to position $$$i_1$$$, than we can also move $$$s_{j_2}$$$ to $$$i_1$$$ because $$$s_{j_1}=s_{j_2}$$$ and $$$j_2<j_1$$$. Also, if we can move $$$s_{j_1}$$$ to $$$i_1$$$, than we can move $$$s_{j_1}$$$ to $$$i_2$$$ because $$$i_1<i_2$$$, from which it follows that we can move $$$s_{j_2}$$$ to $$$i_2$$$, because $$$s_{j_2}=s_{j_1}$$$ and $$$j_2<j_1$$$.

The overall complexity is $$$O(\alpha \cdot (n+m))$$$, where $$$\alpha$$$ is the alphabet size ($$$\alpha=26$$$ in this problem).

Solve the problem when the size of the alphabet is arbitrary (up to $$$n$$$).

To solve the problem for matrices of $$$3$$$-rd type, find the shortest path to $$$2$$$ closest exits with a modification of BFS. Block all cells not belonging to the path with obstacles.

For a matrix of type $$$1$$$, Misha can block all empty cells (except the one Vova stands on).

For a matrix of type $$$2$$$, Misha finds the shortest path to some exit with a single BFS and then blocks every other cell.

Matrices of type $$$3$$$ are more complicated. We want to find two shortest paths to the two closest exits and block the remaining empty cells.

But, notice how the paths will likely share their beginnings. We do not have to count those cells twice. Let's take a look at the junction where the two paths merge. If we first fix the junction, finding the shortest path to Vova can be done by running a single BFS and precalculating the shortest distances from each cell to Vova. Finding the shortest path from the junction to the two closest exits can also be done with BFS and precalculation. We modify the BFS, making it multi-source, with a source in each exit. Also, we will allow each cell to be visited twice (but by different exits). We will need to maintain the following data for each cell:

• How many times was it visited;
• The last exit/source that visited it;
• The sum of paths from all exits/sources that visited the cell so far.

Running the BFS with proper implementation produces the answer. When everything said is precalculated, we fix the junction in $$$O(nm)$$$ ways (each empty cell can be a valid junction), and then calculate the shortest path from Vova to the two closest cells in $$$O(1)$$$ per junction.

Total complexity is $$$O(nm)$$$.

Solve the problem with LCA, or report that such a solution does not exist.

What happens when $$$\texttt{L}$$$ appears after some $$$\texttt{R}$$$ in the string?

Suppose that there exists an index $$$i$$$ such that $$$s_i = \texttt{R}$$$ and $$$s_{i+1} = \texttt{L}$$$. Lamp $$$i$$$ illuminates trophies $$$i+1,i+2,\ldots n$$$ and lamp $$$i+1$$$ illuminates $$$1,2,\ldots i$$$. We can conclude that all trophies are illuminated if $$$\texttt{L}$$$ appears right after some $$$\texttt{R}$$$. So, strings $$$\texttt{LLRRLL}, \texttt{LRLRLR}, \texttt{RRRLLL}, \ldots$$$ do not require any operations to be performed on them, since they represent configurations of lamps in which all trophies are already illuminated.

Now, we consider the case when such $$$i$$$ does not exist and think about how we can use the operation once. Notice that if $$$\texttt{R}$$$ appears right after some $$$\texttt{L}$$$, an operation can be used to transform $$$\texttt{LR}$$$ into $$$\texttt{RL}$$$, and we have concluded before that all trophies are illuminated in that case. So, if $$$\texttt{LR}$$$ appears in the string, we perform the operation on it.

An edge case is when $$$\texttt{L}$$$ and $$$\texttt{R}$$$ are never adjacent (neither $$$\texttt{LR}$$$ nor $$$\texttt{RL}$$$ appears). Notice that $$$s_i = s_{i+1}$$$ must hold for $$$i=1,2,\ldots n-1$$$ in that case, meaning that $$$\texttt{LL} \ldots \texttt{L}$$$ and $$$\texttt{RR} \ldots \texttt{R}$$$ are the only impossible strings for which the answer is $$$-1$$$.

Solve the task in which $$$q \leq 10^5$$$ range queries are given: for each segment $$$[l,r]$$$ print the required index $$$l \leq i < r$$$, $$$0$$$ or $$$-1$$$.

There always exists an answer for even $$$n$$$. Can you find it?

There always exists an answer for odd $$$n \geq 5$$$. Can you find it?

If $$$n$$$ is even, the array $$$[-1,1,-1,1, \ldots ,-1,1]$$$ is a solution. The sum of any two adjacent elements is $$$0$$$, as well as the sum of the whole array.

Suppose that $$$n$$$ is odd now. Since $$$s_{i-1} + s_i$$$ and $$$s_i + s_{i+1}$$$ are both equal to the sum of the whole array for each $$$i=2,3,\ldots n-1$$$, it must also hold that $$$s_{i-1} + s_i = s_i + s_{i+1}$$$, which is equivalent to $$$s_{i-1} = s_{i+1}$$$. Let's fix $$$s_1 = a$$$ and $$$s_2 = b$$$. The condition above produces the array $$$s = [a,b,a,b, \ldots a,b,a]$$$ (remember that we consider an odd $$$n$$$).

Let $$$k$$$ be a positive integer such that $$$n = 2k+1$$$. The sum of any two adjacent elements is $$$a+b$$$ and the sum of the whole array is $$$(k+1)a + kb$$$. Since the two values are equal, we can conclude that $$$ka + (k-1)b = 0$$$. $$$a=k-1$$$ and $$$b=-k$$$ produces an answer. But, we must be careful with $$$a=0$$$ and $$$b=0$$$ since that is not allowed. If $$$k=1$$$ then $$$ka+(k-1)b=0$$$ implies $$$ka=0$$$ and $$$a=0$$$, so for $$$n=2\cdot 1 + 1 = 3$$$ an answer does not exist. Otherwise, one can see that $$$a=k-1$$$ and $$$b=-k$$$ will be non-zero, which produces a valid answer. So, the array $$$[k-1, -k, k-1, -k, \ldots, k-1, -k, k-1]$$$ is an answer for $$$k \geq 2$$$ ($$$n \geq 5$$$).

Solve a generalized task with given $$$m$$$ — find an array $$$a_1,a_2, \ldots a_n$$$ ($$$a_i \neq 0$$$) such that $$$a_i + a_{i+1} + \ldots a_{i+m-1}$$$ is equal to the sum of the whole array for each $$$i=1,2,\ldots n-m+1$$$ (or determine that it is impossible to find such array).

Try a greedy approach.

What data structure supports inserting an element, finding the maximum and erasing the maximum? That is right, a binary heap, or STL priority_queue.

Let $$$p_i = a_1 + a_2 + \ldots a_i$$$ and suppose that $$$p_x < p_m$$$ for some $$$x < m$$$. Let $$$x$$$ be the greatest such integer. Performing an operation to any element in the segment $$$[1,x]$$$ does nothing since $$$p_m - p_x$$$ stays the same. Similarly, performing an operation to any element in segment $$$[m+1,n]$$$ does not affect it.

A greedy idea is to choose the maximal element in segment $$$[x+1,m]$$$ and perform an operation on it, because it decreases $$$p_m$$$ as much as possible. Repeat this process until $$$p_m$$$ eventually becomes less than or equal to $$$p_x$$$. It might happen that a new $$$p_y$$$ such that $$$p_y < p_m$$$ and $$$y<x$$$ emerges. In that case, simply repeat the algorithm until $$$p_m$$$ is less than or equal to any prefix sum in its "left".

Suppose that $$$p_x < p_m$$$ and $$$x > m$$$ now. The idea is the same, choose a minimal element in segment $$$[m+1,x]$$$ and perform an operation on it as it increases $$$p_x$$$ as much as possible. And repeat the algorithm as long as such $$$x$$$ exists.

To implement this, solve the two cases independently. Let's describe the first case as the second one is analogous. Iterate over $$$i$$$ from $$$m$$$ to $$$1$$$ and maintain a priority queue. If $$$p_i < p_m$$$, pop the queue (possibly multiple times) and decrease $$$p_m$$$ accordingly (we simulate performing the "optimal" operations). Notice that one does not have to update any element other than $$$p_m$$$. Add $$$a_i$$$ to the priority queue afterwards.

The time complexity is $$$O(n \log n)$$$.

Solve the task for each $$$m=1,2,\ldots, n$$$ i.e. print $$$n$$$ integers: the minimum number of operations required to make $$$a_1 + a_2 + \ldots a_m$$$ a least prefix sum for each $$$m$$$ (the tasks are independent).

If $$$a_i < b_i$$$ for some $$$i$$$, then an answer does not exist since a cut cannot make a hair taller.

If you choose to perform a cut on some segment $$$[l,r]$$$ with a razor of size $$$x$$$, you can "greedily" extend it (decrease $$$l$$$ and increase $$$r$$$) as long as $$$x \geq b_i$$$ for each $$$i$$$ in that segment and still obtain a correct solution.

There exist some data structures (segment tree, dsu, STL maps and sets, $$$\ldots$$$) ideas, but there is also a simple solution with a STL stack.

Consider $$$a_n$$$ and $$$b_n$$$. If $$$b_n$$$ is greater, the answer is NO since it is an impossible case (see "Stupid Hint" section). If $$$a_n$$$ is greater, then a cut on range $$$[l,n]$$$ with a razor of size $$$b_n$$$ has to be performed. Additionally, $$$l$$$ should be as small as possible (see "Hint" section). For each $$$i$$$ in the range, if $$$a_i$$$ becomes exactly equal to $$$b_i$$$, we consider the position $$$i$$$ satisfied. If $$$a_n$$$ and $$$b_n$$$ are equal, then we simply pop both arrays' ends (we ignore those values as they are already satisfied) and we continue our algorithm.

Onto the implementation. We keep track (and count) of each razor size we must use. This can simply be done by putting the corresponding sizes into some container (array or vector) and checking at the end whether it is a subset of $$$x_1,x_2,\ldots x_m$$$ (the input array of allowed razors). To do this, one can use sorting or maps. This part works in $$$O(n \log n + m \log m)$$$ time.

Implementing cuts is more challenging, though. To do this, we keep a monotone stack which represents all cuts which are valid until "now" (more formally, all cuts with their $$$l$$$ being $$$\leq i$$$, and the value of $$$l$$$ will be determined later). The top of the stack will represent the smallest razor, and the size of razors does not decrease as we pop it. So, we pop the stack as long as the top is smaller than $$$b_n$$$ (since performing an operation which makes $$$a_i$$$ less than $$$b_i$$$ is not valid). After this, if the new top is exactly equal to $$$b_n$$$ we can conclude that we have satisfied $$$a_n = b_n$$$ with some previous cut and we simply continue our algorithm. Otherwise, we add $$$b_n$$$ to the stack as a cut must be performed. This part works in $$$O(n + m)$$$ time.

Total complexity is $$$O(n \log n + m \log m)$$$ because of sorting/mapping.

Solve the task in $$$O(n+m)$$$ total complexity.

A tournament graph is given. Player $$$i$$$ is a candidate master if for every other player there exists a path from $$$i$$$ to them. Can you find one candidate master? (which helps in finding all of them)

Statement: If player $$$i$$$ has the highest out-degree, then they are a candidate master.

Proof: Let's prove a stronger claim, if player $$$i$$$ has the highest out degree, then they reach every other player in $$$1$$$ or $$$2$$$ edges. Let $$$S_1$$$ be the set of players which are immediately reachable and let $$$S_2$$$ be the set of other players (not including $$$i$$$). Choose some $$$x \in S_2$$$. If $$$x$$$ is not reachable from $$$i$$$, then it has an edge to it as well as to every player in $$$S_1$$$, meaning that the out-degree of $$$x$$$ is at least $$$|S_1|+1$$$. This is a contradiction, since $$$i$$$ has out-degree exactly equal to $$$|S_1|$$$ and the initial condition was for $$$i$$$ to have the highest out-degree. So, every $$$x \in S_2$$$ is reachable by $$$i$$$, which proves the lemma.

Statement: There exists an integer $$$w$$$ such that player $$$i$$$ is a candidate master if and only if its out-degree is greater than or equal to $$$w$$$.

Proof: Let $$$S_1, S_2, \ldots S_k$$$ represent the strongly connected components (SCC) of the tournament graph, in the topological order ($$$S_1$$$ is the "highest" component, while $$$S_k$$$ is the "lowest"). Since the graph is a tournament, it holds that there exists a directed edge from $$$x$$$ to $$$y$$$ for each $$$x \in S_i$$$, $$$y \in S_j$$$, $$$i<j$$$. We can also conclude that $$$x$$$ has a higher out-degree than $$$y$$$ for each $$$x \in S_i$$$, $$$y \in S_j$$$, $$$i<j$$$. The same holds for $$$i=1$$$, which proves the lemma since $$$S_1$$$ is the set of candidate masters, and also each player in it has strictly higher out-degree than every other player not in it.

For each player, we host a simul which includes every other player (but themselves). This tells us the necessary out-degrees and we can easily find one candidate master (the one with highest out-degree).

The second step is to sort all players by out-degree in non-increasing order and maintain the current $$$w$$$ described in "Lemma 2". Its initial value is the out-degree of player $$$1$$$. As we iterate over players, we host additional simuls: if player $$$i$$$ wins a match against at least one player among $$$1,2, \ldots j$$$ (the set of current candidate masters), then $$$i$$$ is also a candidate master, as well as $$$j+1, j+2, \ldots i-1$$$, we update the set accordingly and eventually decrease $$$w$$$.

The first step requires $$$n$$$ simuls to be hosted, and the same hold for step $$$2$$$. In total, that is $$$2n$$$ simuls (or slightly less, depending on implementation).

Solve the task if $$$n-1$$$ simuls are allowed to be hosted.

If XOR of all stones equals $$$0$$$, then by performing one spell to the root we obtain an answer.

Solve the task for even $$$n$$$.

If $$$n$$$ is even, performing a spell to the root guarantees that all nodes will have the same number of stones, meaning that the total XOR of the tree is $$$0$$$, thus performing the same spell again makes all nodes have $$$0$$$ stones.

Consider even and odd subtrees. What does a spell do to them?

A spell performed to the odd subtree does nothing. It does not change the total XOR, and it also makes performing a spell to some node in its subtree useless as their XORs would be $$$0$$$ anyway. Thus, we are only interested in even subtrees.

Please refer to the hints as steps. Let's finish the casework:

Let nodes $$$u$$$ and $$$v$$$ have even subtrees. And let the spell be performed on $$$u$$$, and then on $$$v$$$ slightly later. Consider the following $$$3$$$ cases:

1. $$$u$$$ is an ancestor of $$$v$$$; performing a spell on $$$v$$$ does not make sense as its subtree's XOR is already $$$0$$$.
2. $$$v$$$ is an ancestor of $$$u$$$; performing a spell on $$$u$$$ does not make sense either as it will be "eaten" by $$$v$$$ later. More formally, let $$$s_u$$$ be the current XOR of $$$u$$$'s subtree. We define $$$s_v$$$ and $$$s_1$$$ analogously. A spell performed on $$$u$$$ sets $$$s_v := s_v \oplus s_u$$$ and $$$s_1 := s_1 \oplus s_u$$$. Later, the spell performed on $$$v$$$ sets $$$s_1 := s_1 \oplus s_v$$$. Notice that the final state of $$$s_1$$$ is the same as if only the spell on $$$v$$$ was performed (since $$$s_u \oplus s_u = 0$$$). This means that the total XOR stays the same independent of whether we perform a spell on $$$u$$$ or not.
3. Neither $$$u$$$ or $$$v$$$ is a parent of the other; this is the only case we are interested in and we will use this as a fact.

We only need to choose some subtrees such that their total XOR is equal to the XOR of the root. Why? Because after applying the spells to them the total XOR becomes $$$0$$$, and that problem has been solved in "Hint 1.1". Of course, each pair of subtrees must satisfy the condition in case $$$3$$$, thus finding the subtrees is possible with dynamic programming and reconstruction. In each node we keep an array of size $$$32$$$ which tells us the possible XOR values obtained by performing spells on nodes in its subtree. Transitions are done for each edge, from child to parent, in similar fashion to the knapsack problem, but with XOR instead of sums.

Time complexity is $$$O(n A^2)$$$ and memory complexity is $$$O(nA)$$$. It is possible to optimize this, but not necessary.

Can you minimize the number of operations?

The number of them is $$$\leq 6$$$ (in an optimal case).

Consider the sides of the big triangle. If they have the same orientation (clockwise or counter-clockwise), $$$0$$$ segments have to be inverted since the village is already biconnected.

If the three sides do not all have the same orientation, inverting some segments is necessary. The following picture represents them (or rather, one case, but every other is analogous).

There are two "major" paths:

• $$$A \rightarrow C$$$
• $$$A \rightarrow B \rightarrow C$$$

Each road has a "beginning" in one of the paths, hence it is possible to reach every intersection from $$$A$$$. Similarly, $$$C$$$ can be reached from every other intersection. The problem is that $$$C$$$ acts as a tap as it cannot reach anything.

To make the village biconnected, we will make it possible for $$$C$$$ to reach $$$A$$$ by inverting the smallest number of road segments. Intuitively, that will work since for every intersection $$$x$$$ there exists a cycle $$$A \rightarrow x \rightarrow C \rightarrow A$$$. A formal proof is given at the end of this section.

The task is to find a shortest path from $$$C$$$ to $$$A$$$, with edges having weights of $$$0$$$ (its direction is already as desired) and $$$1$$$ (that edge has to be inverted). To implement this in $$$O(n)$$$, one has to notice that we are only interested in the closest road of each direction to the big triangle's side. One can prove that by geometrically looking at the strongly connected components, and maybe some casework is required. But, the implementation is free of boring casework.

Now, it is possible to build a graph with vertices which belong to at least one of the $$$6$$$ roads we take into consideration (there are $$$3$$$ pairs of opposite directions). One can run a $$$0$$$-$$$1$$$ BFS and obtain the shortest path.

This will indeed make the village biconnected as a shortest path does not actually pass through sides $$$A \rightarrow B$$$ and $$$B \rightarrow C$$$ (why would it? it is not optimal making effort to reach it just to invert some unnecessary additional road segments) The shortest path from $$$C$$$ to $$$A$$$ intersects the side $$$A \rightarrow C$$$ though (possibly multiple times), but it can be proved that every intersection on it is reachable from $$$C$$$. Also, sides $$$A \rightarrow B$$$ and $$$B \rightarrow C$$$ are reachable from $$$C$$$ since $$$A$$$ is reachable from $$$C$$$. This means that all sides are reachable by both $$$A$$$ and $$$C$$$, and so is every other intersection.

Solve the problem if it is required to process $$$q \leq 10^5$$$ queries: invert a given road (and every segment in it), then print the minimum number of road segments you need to additionally invert to make the village biconnected (and not perform them, they are independent from the queries).

Try reversing the process.

Start with some multiset $$${ x }$$$ containing only $$$1$$$ element. We will try to make $$$x$$$ an absolute winner. Extend it by repeatedly adding subsets of equal sizes to it (which have sum less than or equal to the current one).

A simple greedy solution is to always extend the current subset with the one which has the maximum sum. This, however, gives WA as 100 100 101 98 89 103 103 104 111 680 1 1 1 1 1 2 is a counter-example. (see it for yourself!)

Statement: If it is possible to extend some multiset $$$A$$$ to the whole array $$$s$$$, we consider it winning. If $$$A \leq B$$$ holds for some subset $$$B$$$, then $$$B$$$ is also winning. Here, $$$A \leq B$$$ means that there exists a bijection $$$f\colon A\to B$$$ such that $$$x \leq f(x)$$$ for each $$$x \in A$$$.

Proof: Let $$$A, A_1, A_2, \ldots A_k$$$ be a winning sequence of extensions. By definition of $$$A \leq B$$$, we can swap each element of $$$A$$$ with some other element. There are three cases:

1. If we swap some $$$x \in A$$$ with an element which is already in $$$A$$$, nothing happens.
2. If we swap some $$$x \in A$$$ with an element which is not in any $$$A_i$$$, the sum of $$$A$$$ increases hence it is also winning.
3. If we swap some $$$x \in A$$$ with an element which is contained in some $$$A_i$$$, the sum of $$$A$$$ increases, the sum of $$$A_i$$$ decreases and the sum of sums of $$$A,A_1, \ldots, A_i$$$ stays the same. The sequence remains winning.

Special cases of the lemma are subsets of size $$$1$$$. We can conclude that if $$$x$$$ is winning and $$$x \leq y$$$, then so is $$$y$$$. The answer is binary-searchable. Let's work with some fixed $$$s_i = x$$$ from now on. The idea is to maintain a list of current possible winning subsets. The motivation of lemma is to exclude subsets which cannot produce the answer.

1. we can see that $$${ s_j, s_i } \leq { s_{i-1},s_i }$$$ for each $$$j < i-1$$$, hence the only interesting subset is $$${ s_{i-1}, s_i }$$$ (we excluded others because if one of them is an answer, then so is $$${ s_{i-1}, s_i }$$$. We will use this without explanation later on).

2. we extend $$${ s_{i-1}, s_{i} }$$$ further to a subset of size $$$4$$$. There will be at most $$$15$$$ new subsets and it can be proved by using the lemma and two pointers.

3. extend the current subsets to have size $$$8$$$. And, of course, use the lemma again and exclude unnecessary subsets. Implementing it properly should be fast enough. A fact is that there will be at most $$$8000$$$ subsets we have to consider. Although, proving it is not trivial. Consider all subsets of size $$$4$$$ and a partial ordering of them. In our algorithm we have excluded all subsets with large sum and then we excluded all subsets which are less than some other included set. So, the max collection of such subsets is less in size than the max antichain of $$$4$$$-subsets with respect to $$$\leq$$$. Following the theory, a max anti-chain can have size at most $$$\max\limits_{k} f(k)$$$, where $$$f(k)$$$ is the number of $$$4$$$-subsets with indices having sum exactly $$$k$$$. Hard-coding this gives us an approximation of $$$519$$$. This value should be multiplied by $$$15$$$, since we had that many $$$4$$$-subsets to begin with. This is less than $$$8000$$$, which is relatively small.

4. Extending the $$$8$$$-subsets further sounds like an impossible task. But, greedy finally comes in handy. Every $$$8$$$-subset should be extended with another $$$8$$$-subset which maximizes the sum. It is not hard to see that if an answer exists, then this produces a correct answer too. We are left with solving $$$8$$$-sum in an array of size $$$24$$$. As we need to do this around $$$8000$$$ times, we use the meet in the middle approach. It can be done in around $$$2^{12}$$$ operations if merge sort is used (it spares us the "$$$12$$$" factor in $$$12 \cdot 2^{12}$$$).

Summary: Solving the task for $$$n\leq 16$$$ is trivial. Let's fix $$$n=32$$$. Calculating the exact complexity does not make much sense as $$$n$$$ is fixed, but we will calculate the rough number of basic arithmetic operations used. Firstly, a binary search is used, which is $$$\log 32 = 5$$$ operations. Then, we generate $$$8$$$-subsets which can be implemented quickly (but is not trivial). The meet in the middle part consumes $$$8000 \cdot 2^{12}$$$ operations. The total number of operations is roughly $$$5 \cdot 8000 \cdot 4096 = 163\,840\,000$$$, which gives us a decent upper bound.

Try to construct a strong test against fake greedy solutions :)

Greedily take the smallest character in both strings. What's the exception to this?

We can't take the smallest character in both strings when we've already took $$$k$$$ elements from the string we chose. Denote $$$A$$$ as the number of characters we've took from string $$$a$$$ in the last few consecutive moves and denote $$$B$$$ the same for $$$b$$$. If $$$A=k$$$, then we have to take the smallest character in string $$$b$$$ instead of possibly $$$a$$$. If $$$B=k$$$, then we have to take the smallest character in string $$$a$$$ instead of possibly $$$b$$$.

Remember to reset $$$A$$$ to $$$0$$$ when you take a character from $$$b$$$. Similarly, reset $$$B$$$ to $$$0$$$ when you take a character from $$$a$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
 
    int t; cin>>t;
    while (t--)
    {
        int n,m,k; cin>>n>>m>>k;
        string a,b,c; cin>>a>>b;
        sort(a.begin(),a.end(),greater<char>());
        sort(b.begin(),b.end(),greater<char>());
 
        int ak=0,bk=0;
        while (!a.empty() && !b.empty())
        {
            bool gde=b.back()<a.back();
            if (gde && bk==k) gde=0;
            if (!gde && ak==k) gde=1;
 
            if (gde) c.push_back(b.back()),bk++,ak=0,b.pop_back();
            else c.push_back(a.back()),ak++,bk=0,a.pop_back();
        }
 
        cout<<c<<"\n";
    }
}

When is it impossible to find such permutation?

It is impossible only for $$$n=1$$$. In every other case, iterate over each position in order from $$$1$$$ to $$$n$$$ and take the smallest available number. What's the exception to this?

The exception is the last two elements. We can always take the smallest available number for each $$$q_i$$$ satisfying $$$i<n-1$$$. To do this we maintain an array of bools of already taken numbers, and then iterate over it to find the smallest available number satisfying $$$p_i\neq q_i$$$ which is also not checked in the array, and then check it (we took it).

Now consider $$$(p_{n-1},p_{n})$$$ and we want $$$(q_{n-1},q_{n})$$$ to be lexicographically minimal while satisfying $$$p_{n-1}\neq q_{n-1}$$$ and $$$p_{n}\neq q_{n}$$$. Let $$$a$$$ and $$$b$$$ be the last two unused numbers in the array of bools with $$$a<b$$$. We try to take $$$(q_{n-1},q_{n}) = (a,b)$$$. If $$$a=p_{n-1}$$$ or $$$b=p_{n}$$$, then we take $$$(q_{n-1},q_{n}) = (b,a)$$$. If $$$(a,b)$$$ isn't valid, then $$$(b,a)$$$ is. The proof is left as an exercise to the reader.

This solution runs in $$$O(n^2)$$$ and can be optimized to $$$O(n \ log \ n)$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
bool took[1005];
int p[1005];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
 
    int t; cin>>t;
    while (t--)
    {
        int n; cin>>n;
        for (int i=1;i<=n;i++) cin>>p[i];
        for (int i=1;i<=n;i++) took[i]=0;
        
        if (n==1)
        {
            cout<<"-1\n";
            continue;
        }
 
        for (int i=1;i<=n-2;i++)
        {
            int k=1;
            while (took[k] || k==p[i]) ++k;
            cout<<k<<" "; took[k]=1;
        }
 
        int a=-1,b=-1;
        for (int i=1;i<=n;i++) if (!took[i])
        {
            if (a==-1) a=i;
            else b=i;
        }
 
        if (a!=p[n-1] && b!=p[n]) cout<<a<<" "<<b<<"\n";
        else cout<<b<<" "<<a<<"\n";
    }
}

#include <bits/stdc++.h>

using namespace std;

int t,n,A[1010],B[1010];

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&A[i]);
            B[i] = i;
        }
        if(n==1)
        {
            printf("-1\n");
            continue;
        }
        for(int i=1; i<n; i++)
        {
            if(A[i]==B[i]) swap(B[i],B[i+1]);
        }
        if(A[n]==B[n]) swap(B[n-1],B[n]);
        for(int i=1; i<=n; i++) printf("%d ",B[i]);
        printf("\n");
    }
    return 0;
}

We always delete a vertex directly connected to an infected one.

Use dp.

Let $$$u_1,u_2,...,u_k$$$ be the sequence of removed vertices such that the infection cannot spread anymore. If vertex $$$u_i$$$ was never directly connected to an infected vertex, then we could have deleted its parent instead of $$$u_i$$$ and we would have got a better solution. Hence, we may assume we always delete a vertex directly connected to an infected one.

Now, we may use some dynamic programming ideas. Let $$$dp_i$$$ be the maximum number of vertices we can save in the subtree of vertex $$$i$$$ if that vertex is infected and we use operations only in the subtree. We can assume the second as the tree is binary and we have two choices — save the subtree of one child by deleting it and infect the other, or the other way around. In each case, the infection will be "active" in at most one subtree of some vertex.

If $$$c_1$$$ and $$$c_2$$$ are the children of vertex $$$i$$$, the transition is

where $$$s_i$$$ denotes the number of vertices in the subtree of $$$i$$$.

The answer to the problem is $$$dp_1$$$. Complexity is $$$O(n)$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
vector<vector<int>> g(300005);
int ch[300005],dp[300005];
 
void dfs(int p, int q)
{
    ch[p]=1,dp[p]=0; int s=0;
    for (auto it : g[p]) if (it!=q)
    {
        dfs(it,p); s+=dp[it];
        ch[p]+=ch[it];
    }
    for (auto it : g[p]) if (it!=q)
    {
        dp[p]=max(dp[p],s-dp[it]+ch[it]-1);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
 
    int t; cin>>t;
    while (t--)
    {
        int n; cin>>n;
        for (int i=1;i<=n;i++) g[i].clear();
        for (int i=1;i<n;i++)
        {
            int u,v; cin>>u>>v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
 
        dfs(1,0);
        cout<<dp[1]<<"\n";
    }
}

There are not a lot of useful black squares.

Consider this algorithm: iterate over all squares in the matrix and find the most distant black square.

Let's find out how to do that efficiently. In fact, only 4 (not necessarily distinct) black squares will be useful: one square which minimizes $$$i-j$$$, one square which maximizes $$$i-j$$$, one square which minimizes $$$i+j$$$ and one square which maximizes $$$i+j$$$, where $$$(i,j)$$$ denotes the black cell's coordinates. In other words, we would like to find the most distant "border".

Let's look at the example above. The cell we choose to recolour to yellow creates four regions (the top-left rectangle, the top-right rectangle, the bottom-left rectangle and the bottom-right rectangle, which are created by two lines parallel with coordinate axes passing through our yellow point). The most distant border will be fully contained inside one region, hence we should find the distance from our yellow cell to any cell on that border, and that is the maximum possible distance.

The complexity is $$$O(n\cdot m)$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
char tab[1003][1003];
pair<int,int> a={-1,-1},b={-1,-1},c={-1,-1},d={-1,-1};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
 
    int t; cin>>t;
    while (t--)
    {
        a={-1,-1},b={-1,-1},c={-1,-1},d={-1,-1};
        
        int n,m; cin>>n>>m;
        for (int i=0;i<n;i++) cin>>tab[i];
 
        vector<pair<int,int>> interesting;
 
        for (int i=0;i<n;i++) for (int j=0;j<m;j++) if (tab[i][j]=='B')
        {
            if (a.first==-1 || i+j>a.first+a.second) a={i,j};
            if (b.first==-1 || i+j<b.first+b.second) b={i,j};
            if (c.first==-1 || i-j>c.first-c.second) c={i,j};
            if (d.first==-1 || i-j<d.first-d.second) d={i,j};
        }
 
        interesting.push_back(a);
        interesting.push_back(b);
        interesting.push_back(c);
        interesting.push_back(d);
 
        int ans=1e9; pair<int,int> opt;
        for (int i=0;i<n;i++) for (int j=0;j<m;j++)
        {
            int dist=0;
            for (auto it : interesting) dist=max(dist,abs(i-it.first)+abs(j-it.second));
            if (dist<ans) ans=dist,opt={i,j};
        }
 
        cout<<opt.first+1<<" "<<opt.second+1<<"\n";
    }
}

Increase every $$$0$$$ by $$$1$$$ initially.

Check if the answer is $$$0$$$: check whether the graph is already connected.

Check if the answer is $$$1$$$.

If the answer is not $$$0$$$ or $$$1$$$, then it is $$$2$$$.

Firslty, let's understand how to check whether the graph induced by some array $$$b$$$ is connected in $$$O(n \ log \ max \ b_i)$$$. We create a graph over bits. Let's take all elements $$$b_i$$$ and add an edge between their adjacent bits (all bits of a single $$$b_i$$$ will be connected). To quickly access the lowest bit we will use $$$b_i \ \& \ -b_i$$$ in code. Now we just check whether the graph over bits is connected.

We check whether the graph for initial array $$$a$$$ is connected. If it is, the answer is 0.

Then, we wonder if the answer is $$$1$$$. Check if at least one of the graphs for arrays $$$a_1,...,a_{i-1},a_i-1,a_{i+1},...,a_n$$$ for every $$$1\leq i \leq n$$$ is connected. Do the same for arrays $$$a_1,...,a_{i-1},a_i+1,a_{i+1},...,a_n$$$. If none of the graphs is connected, the answer is $$$2$$$ and otherwise $$$1$$$.

Now let's see how the answer will be at most $$$2$$$. Let $$$i_1,i_2,...,i_k$$$ be the sequence of indices denoting that $$$a_{i_j}$$$ has the highest lowest bit (the highest value of $$$a_i \ \& \ -a_i$$$). if $$$k=1$$$ then we can just decrease $$$a_{i_1}$$$ by $$$1$$$ and connect everything. If $$$k\geq 2$$$ and we do the same we might disconnect that number from other numbers having the highest lowest bit, thus an additional operation of adding $$$1$$$ to $$$a_{i_2}$$$ is needed to keep everything connected. The answer is $$$2$$$ in this case.

Complexity of this solution is $$$O(n^2 \ log \ max \ a_i)$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
int a[2005];
 
vector<vector<int>> g(32);
bool vis[32];
 
void dfs(int p)
{
    if (vis[p]) return; vis[p]=1;
    for (auto it : g[p]) dfs(it);
}
 
bool connected(int n)
{
    int m=0;
    for (int i=0;i<n;i++) if (a[i]==0) return false;
    for (int i=0;i<n;i++) m|=a[i];
    for (int i=0;i<31;i++) g[i].clear();
    for (int i=0;i<n;i++)
    {
        int last=-1;
        for (int j=0;j<31;j++)
            if (a[i]&(1<<j)){
                if (last!=-1) g[last].push_back(j),g[j].push_back(last);
                last=j;
            }
    }
 
    for (int j=0;j<31;j++) vis[j]=0;
    for (int j=0;j<31;j++) if ((1<<j)&m)
    {
        dfs(j); break;
    }
    for (int j=0;j<31;j++) if (((1<<j)&m) && !vis[j]) return false;
    return true;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
 
    int t; cin>>t;
    while (t--){
 
 
    int n; cin>>n;
    for (int i=0;i<n;i++) cin>>a[i];
 
    int ans=0;
    for (int i=0;i<n;i++) if (a[i]==0) ans++,a[i]++;
 
    int m=0;
    for (int i=0;i<n;i++) m=max(m,(a[i]&(-a[i])));
 
    if (connected(n))
    {
        cout<<ans<<"\n";
        for (int i=0;i<n;i++) cout<<a[i]<<" "; cout<<"\n";
        goto kraj;
    }
 
    for (int i=0;i<n;i++)
    {
        a[i]--;
        if (connected(n))
        {
            cout<<ans+1<<"\n";
            for (int i=0;i<n;i++) cout<<a[i]<<" "; cout<<"\n";
            goto kraj;
        }
        a[i]++;
    }
    
    for (int i=0;i<n;i++)
    {
        a[i]++;
        if (connected(n))
        {
            cout<<ans+1<<"\n";
            for (int i=0;i<n;i++) cout<<a[i]<<" "; cout<<"\n";
            goto kraj;
        }
        a[i]--;
    }
 
    for (int i=0;i<n;i++) if ((a[i]&-a[i])==m)
    {
        a[i]--;
        break;
    }
    for (int i=0;i<n;i++) if ((a[i]&-a[i])==m)
    {
        a[i]++;
        break;
    }
 
    cout<<ans+2<<"\n";
    for (int i=0;i<n;i++) cout<<a[i]<<" ";
    cout<<"\n";
    
    kraj:;
    }
}