### A – Repeat ACL

**Spoiler**

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)
}
```

### B – Integer Preference

**Spoiler**

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.

### C – Connect Cities

**Spoiler**

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.

### D – TODO

**Spoiler**

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.

### E – TODO

**Spoiler**

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)$$$.

### F – Heights and Pairs

**Spoiler**

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