Autors have proposed different solutions. One can notice that if semiknights did not have a meeting after first step (it is not necessary they have a meeting in "good" square), they will not meet at all. This fact appears from board size and possible semiknight's moves. As the initial semiknight's squares are considered good for the meeting the semiknights have arrived to the one square and then they move together to one of the initial squares and meeting will count.
One has to note that the number of dirty stairs ≤ 3000. Petya can reach stair number n if the first and the last stairs are not dirty and there are not three or more dirty stairs in a row. So let sort the array of dirty stairs and go through it, checking for three or more consecutive dirty stairs. Also one need to check if the first or the last stair is in this array.
The number of times swap is called equals the number of inversions in the input permutation. It’s easy to see that it is reasonable to swap only such elements ai, aj that i < j and ai > aj (otherwise the number of inversions will increase). Let di, j be the number of permutation of elements with indices from 0 to i inclusive which are strictly less than j. Then, after swapping elements with indices i and j, the number of inversions will be old - 2 * (di, ai + dj, aj - di, aj - dj, ai) - 1, where old is the number of inversions in the initial permutation. It is sufficient to search all pairs of elements and pick those which help to minimize the number of inversions. The reader may prove the correctness of the formula as a supplementary task.
362D - Fools and Foolproof Roads
If the given graph contains less than q connectivity components, then there’s no solution. Otherwise it’s optimal at first add edges that connect different components and afterwards all remaining edges (they will be connect edges from one component). For the first phase you can use greedy algorithm: each time you select two components, current weight of which is minimal, and connect them with an edge. For example, you can store weights of all components in the current graph in some data structure (like set in С++). For the second phase it’s enough to find any component that contains two or more vertices (because loops are forbidden) and add all remaining edges between some two vertices of this component. If some action cannot be successfully executed (for example, you added all the edges and number of connectivity components if greater than q), then there’s no solution.
Asymptotics — O(n + m + plogn).
Construct the following flow network. Water tank 1 is the source, water tank n is the sink. Every pipe from water tank u to water tank v is presented as two arcs — the first one with capacity cuv and cost 0 and the second one with infinite capacity and cost 1. Thus, the answer is the maximum flow with cost not greater than k. It can be found by standard augmenting paths algorithm.
UPD1. Tutorial for problems A and B added. UPD2. Tutorial for problem C added.
