### A – Repeat ACL

**Спойлер**

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

**Спойлер**

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

**Спойлер**

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 `dsu`

module of 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 they aren't, `merge`

them and decrement $$$c$$$.

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

### D – Flat Subsequence

**Спойлер**

Imagine an array $$$B$$$, initially filled with zeros. The answer then can be theoretically obtained with the following algorithm:

For each $$$a$$$ in $$$A$$$:

- Find $$$\displaystyle\max _{j = a-k} ^{a+k} B_j$$$. Let it be $$$r$$$
- Set $$$B_a := r+1$$$. This works because you are finding the longest subsequence that can include $$$a$$$, and then extending it.

Then the final answer is $$$\max B_i$$$.

Unfortunately this is too slow as searching for the maximum in a range naively is $$$O(K)$$$, thus making the final complexity $$$O(NK)$$$. However, there is a special data structure that solves this problem, called a segment tree.

Segment trees work by storing the array data in the leaves of a fixed binary tree, then storing a "sum" in the ancestor nodes of those leaves. Updating a single entry is slower than a normal array as $$$O(\log n)$$$ ancestors need to be updated, but querying the "sum" of a range becomes much faster, as only $$$O(\log n)$$$ nodes need to be accessed, and the data "summed".

The scare quotes around "sum" imply that it's a more general term — segment trees can indeed implement sums, but more generally, it can implement any monoid. Basically, it's a closed binary operation $$$(S \oplus S) \rightarrow S$$$ that is both associative and has an identity element.

As you are only storing non-negative integers, the $$$\max$$$ operator indeed has an identity element, $$$0$$$. Even if you needed to store negative integers, you can typically set the identity to any number lower than anything else you'd use (just like how you might use a large number as "infinity" in DP/greedy problems)

The `segtree`

module in the AtCoder library is an implementation of a segment tree. Be sure to read the documentation carefully; you need to set the operator and identity element. Ranges should be entered in half-open form, and be careful of accidentally exceeding the index limits in queries.

There is also a way to solve this using only an ordered map.

### E – Replace Digits

**Спойлер**

Precalculate $$$10^x$$$ (under modulo, of course) for $$$0 \le x \le N$$$. Also precalculate $$$\displaystyle ones(x) = \sum _{j=0} ^{x-1} 10^j$$$ for $$$0 \le x \le N$$$, representing the value of a string of all ones of length $$$x$$$.

This problem should remind you a lot of the previous one, however you now have to also update on a range. This can be done using a lazy-propagating segment tree. It's "lazy" because range updates are not all done straight away, but could be "queued" up in an ancestor node, only being "pushed" toward the leaves when needed for queries.

There is a `lazysegtree`

in the AtCoder library as well. Configuring it for this problem is a little more involved than the previous one:

The monoid operator isn't a simple sum, but requires that the

*size*of the segment to be known as well. Thus $$$S$$$ should be a tuple $$$(sum, size)$$$, with the operator $$$(sum_a, size_a) \oplus (sum_b, size_b) = (sum_a \cdot 10^{size_b} + sum_b, size_a + size_b)$$$. Its identity, $$$e = (0, 0)$$$. The $$$sum$$$ terms should be under modulo.$$$F$$$, the mapping, can be a simple integer indicating the digit to update with, however a "null / identity map" needs to be assigned as well, this could be $$$id = -1$$$. $$$composition(g, f)$$$ should be $$$g$$$ (the newer update is on the left as in the traditional notation $$$(g \circ f)(x) = g(f(x))$$$). $$$mapping(f, s)$$$ should be $$$s$$$ if $$$f = id$$$, and otherwise $$$(f \cdot ones(size_s), size_s)$$$

The rest is then just implementing the task. Note that when initializing the segment tree, the value $$$(1, 1)$$$ needs to be set individually to all indices; you can't just queue a $$$1$$$ range-update as they start out as the empty segment $$$(0, 0)$$$.

You can also still solve this with an ordered map.

### F – Heights and Pairs

**Спойлер**

Define a *bad pair* as a pair where the two persons' 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 $$$F_k$$$ denote the set of sets of exactly $$$k$$$ bad pairs, such that within a set, no person appears twice. Let's assume we have a function, $$$f(k)$$$, denoting the size of $$$F_k$$$. $$$f(0) = 1$$$, because there is exactly one set consisting of $$$0$$$ bad pairs: the empty set.

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

Imagine that we got the bad pairs from $$$F_1$$$, and listed them in some arbitrary order. Let $$$BAD_i$$$ denote the set of all bad matchings that contain the $$$i$$$-th bad pair in that list. We want to find the size of the union of all $$$BAD$$$ sets, i.e. $$$|BAD_{1} \cup BAD_{2} \cup ... \cup BAD_{f(1)}|$$$ However we only have the sizes of the individual $$$BAD$$$ sets, which are all $$$pairs(N-1)$$$, cause we've constructed $$$N-1$$$ pairs after the fixed bad pair. Thus the sum of their sizes are $$$f(1) \cdot pairs(N-1)$$$

This however, overcounts the size of the union, as matchings with more than one bad pair would be represented in several $$$BAD$$$ sets. However, we can obtain the sum of sizes of pairwise intersections $$$BAD_i \cap BAD_j$$$ by fixing *two* bad pairs using the sets from set $$$F_2$$$, then filling the rest arbitrarily; the sum is thus $$$f(2) \cdot pairs(N-2)$$$

[noting that if we counted $$$f(2)$$$ correctly, we would correctly skip the empty intersections where bad pairs $$$i$$$ and $$$j$$$ happened to contain the same person]

Likewise we can obtain sums of sizes of triple-wise intersections, etc., then using the inclusion-exclusion principle to obtain the formula

And note that our final answer,

[If this is difficult to understand, try working through the "Counting derangements" example in the Wikipedia article, which describes an analogous but simpler situation of "fixing" matching cards like we do with bad pairs here]

Now let's figure out how to find $$$f(k)$$$. First note that the exact heights don't matter, only their equality. We can divide the people into *components* with the same height as each other. Collect all component sizes into array $$$a$$$. For example, if $$$h = [1, 1, 1, 2, 2, 4]$$$, then $$$a = [3, 2, 1]$$$. This can be easily done using sorting and run-length compression.

Then from each component $$$a_i$$$, construct array $$$b_i$$$, indexed over $$$[0, \lfloor a_i/2 \rfloor]$$$, where $$$b_i[j]$$$ denotes how many ways are there to fix $$$j$$$ bad pairs from this component. $$$\displaystyle b_i[j] = \binom {a_i}{2j} \cdot pairs(j)$$$, since we take $$$2j$$$ people from the component and make $$$j$$$ pairs out of them.

In the case of a single component, $$$f(j) = b_1[j]$$$, but how do we combine the results of several components? Let's assume we have only two components. Then we may take $$$0$$$ bad pairs from one component and $$$j$$$ from the other, or $$$1$$$ from one and $$$j-1$$$ from the other, etc., therefore:

$$$\displaystyle f(j) = b_1[0] \cdot b_2[j] + b_1[1]\cdot b_2[j-1] + b_1[2]\cdot b_2[j-2] + ... + b_1[j]\cdot b_2[0] = \sum_{i=0}^j b_1[i] \cdot b_2[j-i] $$$.

This is called a *convolution*, and is the same formula for when we multiply two polynomials of the form $$$p(x) = B_0x^0 + B_1x^1 + B_2x^2 + ... + B_nx^n$$$ and wishing to find the $$$j$$$-th coefficient. The case with more components is similar, except we must convolve all the $$$b_i$$$ arrays, i.e. find the product of several polynomials of different lengths.

[One can visualize this by treating $$$x^k$$$ as a formal symbol meaning "ways to make $$$k$$$ bad pairs", which naturally add together when their coefficients are multiplied]

However, computing convolutions for two polynomials of size $$$n$$$ and $$$m$$$ naively is $$$O(nm)$$$, which is too slow. There is just the right tool in the AtCoder library for that; the function `convolution`

. This function uses the Fast Fourier Transform method to convolve two polynomials in $$$O((n+m) \log (n+m))$$$. However note that it only accepts two arguments, and convolving multiple polynomials could be inefficient if called in the wrong order; imagine if you had about $$$N/2$$$ polynomials, and all of them are short except for one. Then imagine if you convolved a short one to the longest one over and over; suddenly your submission takes $$$O(N^2 \log N)$$$ and times out.

Fortunately there is a simple fix: just put all the polynomials into a heap / priority queue that sorts them from shortest to longest. While there is more than one polynomial in that heap, withdraw two, convolve them, then put the result back in the heap.

This works in $$$O(N \log ^2 N)$$$, the worst case being $$$N$$$ polynomials of degree $$$1$$$ (length $$$2$$$), which would take $$$O(\log N)$$$ "cycles" to fully combine, with the convolutions taking a time of $$$O(N \log N)$$$ each cycle.

And thus finally, you are able to obtain $$$f(k)$$$ by reading the coefficients of the final polynomial, and can apply the inclusion-exclusion formula above to obtain the answer.

Thanks for the detailed explanations!

Unfortunatly I still do not get F at all, I am out before the interesting part. Here are my questions:

The term "matching" does mean... a pair of two persons, or the set of pairs in one permutation?

I think I understand the definition of $$$pairs(n)$$$. Is there a difference to $$$pairs(N)$$$?

The function $$$f(k)$$$, what exactly is the meaning of $$$f(1)$$$, it is the number of permutations with one... what?

How do you come from $$$f(k)$$$ to $$$BAD(x,y)$$$, there is the term "seed"?

Matching means a state where all the people are paired up (and some might be bad pairs)

$$$pairs(N)$$$ simply means the $$$pairs$$$ function called on the $$$N$$$ given in the input

$$$f(k)$$$ is the number of sets of exactly $$$k$$$ bad pairs, such that within a set, no person appears twice; i.e. the cardinality of $$$F_k$$$. It's used to "fix" $$$k$$$ bad pairs before matching the rest using $$$pairs$$$.

The rest is just a way to tie the set-theoretic definition of the inclusion-exclusion principle to the counts we are interested in. There might be room for improvement there

edit: Oh I noticed a use of "matching" when defining a bad pair, thus being inconsistent, I shall fix it

Maybe try reading the "counting derangements" example in the Wikipedia page for the inclusion-exclusion principle; it's an analogous but simpler example of the application in this problem. When counting derangements of cards, you count the number of permutations fixing one matching card, two matching cards, etc., same applies here with fixing one bad pair, two bad pairs, etc.

For Problem D:

Can you explain it a bit?

Problem D, and E much more transparently, can both be reframed as what I call "segment painting" problems. They're basically like the "junior" version of lazy-segtree where a range query is always followed by an assignment in the same range, thus destroying or truncating ("painting over") any old segments in the way.

The method is as follows — use an ordered map of entries $$$r \rightarrow (l, s)$$$, denoting a segment in the range $$$[l, r)$$$ (half-open ranges are convenient here) with metadata $$$s$$$ (e.g. the length of the longest subsequence in D, the digit in E). On each update, you have a new segment $$$(l_{new}, r_{new}, s_{new})$$$; iterate through the map starting from $$$l_{new}+\varepsilon$$$ (using e.g.

`upper_bound`

in C++ or`higherKey`

in Java). Then you may do something with each overlapped segment (in fact you may even decide $$$s_{new}$$$ with this step), and remove them from the map. If the old segment isn't completely covered, it should be replaced with a smaller segment (truncation); in fact this may split an old range into two, in the case of $$$l_{old} < l_{new} \wedge r_{old} > r_{new}$$$. Stop when you either reach the end or find a non-overlapping segment, then add the new range to the map.This works in $$$O(n \log n)$$$ because each operation adds a maximum of $$$3$$$ range entries to the map, and only iterates through and immediately removes older entries.

E is quite straightforwardly solved this way, but D requires a transformation where points $$$A_i$$$ are replaced by segments $$$[2A_i - k, 2A_i + k + 1)$$$. Funnily enough I found this solution before the segtree solution (and only after solving E), due to how brains work sometimes...

(Food for thought: is there a problem that can be solved this way that lazy-segtree can't, due to greater flexibility?)

Can you provide link to your submissions, in case you solved using an ordered map?

For D

For E

Bonus: For "Painter" problem in EDU Segment Tree part 2: https://pastebin.pl/view/c1d86bdf

Thank you for your solution. Pretty cool technique. For those who want to check out C++ solution for Problem E

Link to submission : https://atcoder.jp/contests/abl/submissions/17139903

But I am still not clear about the complexity part. What I understood so far :

What I didn't understand is "and only iterates through and immediately removes older entries.". Can you please elaborate it a bit more, because I guess this the crucial part for calculating complexity.

Can you please explain why there is bound on number of elements that we will be iterating over in our data structure?

Iterating through the map takes $$$O(\log n)$$$ per entry, but you delete entries right after iterating through them (except for the one that tells you to stop, but that's only one per step), so you can amortize that cost into the cost of the step that placed that entry into the map.

It's analogous to the analysis of stack-based problems. A single step may iterate through and remove many older entries of the stack, but those entries must have already been added by a previous step, and once an entry is removed they won't be accessed anymore.