maroonrk's blog

AtCoder Regular Contest 154 Announcement
By maroonrk, history, 23 months 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
  • +154
  • Vote: I do not like it

Comments Comments (39)
| Write comment?
»
23 months ago, # |
  Vote: I like it +171 Vote: I do not like it

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

→ Reply
»
23 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Good luck.

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D ?

→ Reply
»
23 months 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.

→ Reply
  • »
    »
    23 months 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
    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you! You are so good at debugging.

      → Reply
»
23 months 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 >_<

→ Reply
»
23 months 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.

→ Reply
  • »
    »
    23 months 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?

    → Reply
    • »
      »
      »
      23 months 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

      → Reply
»
23 months 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]

→ Reply
  • »
    »
    23 months 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.

    → Reply
»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it
Extremely subjective view
→ Reply
»
23 months 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

→ Reply
»
23 months 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 :(

→ Reply
»
23 months 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=(

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for the problems!

→ Reply
»
23 months 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)

→ Reply
  • »
    »
    23 months 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$$$)

    → Reply
»
23 months 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)$$$.

→ Reply
»
23 months ago, # |
  Vote: I like it +30 Vote: I do not like it

weird screencast

→ Reply
»
23 months 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?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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

    → Reply
»
23 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Could someone elaborate the solution for problem C?

→ Reply
»
23 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
23 months ago, # |
  Vote: I like it +5 Vote: I do not like it

how to solve problem c?

→ Reply
»
23 months 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.

→ Reply
»
23 months 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.

→ Reply
»
23 months 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.

→ Reply
»
23 months 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.

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it +38 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    At least I'm trying to spare good and hard problems for AGC and don't intend to surprise LGMs in ARCs. For this F, I was able to apply the technique instantly and didn't think it was mind-blowing.

    That being said, apparently, I was making some mistakes, and I'm sorry for the scarcity of AGCs. I've been gradually changing my policy on problem selection, and comments from very strong people are really helpful as a reference. Thank you for your feedback, and I would say this year we'll have more AGCs than last year.

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Agreed, Fs are definitely good enough to raise the limit, though I wouldn't remove it completely.

    → Reply