As a Writer, I wish all participants enjoy the contest.

Good luck.

How to solve D ?

Not so good at debugging.

Would you please debug my D: https://atcoder.jp/contests/arc154/submissions/38266772?

My idea is the same with editorial, find $$$1$$$ + merge sort.

• Lose lots of rating in recent cf&at contests
• Feel disappointed and choose unrated
• Get good results in this contest
• Check the predictor and cry

E&F are both great >_<

TROC 30 B makes today's' C trivial.
Upd: Added problem link instead.

hey guys i am new here. And i am finding it quite difficult. Can you please help me out on how to start with these contests ? Thanks in advance![user:PCTprobability]

In problem D, you don't need to implement merge sort from scratch. You can use STL stable_sort with a custom comparator (sort doesn't work because it makes too many comparisons).

AC submission

got stuck on D because I wrote a much more complex approach on finding 1 :(

great race,but I think it's difficult for C C feels DP but not=(

Thank you for the problems!

E was super cool. It's a shame that I didn't manage to debug (because I forgot all linear algebra)

A different way to think about F: let $$$X$$$ be the number of rolls to see every side. Let $$$X_i$$$ be the number of rolls to see a new side after seeing $$$i-1$$$ distinct sides already. Then $$$X=X_1+\dotsb+X_n$$$ and the $$$X_i$$$ are independent random variables. The variable $$$X_i$$$ follows a geometric distribution with parameter $$$\frac{n+1-i}{n}$$$. To find the moments of $$$X$$$, we just need to multiply the moment generating functions of the $$$X_i$$$, which gives the following:

Unfortunately, I couldn't finish the problem from here because I didn't know how to go from the coefficients of a polynomial $$$f(x)$$$ to the coefficients of $$$f(e^x)$$$.

weird screencast

the editorial mentions a greedy O(N) solution for B-New Place Can someone please elaborate this?

Could someone elaborate the solution for problem C?

Can anyone explain problem B . I didn't understand the editorial.

how to solve problem c?

Wow, the method (substitution of $$$e^x$$$ and how to calculate it) for F blows my mind. Is it well known? Any tutorials? I think I understood how it works, implemented it, got AC and added to my fft-lib, but... the editorial looks like everyone who reads it is supposed to know that already.

Maybe there is something wrong with the editorial of problem A. (aibj+ajbi)-(aibi+ajbj)is equals to (ai-aj)(bj-bi),instead of (ai-aj)(bi-bj),thus the following conclusions should be wrong. besides,I think we should compare aibj+ajbi with aiaj+bibj instead of aibi+ajbj,the latter seems useless there.

Here is my more detailed solution to F:

We start with a well-known approach. If exactly $$$i$$$ faces have been seen so far ($$$0 \le i \lt N$$$), the probability of seeing a new face after exactly $$$t+1$$$ tosses is $$$(i/N)^t (1-i/N)$$$. Let's consider non-negative integer sequences $$$T = t_0, \ldots, t_{N-1}$$$, then the expected value of $$$m$$$-th power is

Let's define functions $texfix$ $$$p_i(x) = \sum_{t \ge 0} \left(\frac{i}{N}\right)^t x^t = 1/\left(1-\frac{ix}{N}\right)$$$. Then with some new notation we have

where $[x^k]$ denotes the coefficient of formal series at $$$x^k$$$. Next, we can notice that $$$(k+N)^m F(x) [x^k]$$$ is the coefficient of $$$x^{k+N}$$$ of the formal series $$$O^m \left(F(x) x^N\right)$$$, where $$$O = x \frac{\mathrm{d}}{\mathrm{d}x}$$$ is the Mellin operator, effectively just turning $$$x^k$$$ to $$$k x^k$$$. That means we can express

The Mellin operator satisfies the general Leibniz rule for derivatives too, so for non-negative integer sequences $texfix$ $$$E = e_0, \ldots, e_{N-1}$$$, we get

swapping sums to simplify

from now on, let's omit $i=0$ since $$$p_0=1$$$ and it'd cause some annoying singularities. At this point we're not doing any more derivatives, so we can plug in $$$x=1$$$ and simplify further:

where $texfix$ $$$P(x) = \prod_{i=1}^{N-1} \left(x - \frac{i}{N}\right)$$$. We know how to calculate $$$P(x)$$$ by multiplying $$$N-1$$$ linear polynomials or do polynomial inversion easily, we just need the first $$$O(M+1)$$$ terms of the composite $$$y$$$-function $$$P(e^y)$$$ since flipping the sign of $$$y$$$ is just multiplying odd-indexed coefficients by $$$-1$$$.

How to compose a polynomial with exponential? If $$$P(x) = \sum_{j=0}^D c_j x^j$$$ then $$$P(e^y) = \sum_{j=0}^D c_j e^{yj}$$$ and the $$$m$$$-th derivative is $$$\sum_{j=0}^D c_j j^m e^{yj}$$$, so the $$$m$$$-th (at $$$y^m$$$) coefficient of $$$P(e^y)$$$ is $$$\frac{1}{m!} \sum_{j=0}^D c_j j^m$$$. (You may notice the Mellin operator in this again.) For now, let's forget about the $$$1/m!$$$ factor that makes an exponential — we need the coefficients separately for each $$$m$$$ anyway. What function has coefficients $$$\sum_{j=0}^D c_j j^m$$$?

Let's rephrase the final sum in the following way: we have $$$D=N-1$$$ linear polynomials $$$y-\frac{1}{j}$$$ for $$$1 \le j \lt D$$$, we multiply each coefficient $$$(-c_j/j)$$$ by all of them except $$$y-\frac{1}{j}$$$, take the sum, then multiply by the inverse of product of all $$$D$$$ linear polynomials. The "coefficient multiplied by all other factors" sum can be quickly evaluated the same way as Lagrange interpolation polynomial, with divide and conquer — recursively evaluate left half, multiply by the sum of all linear polynomials in the right half and vice versa, then take the sum.

Together, we have time complexity $$$O(N \log^2 N)$$$ for product of linear polynomials and the "coefficient multiplied by all other factors" recursive sum, and $$$O(\max(N,M) \log M)$$$ for inversion and remaining multiplications.

I thought C in some different way, I thought in direction of reverse of given operation and making and converting B->A. The reverse operation can be stated as: If Bi and Bi+1 are equal, replace Bi with any integer in [1,N]. This lead to conclusion that A should contain some cyclic rotation of compressed B as its subsequence.

maroonrk have you ever considered raising or dropping completely the upper bound on rating of rated range for ARCs? Seeing this solution by Xellos or Um_nik saying his mind was blown does not look to me like ARC are too easy for me to pose any challenge. And FWIW it's not like it's an unrepresentive sample. Recently I took one random problem F from ARC with mnbvmar and we spent half an hour thinking together about this, constantly coming up with new observations and after that 0.5h we were around halfway through the solution. In theory I could still participate, but being "unofficial" participant and not being rated is somehow discouraging and I somehow never considered participating regularly in ARCs cause of that even though I should. Especially given how AGC are so rare nowadays