Easy programming-language-knowledge check typical of the first task of AtCoder beginner contests. The following is a passing Kotlin submission:

fun main() {
    val k = readLine()!!.toInt()
    val ans = "ACL".repeat(k)
    println(ans)
}

Assume there is an integer in both ranges and call it $$$x$$$. Note that both $$$x \ge \max(A, C)$$$ and $$$x \le \min(B, D)$$$ must therefore be true.

Thus $$$x$$$ exists if and only if $$$\max(A, C) \le \min(B, D)$$$ is true. This is the standard formula for finding the overlap of two ranges.

Note that the initial network of cities can be divided into one or more components, where any city of a component can reach any other city in that component following roads, but there are no roads connecting components together.

If there are $$$c$$$ components, Snuke can connect two of them by choosing one city from each component and building a road between them, which combines them to a single component; so the answer would be $$$c - 1$$$.

Components can be found using breadth-first/depth-first searches, however there's an easier way if you already have a special data structure known as DSU (disjoint-set union). And there is an implementation available right in the AtCoder library. So start with $$$c := N$$$, for each road given in the input, you can use same to check if the vertices are already connected; if there isn't, merge them and decrement $$$c$$$.

Note that though the input is $$$1$$$-indexed, the AtCoder DSU implementation is $$$0$$$-indexed.

Can be done with basic dynamic programming. Let $$$dp_i$$$ represent the number of sequences whose sum is $$$i$$$. $$$dp_0 = 1$$$, the empty sequence. Then $$$\displaystyle dp_i = \sum_{j=0}^{i-3} dp_j$$$, i.e. the sum of $$$dp_j$$$ for all integers $$$j$$$ between $$$0$$$ and $$$i-3$$$ inclusive, representing the addition of a number $$$\ge 3$$$ to each of the previous sequences. The final answer, naturally, is $$$dp_s$$$.

This can be easily calculated in $$$O(s^2)$$$, which is good enough to pass, however it can be improved to $$$O(s)$$$ by accumulating the prefix sum.

An $$$O(\log s)$$$ solution is possible via matrix exponentiation.

We can take the following approach — for each $$$i$$$ from $$$2$$$ to $$$n$$$, try to match $$$(x_i, y_i)$$$ with the "best" previous point $$$(x_j, y_j), 1 \le j < i$$$, then update the answer.

Testing all previous points is too slow ($$$O(n^2)$$$). However, it is sufficient only to keep up to $$$4$$$ previous points to test against. $$$2$$$ of those points are the maximal and minimal of the "score" $$$x_i + y_i$$$, while the other $$$2$$$ maximize and minimize $$$x_i - y_i$$$

Why? Note that taking any point as the center, the set of points with Manhattan distance some arbitrary constant $$$d$$$, forms a "diamond" shape, i.e. a square rotated 45 degrees. Thus the furthest point must lie on at least one of the four sides of this square when $$$d$$$ is maximized. As the sides are on lines with equations of $$$x+y = C$$$ or $$$x-y = C$$$, the maximums and minimums of these values are sufficient to find the furthest point in each of the 4 possible directions.

Thus we have a solution in $$$O(n)$$$.

Define a bad pair as a matching where the two person's heights are equal.

Let's define a useful function $$$\displaystyle pairs(n) := \frac{(2n)!}{n!\cdot 2^n}$$$, the number of ways to make $$$n$$$ pairs (good or bad) out of $$$2n$$$ people. Explanation: Start with any of $$$(2n)!$$$ permutations. When you pair them up, you don't care about the order within the pair, so you divide by $$$2$$$ a total of $$$n$$$ times. Then you also don't care about the order between the pairs, so you divide by $$$n!$$$.

The main idea involves the Inclusion–exclusion principle. Let's assume we have a function, $$$f(k)$$$, denoting the number of sets consisting of exactly $$$k$$$ bad pairs of people (with no person appearing more than once in a set). $$$f(0) = 1$$$, because there exactly one set consisting of $$$0$$$ bad pairs: the empty set.

We want to find the number of matchings with at least one bad pair; from that we can subtract it from $$$pairs(N)$$$ for the final answer.

Say we had a list of bad pairs $$$L^1$$$; note that $$$|L^1| = f(1)$$$. Each bad pair can be the "seed" of a set $$$BAD_{(x, y)}$$$, denoting the set of all bad matchings that contain the bad pair $$$(x, y)$$$. We want to find the size of the union of all $$$BAD$$$ sets, i.e. $$$|BAD_{L_1} \cup BAD_{L_2} \cup ... \cup BAD_{L_f(1)}|$$$ However we only have the cardinalities of the individual $$$BAD$$$ sets