### maroonrk's blog

By maroonrk, history, 2 weeks ago, We will hold AtCoder Regular Contest 154.

The point values will be 300-400-500-700-900-900.

We are looking forward to your participation! Comments (40)
 » As a Writer, I wish all participants enjoy the contest.
 » It will be another difficult contest, though.
 » Good luck.
•  » » Good luck.
 » How to solve D ?
•  » » HintMerge sort
 » 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.
•  » » I think your f1() function takes too many queries. In the worst case here, we need to make 3 queries to remove a single element. So that's $3n + n \log n = 28000$ queries in an upper-bound worst case which is too many. I don't know what the actual worst case is for your code because if every query returns 1, we remove all 3 elements after 3 queries, which is fine. But if we use 3 queries to only remove 1 element, that's bad. Changing the f1() function gives AC. Spoiler int one = 1; for(int i = 2; i <= n; i++){ int x = query(one, one, i); if(x == 1) one = i; } return one; 
•  » » » Thank you! You are so good at debugging.
 » 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 >_<
 » 2 weeks ago, # | ← Rev. 2 →   TROC 30 B makes today's' C trivial.Upd: Added problem link instead.
•  » » 11 days ago, # ^ | ← Rev. 2 →   In the solution of TROC 30 B, errorgorn mentioned that r(B) must be a subsequence of r(A), hence r(B) must be a subsequence of A. But that is not fit for the second test case i.e 42 3 1 12 1 1 2 Can you tell me the reason why?
•  » » » There is a slight difference between these two problems, operations are same but arrays are cyclic in ARC problem, but they aren't in TROC problem.So you should solve TROC problem for n different A's A[i...n]+A[0....i-1] (when B has < n distinct elements), if answer is yes for any of them, answer is yes overall.In this example, first change B to 1 2, removing consecutive elements taking into account that array is cyclic. Then 1 1 3 2 has 1 2 as subsequence.Submission
•  » » » » Thanks
 » 2 weeks ago, # | ← Rev. 2 →   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]
•  » » If you find ARC too hard, try to participate in some ABCs first. They are much easier.
•  » » » Oh okay I'll do that... thankyou!
 » Extremely subjective viewD is too straight-forward to worth $700$ points.
•  » » I think it is. But there is a gap between "knowing how to do" and "AC", especially it is an interactive problem which is hard to debug.Would you please debug my D: https://atcoder.jp/contests/arc154/submissions/38266772? Thanks!
 » 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!
 » 2 weeks ago, # | ← Rev. 2 →   E was super cool. It's a shame that I didn't manage to debug (because I forgot all linear algebra)
•  » » Okay, my solution is much harder than the one at the editorial, never mind (I found an orthogonal eigenbasis of the transition matrix and then calculated the value of $(1, \ldots, n)\cdot A^m\cdot p^T$)
 » 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: $\displaystyle\sum_{k=0}^{\infty}\frac{\mathbb{E}[X^k]}{k!}x^k=\dfrac{(n-1)!e^{nx}}{\displaystyle\prod_{k=1}^{n-1}(n-ke^x)}.$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)$.
 »
 » the editorial mentions a greedy O(N) solution for B-New Place Can someone please elaborate this?
•  » » Find the longest suffix of $S$ that is a subsequence of $T$. You can build the subsequence from right to left, always picking the rightmost available character.Submission
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   thanks got it
•  » » » thanks
 » 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.
 » Why am i getting a wrong answer in C?--https://atcoder.jp/contests/arc154/submissions/38281022
 » 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.
•  » » Oops, sorry, fixed.
 » 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 $a_m = \sum_{k \ge 0} (k+N)^m \sum_{T: \sum(T)=k} \prod_i \left(\frac{i}{N}\right)^{t_i} \prod_i \left(1-\frac{i}{N}\right) \,.$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 $a_m = \prod_i \left(1-\frac{i}{N}\right) \sum_{k \ge 0} (k+N)^m \prod_i p_i(x) \quad [x^k] = C_{\prod} \sum_{k \ge 0} (k+N)^m F(x) \quad [x^k]$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 $a_m = C_{\prod} \left[ O^m \left(F(x) x^N \right) \right]_{x=1} = C_{\prod} \left[ O^m \prod_i \frac{x}{1-ix/N} \right]_{x=1} \,.$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 $O^m \prod_i \frac{x}{1-ix/N} = m! \sum_{E: \sum(E)=m} \prod_i \left(\frac{1}{{e_i}!} O^{e_i} \frac{x}{1-ix/N}\right) = m! \prod_i \left(\sum_{e \ge 0} \frac{1}{e!} O^e \frac{x}{1-ix/N} y^e \right) \quad [y^m] \,,$ $O^e \frac{x}{1-ix/N} = O^e \sum_{k > 0} \left(\frac{i}{N}\right)^{k-1} x^k = \sum_{k > 0} \left(\frac{i}{N}\right)^{k-1} k^e x^k \,,$swapping sums to simplify $\sum_{e \ge 0} \frac{1}{e!} O^e \frac{x}{1-ix/N} y^e = \sum_{k > 0} \left(\frac{i}{N}\right)^{k-1} x^k \sum_{e \ge 0} \frac{1}{e!} \left(ky\right)^e = \sum_{k > 0} \left(\frac{i}{N}\right)^{k-1} x^k e^{ky} \,;$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: $a_m = m! \, C_{\prod} \prod_i \left(\sum_{k > 0} \left(\frac{i}{N}\right)^{k-1} x^k e^{ky} \right)_{x=1} \quad [y^m] = m! \, C_{\prod} \prod_i \frac{e^y}{1-\frac{i}{N} e^y} \quad [y^m] = m! \, C_{\prod} \frac{1}{P\left(e^{-y}\right)} \quad [y^m] \,,$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$? $\sum_{m \ge 0} y^m \sum_{j=0}^D c_j j^m = \sum_{j=0}^D c_j \sum_{m \ge 0} (yj)^m = \sum_{j=0}^D \frac{c_j}{1-yj} = c_0 + \sum_{j=1}^D \left(\frac{-c_j}{j} \right) \cdot \left( y - \frac{1}{j} \right)^{-1}$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.