SureYeaah's blog

Problem F from CERC 15
By SureYeaah, history, 7 years ago, In English

I was trying to solve problem F from CERC 15. The problem was basically reduced to finding the sum . How can I find this sum in better than quadratic time without FFT?

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

»
7 years ago, # |
  Vote: I like it +31 Vote: I do not like it

I didn't realize the FFT solution (which is pretty straightforward) while doing virtual so here's my (a bit messy) approach:

Think of the sum as a polynomial of a. More precisely, let then we are looking for

Now let's calculate Fy(a) according to Fy - 1(a):

Hence,

Since F0(a) is easy to calculate, we can achieve O(N * log(N)) time complexity, with logarithm factor being the cost for calculating modular inversions.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    I have not read carefully your solution, but seeing just the last line I am pretty sure you got exactly the same solution as I got on contest. I first wrote FFT solution but at that time our FFT from library was not precise enough, so I needed to come up with completely different solution and did what you did. However there is a division by a - 1 in your formula. So you need to also consider case a = 1 :). But I have not done this on contest. And got AC either way :DD. However it is easy to fix, so that is not a big deal.

    However there were other controversies about this problem. It has a really easy solution if (which can't be easily seen from presented here reduced version but can be seen from original statement). You can add to all values of F and you basically get rid of +c term and that makes problem very easy. But if you can't do this, you are basically screwed, there is no easy fix for this. But in tests there were no cases where P|a + b - 1, so many people wrote this solution and got it accepted.

    Authors of that problem thought only about FFT solution that has no special cases and they missed other solutions (it turned out that there are at least two different approaches that were already described here), so they did not prepare tests against them what led to many participants getting not deserved AC.

    → Reply