#### A. Lister to your Heart.

**Idea**

It is rather unlikely, that combination of roots of different degrees may be equal to another combination, unless all roots are integers. Therefore, it makes sense to iterate through such $$$x$$$, that $$$x - 3$$$, $$$(x^2 - 1984)/5$$$ are squares, and $$$(3x+2)/2$$$ is a cube.

**Answer**

$$$x = 228$$$.

#### B. WA6.

**Idea**

Int overflow.

**Solution**

Any implementation of binary power (including those from cp-algorithms) would work, when instead of long long or int64_t a simple int is used.

#### C. Anime.

**Idea**

Printing positions of anime discs is a rather unlikely action to "regain hope to better future".

**Solution**

Print $$$n$$$ ones, i.e. everything on the shelf is a trash.

#### D. Distributed Computing.

**Idea**

It is straightforward to observe we are asked to find an area of the union of some rectangles, sharing same corner at $$$(1, 1)$$$, but having different opposite corners $$$(a_i, b_i)$$$.

**Solution**

Let us sort those points by first coordinate: $$$a_1 \le a_2 \le \dots \le a_T$$$. One can see that in order to find an area of the union it is enough to keep just those rectangles corresponding to maximal decreasing subsequence $$$b_{i_1} > b_{i_2} > \dots$$$. Then, calculating the overall area is rather straightforward. Time complexity is $$$O(T\log{T})$$$ because of the sorting, memory complexity is $$$O(T)$$$.

#### E. Rating Recalculating.

**Remark**

The very first fact to pay attention at is that using standard double and pow function lets you calculate the answer correctly up to $$$n \approx 500$$$. Then accuracy of pow significantly decreases.

**Idea**

Given $$$a, b$$$ are large, but of the same order, it is enough to calculate their logarithms. Then $$$a/b = e^{\log{a} - \log{b}}$$$

**Solution 1**

Let $$$a = 1 + x + \frac{x^2}{2!} + \dots + \frac{x^n}{n!}$$$, $$$b = e^x$$$, we see $$$\log{b} = x$$$. Let us calculate $$$\log{a}$$$. Clearly,

Therefore,

Sum $$$1 + \frac{n}{x} + \frac{n(n-1)}{x^2} + \dots$$$ fits good in double, and therefore we calculated $$$\log{a}$$$. Time complexity: $$$O(50 * n)$$$, where $$$50$$$ stands for a maximal amount of values we have to iterate $$$k$$$.

**Solution 2**

Solution calculating $$$e^x$$$ by Taylor Series (instead of pow(e, x)) as $$$e^x = 1 + x + x^2/2! + \dots + x^n/n! + \dots$$$, cut at $$$n = 100000$$$ can also pass.

#### F. Rudolph and Rhymes.

**Idea**

Let $$$q_1, q_2, \dots, q_n$$$ be questions, and $$$a_1, a_2, \dots, a_n$$$ be answers. Denote by $$$\rho_{i,j}$$$ the rhyming value of the pair $$$q_i, a_j$$$. Straightforward calculating of all $$$\rho_{i, j}$$$ gives time complexity as $$$O(Ln)$$$, where $$$L$$$ is a total length of all strings. How to reformulate problem now?

**Solution 1**

Given square $$$n \times n$$$ with number $$$\rho_{i, j}$$$ at cell $$$(i, j)$$$, we need to choose $$$n$$$ cells in such a way so that no two belong to the same row or column, while the sum $$$\sum {\rho_{i, j}}$$$ is large as possible. This a classical problem for Hungarian algorithm. One can use an elegant implementation in 26 rows from cp-algorithms with time complexity $$$O(n^3)$$$. Finally, time complexity is $$$O(n^3) + O(Ln)$$$, memory complexity is $$$O(Ln) + O(n^2)$$$.

**Solution 2**

Now let us use a dynamic programming approach. We reverse all the strings (both questions and answers) and sort then in lexicographic order, obtaining a sequence $$$s_1, s_2, \cdots, s_{2n}$$$. One can see that longest common prefix of $$$s_i, s_j$$$ is the minimal value among $$$(s_i, s_{i+1}), \cdots, (s_{j-1}, s_j)$$$.

Let $$$q_1, q_2$$$ be 2 arbitrary questions, аnd $$$a_1, a_2$$$ be 2 arbitrary answers. Suppose that in optimal solution $$$a_1$$$ replies to $$$q_1$$$, а $$$a_2$$$ replies to $$$q_2$$$. Then one can observe that segments $$$a_1q_1$$$ and $$$a_2q_2$$$ either do not interesct or one belongs to another.

Let $$$d[i][j]$$$ be a maximal rhyming value when we connect questions and answers from $$$s_i$$$ to $$$s_j$$$. If segment $$$s_i, s_j$$$ has different number of questins and answers we put $$$d[i][j] = -INF$$$. Otherwise,

Time complexity is $$$O(n^3)$$$, and the answer to the problem is $$$d[1][2n]$$$.

The disadvantage of such an approach is that it is not that easy to restore a mapping from questions to answers.

**Remark**

There are also solutions using string-related data structures.

#### G. Noogies.

**Remark 1**

It is clear from the statement that we need to find $$$n$$$ such that $$$n - \phi(n) = m$$$, where $$$\phi(n)$$$ is an Euler function (which is an amount of numbers, less or equal than $$$n$$$, and coprime to $$$n$$$). We know that for $$$n = p_1^{\alpha_1}\dots p_k^{\alpha_k}$$$ equality $$$\phi(n) = p_1^{\alpha_1 - 1}\dots p_k^{\alpha_k - 1}(p_1 - 1)\dots (p_k - 1)$$$ holds.

**Remark 2**

We will only consider case $$$m > 1000$$$ (and use bruteforce for smaller $$$m$$$).

**Idea 1**

When $$$m$$$ is odd, then $$$n = pq$$$ would work, where $$$p, q$$$ are primes such that $$$p + q = m + 1$$$.

**Idea 2**

When $$$m$$$ is even, inequality $$$m < n \le 2m$$$ holds.

**Idea 3**

Let us search for solutions $$$n$$$ of form $$$n = ab$$$, where $$$a, b$$$ are relatively small. Fixing one of them (say $$$a$$$) enables us to iterate through it. Equation $$$n - \phi(n) = m$$$ becomes then $$$ab - \phi(a)\phi(b) = c$$$, or $$$ax - \phi(a)y = c$$$.

**Solution 1**

Let us fix some parameter $$$M$$$.

We consider two cases:

**Case 1**

$$$n = ab, \frac{\sqrt{m}}{M} \le a \le b \le \sqrt{m}M$$$, where $$$(a, b) = 1$$$. When $$$a$$$ is fixed, the inequality $$$b \le n/a < 2m/a$$$ holds. Now let us iterate through solutions $$$(x, y)$$$ of equation $$$ax - \phi(a)y = m$$$, given the restriction $$$0 < x < 2m/a$$$. Using the Extended Euclidian Algorithm, we find an arbitrary solution $$$(x_0, y_0)$$$, and then obtain other solutions easily. One can check that the number of such $$$x$$$ for $$$a$$$ is at most $$$O(m/a^2)$$$. Summing $$$O(2m/a^2)$$$ by $$$a$$$ from $$$\sqrt{m}/M$$$ to $$$\sqrt{2m}$$$, we get time complexity $$$O(\sqrt{m}M)$$$.

**Case 2**

If $$$n$$$ can not be represented like this, and therefore $$$n$$$ has a divisor of the form $$$p^k$$$ greater than $$$M^2$$$. Let us look up for solutions $$$n$$$ in form $$$n = ap^k$$$. For simplicity of argument we only consider case $$$k=1$$$ (when $$$k>1$$$, it gives $$$p|m$$$, and it simplifies things). If $$$n = ap$$$, then $$$ap - \phi(a)\phi(p) = ap - \phi(a)(p - 1) = p(a - \phi(a)) + \phi(a) = m$$$. Also inequality $$$a = n/p < 2m/p \le 2m/M^2$$$ holds.

Iterating through $$$a$$$ from $$$2$$$ to $$$2m/M^2$$$, checking $$$(m - \phi(a))/(a - \phi(a))$$$ is indeed some prime number $$$p$$$, we return answer $$$n = ap$$$. Time complexity is $$$O(m/M^2)$$$.

Overall time complexity for two cases is $$$O(\sqrt{m}M + m/M^2)$$$. To optimize it we put $$$M = m^{1/6}$$$. Finally, time complexity is $$$O(m^{2/3})$$$. Memory usage (namely precalculating Euler function up to $$$\sqrt{m}M$$$)) equals $$$O(\sqrt{m}M) = O(m^{2/3})$$$. Hidden constants actually contain some logarithms, coming from calculating gcd and Euler function.

Due to restrictions on time and memory, the following solution could also pass:

**Solution 2**

Let us find $$$n$$$ in form $$$n = ap^k$$$, where $$$(a, p) = 1$$$. One can see that the largest divisor of $$$n$$$ of type $$$p^k$$$ is at least $$$\log{n}$$$. Indeed, if all such divisors were smaller, than even greed search for divisor would have given a contradiction: $$$2 \times 3 \times 5 \times 7 \times \cdots < n$$$). Therefore $$$n = ap^k$$$, where $$$p^k > \log{n}$$$. Let us suppose for simplicity that $$$k = 1$$$. Then $$$m = n - \phi(n) = ap - \phi(a)(p - 1) = p(a - \phi(a)) + \phi(a)$$$. Iterating through $$$a$$$ from $$$2$$$ to $$$2m / \log{m}$$$ we just check that $$$(m - \phi(a)) / (a - \phi(a))$$$ is indeed prime.

Once $$$k > 1$$$, we have $$$p^{k-1} | m$$$. Iterating through divisors of $$$m$$$ of the form $$$p^{\cdots}$$$, we also iterate through $$$O(m/\log{m})$$$ of solutions to the equation $$$p(a - \phi(a)) + \phi(a) = m/p^{k-1}$$$. There are might be up to $$$O(\log{m})$$$ such divisors.

Finally times complexity is $$$O(m)$$$ (with some hidden logarithms), memory complexity is $$$O(m/\log{m})$$$ (because of precalculating the Euler function).

Attention! Thank you for Editorial.

Slight Typo Lister -> Listen

If anime is trash, then so am I...

Hmm I passed E by direct computation (though I did not calculate $$$\frac{x^n}{n!}$$$ using pow but by multiplying $$$x$$$ $$$n$$$ times while dividing by $$$n$$$, $$$n-1$$$, ..., $$$1$$$ along the way).

In problem B Bredor will you please explain why long long gives wa? Reason behind giving overflow and why int don't overflow?

Because Bredor is a troll

I think you did not get the question or the editorial correctly. So, the story is , a person implemented a program to get modular inverse of a number. Turns out he got wrong answer due to some mistake in his code. We have to guess the mistake and make the program with the mistake. The mistake our protagonist made is he used int instead of long long. Therefore, int overflows and not long long.

could anyone tell me what's my mistake in problem B

code

I used long long but wa6

Problem is troll, and so are you!

To cite rockstar2514

the story is, a person implemented a program to get modular inverse of a number. Turns out he got wrong answer due to some mistake in his code. We have to guess the mistake and make the program with the mistake. The mistake our protagonist made is he used int instead of long long.Whole point of problem is troll — change long long to int and you will get "correct" solution.

hhhh, my fault, thank you