Codeforces Round #566 (Div. 2) Editorial

If you want to have no empty spaces on $$$3 \times n$$$ tiles, you should fill leftmost bottom tile. Then you have only 2 choices;

Both cases force you to group leftmost $$$3 \times 2$$$ tiles and fill. By this fact, we should group each $$$3 \times 2$$$ tiles and fill independently. So the answer is — if $$$n$$$ is odd, then the answer is $$$0$$$ (impossible), otherwise, the answer is $$$2^{\frac{n}{2}}$$$.

Time complexity is $$$O(1)$$$ with bit operation or $$$O(n)$$$ with iteration.

First, try to find if there is any nonempty space which has 4 neighbors are all nonempty spaces. (Giant black star in the picture below.) If there is no such nonempty space, the answer is "NO".

Second, try to search the end of the "+" shape from the center. (White stars in the picture below.)

Third, try to find if there is any nonempty space outside of "+" shape(the area filled with "?"). If found then the answer is "NO".

If you validated all steps, then the answer is "YES".

Time complexity is $$$O(wh)$$$.

Let's make some definitions;

• $$$s_{1}$$$ and $$$s_{2}$$$ are complete duo if two word $$$s_{1}$$$ and $$$s_{2}$$$ have same number of vowels and the last vowels of $$$s_{1}$$$ and $$$s_{2}$$$ are same. For example, "hello" and "hollow" are complete duo.
• $$$s_{1}$$$ and $$$s_{2}$$$ are semicomplete duo if two word $$$s_{1}$$$ and $$$s_{2}$$$ have same number of vowels but the last vowels of $$$s_{1}$$$ and $$$s_{2}$$$ are different. For example, "hello" and "hola" are semicomplete duo.

If you want to form a beautiful lyric with $$$4$$$ words, then the lyric must be one of the things listed below;

• Consist of two complete duos.
• Consist of one semicomplete duo and one complete duo.

Since the order of lyrics is not important, make complete duos as many as possible, then make semicomplete duos as many as possible. This can be done with the greedy approach with the usage of the red-black tree or hashmap.

After you formed all duos, make beautiful lyrics using one semicomplete duo and one complete duo first, then make beautiful lyrics using two complete duos. With this method, you can make the maximum possible number of beautiful lyrics.

Time complexity is $$$O(n \text{ log } n)$$$ or $$$O(n)$$$.

First, the valid tree should form like the picture below unless the whole tree is completely linear.

• top: This node is the top of the tree. This node has always degree $$$1$$$. This node is always one of the possible answers of valid tree. There might be no top node in the tree.
• semitop: This node is the closest children from the top node that satisfies $$$degree >= 3$$$. In other words, this node is the end of the leaf branch which includes top node as leaf. This node can be one of the possible answers of valid tree. If there is no semitop in the tree, the whole tree is invalid.
• mid level: This is the area of nodes between semitop node and semibottom nodes.
• semibottom: These nodes are the closest ancestors from each leaf nodes which satisfies $$$degree >= 3$$$. In other words, these nodes are the end of each leaf branches.
• bottom: These nodes are the leaves except top node.

And also let's define $$$u_{1}$$$ and $$$u_{2}$$$ are directly reachable if there are only nodes with $$$degree = 2$$$ between $$$u_{1}$$$ and $$$u_{2}$$$ exclusive.

There are two ways to find the top node and the semitop node.

1. Lawali's solution. Find the diameter path and validate for two leaves of the diameter path. If no valid vertex found(i.e. top is not in the diameter path), then the semitop should be the middle of the diameter path. Now validate for the semitop and the closest directly reachable leaf from semitop. If any valid vertex found, print it. Otherwise print $$$-1$$$. The first case of diameter path in valid tree. Semitop node is the middle of diameter path.

   The second case of diameter path in valid tree. Top node is the end of diameter path.

2. McDic's solution. Clone the whole tree and cut the leaf branches(include top) from the cloned tree. Let's call this tree as "inner tree". Inner tree consists of only semitop, mid level nodes and semibottom nodes. Then you can find the semitop by collapsing each level from leaf nodes of inner tree. Now validate for semitop, the furthest directly reachable leaf node from semitop, and the closest directly reachable leaf node from semitop. It is guaranteed that the top node is one of those two leaves. If any valid vertex found, print it. Otherwise print $$$-1$$$. This is the inner tree of original tree. You can find the semitop easier than before since top is removed in inner tree.

Time complexity is $$$O(n)$$$.

You can form the expression into this;

$$$$$$ c^{x} f_{x} = c^{x-1} f_{x-1} \cdot c^{x-2} f_{x-2} \cdot c^{x-3} f_{x-3} $$$$$$

Let $$$g(x, p) = c^{x} f_{x}$$$'s $$$p$$$-occurrence for prime number $$$p$$$. For example, $$$40 = 2^{3} \times 5$$$ so $$$40$$$'s $$$2$$$-occurrence is $$$3$$$.

Then we can set the formula $$$g(x, p) = g(x-1, p) + g(x-2, p) + g(x-3, p)$$$ and calculate $$$g(n, p)$$$ using matrix exponentiation. Since all different prime numbers $$$p$$$ share same matrix, we can calculate matrix only once. And we have less or equal than 36 distinct prime numbers targeted because you cannot get more than $$$9$$$ distinct prime numbers by prime decomposition from numbers in range $$$[1, 10^9]$$$.

With $$$g(x, p)$$$ we can calculate $$$c^{n} f_{n}$$$, and we can calculate $$$f_{n}$$$ using modulo inverse.

Time complexity is $$$O(\text{log } n + \text{ sqrt}(\text{max}(f_{1}, f_{2}, f_{3}, c)))$$$.

Lemma: For all $$$x$$$, $$$y$$$ $$$\in [0, \pi]$$$, if $$$|\text{sin}(x)| > |\text{sin}(y)|$$$ then $$$x$$$ is more closer to the $$$\frac{\pi}{2}$$$ than $$$y$$$.

With this lemma, we can avoid the calculation of floating precision numbers. Let's reform the problem; Find minimum possible integer $$$x$$$ that $$$\frac{p}{q}x \pi \bmod \pi$$$ is the closest to $$$\frac{\pi}{2}$$$. This is equivalent to find minimum possible integer $$$x$$$ that $$$2px \bmod 2q$$$ is the closest to $$$q$$$.

Let $$$g(x) = 2px \bmod 2q$$$. Now set the interval with length $$$t = \text{sqrt}(b-a+1)$$$ and construct the list like this — $$$[(g(a), a), (g(a+1), a+1), \ldots (g(a+t-1), a+t-1)]$$$. Then remove the big number $$$x$$$s with duplicated $$$g(x)$$$ values from the list and sort the list.

Now we can find any $$$x$$$ that $$$g(x)$$$ is the closest to any integer $$$y$$$ in $$$O(\text{log}(n))$$$. We will search all numbers in range $$$[a, b]$$$ without modifying the list we created. How is this possible? Because $$$g(x) + g(y) \equiv g(x+y) \pmod{2q}$$$ for all integers $$$x$$$, $$$y$$$.

So in every $$$\text{sqrt}(b-a+1)$$$ iterations, we can set the target and just find. More precisely, our target value is $$$q - 2 \times i \cdot t \cdot p \bmod 2q$$$ for $$$i$$$-th iteration. With this search, we can find such minimum possible integer $$$x$$$. Oh, don't forget to do bruteforce in remaining range!

The time complexity is $$$O(\text{sqrt } n \text{ log } n)$$$.