maroonrk's blog

By maroonrk, history, 2 weeks ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +141
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it +171 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It will be another difficult contest, though.

»
2 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Good luck.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D ?

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
»
2 weeks ago, # |
  Vote: I like it +51 Vote: I do not like it
  • 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   Vote: I like it +19 Vote: I do not like it

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

  • »
    »
    11 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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]

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    If you find ARC too hard, try to participate in some ABCs first. They are much easier.

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it
Extremely subjective view
»
2 weeks ago, # |
  Vote: I like it +38 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for the problems!

»
2 weeks ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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$$$)

»
2 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

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)$$$.

»
2 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Could someone elaborate the solution for problem C?

»
2 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

how to solve problem c?

»
2 weeks ago, # |
  Vote: I like it +41 Vote: I do not like it

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.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why am i getting a wrong answer in C?--https://atcoder.jp/contests/arc154/submissions/38281022

»
11 days ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

»
6 days ago, # |
  Vote: I like it +16 Vote: I do not like it

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.

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.