We will hold AtCoder Regular Contest 154.

- Contest URL: https://atcoder.jp/contests/arc154
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230122T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: PCTprobability
- Tester: tatyam, maspy
- Rated range: — 2799

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

We are looking forward to your participation!

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.SpoilerThank you! You are so good at debugging.

E&F are both great >_<

TROC 30 B makes today's' C trivial.

Upd: Added problem link instead.

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 4

2 3 1 1

2 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

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!

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:

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?

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

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

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.