Блог пользователя maroonrk

Автор maroonrk, история, 5 месяцев назад, По-английски

We will hold AtCoder Grand Contest 076. This contest counts for GP30 scores.

The point values will be 700-1100-1200-1400-1400.

We are looking forward to your participation!

  • Проголосовать: нравится
  • +75
  • Проголосовать: не нравится

»
5 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

For the problem D editorial, does "by hand" mean via the Lagrange inversion theorem? Or is there a different way?

References:

  • »
    »
    5 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Also, is there somewhere I can find a list of problems involving power series composition?

  • »
    »
    5 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится +10 Проголосовать: не нравится

    There are several ways to calculate the inverse of $$$x \exp(-x)$$$. Lagrange inversion theorem is the easiest one, but here's more tricky approach.

    Let's consider the case of $$$A=(0)$$$ in this problem, then $$$\exp(-x) g(x \exp(-x)) = 1$$$. Let $$$h(x)=x g(x)$$$ and we have $$$h(x \exp(-x))=x$$$. This means that $$$h$$$ is the compositional inverse of $$$x \exp(-x)$$$. $$$[x^n] h(x) = [x^{n-1}] g(x)$$$, and considering the original problem with $$$A=(0)$$$, this equals the volume of the $$$(y_1,\cdots,y_{n-1})$$$ where $$$0 \leq y_1 \leq \cdots \leq y_{n-1} \leq n-1$$$ and $$$y_i \geq i-1$$$. Now we can calculate this value by hand and get the result of $$$n^{n-1}/n!$$$.

»
2 месяца назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Could you give some insight into the intuition for the solution for problem B? In particular, the construction to sort any array with $$$2$$$ steps.