For all participants. All rated contests in AtCoder will have English statements.

My solution is as follows:

First check, after sorting $$$a$$$ and $$$b$$$, is $$$a_{i}\leq b_{i}$$$ for every $$$i$$$. If not, the answer is impossible.

Note that, after sorting $$$a$$$ and $$$b$$$, if there exists some $$$i \gt j$$$, such that $$$a_{i}\leq b_{j}$$$, then the answer is Yes by simply putting the $$$N-1$$$ indices except $$$i$$$ and $$$j$$$ in place.

So after checking the above cases, we need to arrange $$$a$$$ in a certain permutation, and to sort a permutation, for each cycle of length $$$l$$$ in the permutation, we need at least $$$l-1$$$ swaps. So it suffices to check if the permutation consists a single cycle of length $$$N$$$.

Do this operation at most $$$n-2$$$ times :

for every $$$A[i]$$$, try to swap it with the maximum number $$$ \lt =$$$ $$$B[i]$$$ in the range from $$$i$$$ to $$$n$$$ and lets denote it as $$$x$$$, so if $$$x$$$ equals $$$A[i]$$$ then don't swap the two numbers, else then swap them.

Now, check for every index $$$i$$$ that $$$A[i]$$$ <= $$$B[i]$$$.

my submission

Sort $$$A$$$ and $$$B$$$. If $$$A_i \gt B_i$$$ for some $$$i$$$, the answer is No. Otherwise, if you can swap some two adjacent elements of $$$A$$$ such that the above inequality still holds for all $$$i$$$, the answer is yes [1]. Otherwise, look at the permutation needed to bring $$$A$$$ from its original order to the order where $$$A_i \leq B_i$$$, assuming we didn't change the order of elements in $$$B$$$. The answer is Yes if this permutation has more than one cycle and No otherwise.

Note — the smallest number of swaps needed to sort a permutation is $$$n - c$$$, where $$$c$$$ is the number of cycles in the permutation. In [1], you can choose between some two permutations which differ by exactly one swap, and so they cannot both consist of only one cycle.

Suppose that $$$B_i \leq B_{i+1}$$$ and that we can achieve the required $$$n-1$$$ operations.

If there is $$$x$$$ and $$$y$$$ such that $$$x \neq y$$$, $$$A_x \leq B_1$$$ and $$$A_y \leq B_1$$$ then any pairing between $$$A_x$$$, $$$A_y$$$, $$$B_1$$$ and $$$B_2$$$ is good. Therefore, we can ignore these and pair all the rest of numbers in at most $$$n-2$$$ operations.

If there isn't any $$$x$$$ such that $$$A_x \leq B_1$$$ then obviously answer doesn't exist.

Otherwise there is exactly one such $$$x$$$. If $$$x=1$$$ then we saved one operation and can can pair the rest of numbers in $$$n-1$$$ operations. Otherwise swap $$$A_1$$$ with $$$A_x$$$ and try to solve the smaller problem with $$$n-1$$$ pairs and $$$n-2$$$ operations.

The construction is impossible if

. The above inequality is equivalent to $2K-2>N-1$.

Otherwise, the construction is always possible. For example, if $$$K=4$$$ and $$$N=7$$$, $$$(4, 14), (5, 15), (6, 16), (7, 17), (8, 11), (9, 12), (10, 13)$$$ can be made into construction. That is, divide the numbers between $$$K$$$ and $$$K+2N-1$$$ into "middle half" and "non-middle half" and pair the numbers in ascending order.

I have another solution.

First if k+k>n+1 ,there isn't a construction.

Then just make the construction like this:

(k,2n,k+2n),(k+2,2n-1,k+2n+1),(k+4,2n-2,k+2n+2)....

the rest, just choose the first number in the construction from the left ,the second number in the construction from k+2n-1 to the left (of course they aren't used).

Sort and match them with the rest numbers(bigger than k+2n and aren't used) from small to large.

Think of the tree being constructed from root to the nodes on deeper levels.

You can place any node in the numer of places parent nodes on that level exist.

So, the first node is the root node. All nodes on level 1 must be childs of the root node (on level 0), so there is only one possibiliy to place them.

Every nodes on level 2 can be placed as a child of every node of level 1. So the posibilities are numNodes(level1) * numNodes(level2)

The same is true for all other levels, too, so we need to multiply them.

Really nice problem! I'll give the outline.of the solution.

Firstly, note that by flipping each interior square, we alter the points that lie on two diagonally oriented rectangles (possibly degenerate, i.e. diagonals). There are $$$n+1$$$ such rectangles, and each interior point can be encoded with a pair $$$(a, b)$$$ denoting the rectangles they "flip" (we number the rectangles by their distance of the top vertex from the top left corner of the grid). Notice that $$$a, b$$$ have the same parity and are distinct.

By flipping a point with code $$$(a,b)$$$, we flip the lights where at least one coordinate of their code is $$$a$$$ or $$$b$$$. Consider a graph on the numbers from $$$0$$$ to $$$n$$$ of the same parity. Our operation of flipping a light can be described as choosing two vertices $$$u,v$$$ and flip the edges with at least one endpoint $$$u,v$$$. A configuration of lights is nice iff the lights with the same code are consistent and there exist a sequence if operations to reduce our graph to the empty graph, where we start by drawing an edge between the numbers in the code of on lights.

We claim that if our graph has $$$N$$$ vertices, then the task is always possible if $$$N$$$ is even, and the task is possible for $$$N$$$ is odd iff the degree of each vertex is even. The necessity can be proven simply by considering the parity of the degree of each vertex after each operation.

To prove the sufficiency, firstly note that by performing operations on $$$(a,b),(b,c),(c,a)$$$ where $$$a,b,c$$$ are distinct, then we can flip only these 3 edges. For $$$N$$$ even, flip $$$(u,v)$$$ and then flip $$$(u,v),(v,w),(w,u)$$$ for all other $$$w$$$. This flips exactly one edge $$$(u,v)$$$. For $$$N$$$ odd, we claim that we can always flip an Eulerian cycle. Indeed, we can simply extend the cycle repeatedly by flipping a triangle.

Finally, it remains to count such graphs. The $$$N$$$ even case is obvious. To count the $$$N$$$ odd case consider the graph of unfixed edges. For each connected component, we can choose the existence of all edges except a spanning tree (we need to be careful about the case where the sum of "degree" of all vertices in the component is odd if we consider only fixed edges, in which case the answer is $$$0$$$ since our unfixed edges can only alter the sum of degree by an even number). This gives an $$$O(n^2)$$$ solution.

D is a well known problem,and one can search for countless solutions posted online.Many,sorry to say but it included myself,just copied the solution,modified the edge weight,and got AC.Perhaps problem setters should check for similar,or the same problems more carefully.

Excuse me, but I am having problems with proof of the observation "If you can move to point $$$i$$$ using cost $$$c$$$, you can also move to any point $$$j \lt i$$$ using cost $$$\le c$$$."

Can anyone give some mathematical proof?