Lain's blog

By Lain, history, 2 years ago, In English

Consider the $$$n$$$ degree polynomial $$$P(x) = \sum_{i=0}^n p_ix^i$$$. I call the polynomial $$$Q(x)$$$ it's "prefix sum polynomial" if it satisfies the following condition:

$$$ Q(x) = \sum_{y=0}^x P(y) $$$

Essentially, $$$Q(x)$$$ is a prefix sum on the values of $$$P(x)$$$. So,

$$$ \begin{align} Q(x) &= \sum_{y=0}^x P(y) \\ &= \sum_{y=0}^x \sum_{i=0}^n p_i y^i \\ &= \sum_{i=0}^n p_i \sum_{y=0}^x y^i \end{align} $$$

Now, all we need is a formula for the prefix sum of $$$y^i$$$. This is given by Faulhaber's Formula:

$$$ \sum_{y=0}^x y^i = \frac{1}{i+1} \sum_{j=0}^i \binom{i+1}{j} B_j x^{i+1-j} $$$

where $$$B_j$$$ is the $$$j$$$th Bernoulli number. The formula only applies for positive values of $$$i$$$, so we have to handle $$$[x^0]P(x)$$$ separately. Moreover, we can tell from this formula that the degree of $$$Q(x)$$$ will be $$$n+1$$$.

Just using the formula above is enough to find $$$Q(x)$$$ in $$$O(n^2)$$$, but let us go further. From what we know so far, the coefficients of $$$Q(x)$$$ would be:

$$$ \begin{align} [x^i]Q(x) &= \sum_{j=i-1}^n \frac{p_j}{j+1} B_{j+1-i} \binom{j+1}{j+1-i} \\ &= \sum_{j=i-1}^n \frac{p_j}{j+1} B_{j+1-i} \frac{(j+1)!}{i! \cdot (j+1-i)!} \\ &= \frac{1}{i!} \sum_{j=i-1}^n (p_j j!) \cdot \frac{B_{j+1-i}}{(j+1-i)!} \\ \end{align} $$$

This looks suspiciously like a convolution. Let us define $$$A(x)$$$ and $$$B(x)$$$ as:

$$$ A(x) = \sum_{i=0}^n \frac{B_{n-i}}{(n-i)!} x^i $$$
$$$ B(x) = \sum_{i=1}^n (p_i \cdot i!)x^i $$$

Then,

$$$ [x^i] Q(x) = \frac{[x^{i+n-1}](A \cdot B)}{i!} $$$

We can include the contribution of $$$[x^0]P(x)$$$ after this by adding it to $$$[x^0]Q(x)$$$ and $$$[x^1]Q(x)$$$. This way, we can calculate $$$Q(x)$$$ in $$$O(n \log n)$$$ using FFT.

Finally, we need to tackle the problem of calculating the Bernoulli numbers. We could use the recursive formula on the Wikipedia page, but that's $$$O(n^2)$$$. Instead, we can use the exponential generating function of the Bernoulli numbers:

$$$ \frac{x}{e^x-1} = \left(\sum_i \frac{x^i}{(i+1)!} \right)^{-1} $$$

Now, we can solve the entire problem in $$$O(n \log{n})$$$.

I'd like to thank neal since I only found this technique by looking at his submission for ARC 104 E. I later found out that this same idea is used in the problem SERSUM by chemthan, but I decided to make the blog anyway to introduce it to more people.

Edit: I've also put this on my personal blog. I'll probably put less CF blog-worthy things there in the future.

Full text and comments »

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

By Lain, history, 3 years ago, In English

The round is starting in around half an hour. Let's discuss the approaches here after it's done.

Good luck!

Full text and comments »

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

By Lain, history, 3 years ago, In English

The above image is a problem from a recent hiring test by CodeNation. Any clues on how to solve it?

P.S. This test is over, it's been a couple days now

Full text and comments »

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

By Lain, history, 3 years ago, In English

The Problem

I am trying to solve problem 1136E, where I need to find the lowest $$$pos$$$ such that $$$b_{pos} \geq b_i + x$$$. I generally use the lazy segment tree from the AtCoder Library, which is iterative. In a recursive segment tree, I could just move down the tree choosing the left or right node. How do I do this in an iterative segment tree?

My attempt

  int find_pos(int val)
  {
    int root = 1;
    while (root < size)
    {
      push(root);
      int l = 2*root;
      int r = 2*root+1;
      if (t[l].mx >= val)
        root = l;
      else
        root = r;
    }
    return root-size;
  }

Reference submission

This gives the wrong lower bound on some cases. I think it's because in the iterative case, it is not a clear tree, but rather a set of binary trees. Usually we move bottom up when calculating in an iterative segtree, so either it is not possible in an iterative segtree (without magic) or I have misunderstood something. Please let me know.

Full text and comments »

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