Hasnaine_'s blog

By Hasnaine_, history, 4 years ago, In English

Summary of the problem: You are given a polynomial $$$a_0x^0 + a_1x^1 + a_2x^2 + .... + a_nx^n$$$

Initially, you will be given the values of $$$a_0, a_1, a_2, a_3 ..... a_n$$$.

The degree of this polynomial(n) will be at most $$$200000$$$.

Then there will be another $$$200000$$$ query. In each query, you will receive $$$x$$$. You will have to find the value of the polynomial after evaluating with $$$x$$$ with $$$mod$$$ $$$786433$$$.

Problem Link: Codechef Polyeval

Note: There is an editorial about this problem. But in that editorial, setter mostly discussed about the details of FFT rather than the details of the problem. Or I might be missing the whole point. So, can you please help me here? :(

Thanks a lot. I would be obliged.

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

»
4 years ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

That’s actually a really cool problem! The first time I read the editorial, I completely missed the point. You don’t use FFT as a black-box here like usual. You use the idea of how FFT works to evaluate the function at a bunch of points.

You can just evaluate it at x= all points from 1...mod. The idea the editorial describes (which is also how FFT works) is that if you split your x coordinates into two groups in this particularly clever way, the two groups are pretty much the same, so you only have to go down one path instead of two. This makes the runtime n*log(n) rather than n^2.

The key insight here is that instead of using roots of unity (weird imaginary number stuff) you can use powers of a number called a generator with the special property that it has a cycle of length mod-1 if you look at all of its powers. If you just find one of these first, you can use this number as your base and evaluate the polynomial at ALL X’s(!) instead of at a bunch of imaginary numbers around the unit circle.

Clearly, if you have the polynomial evaluated everywhere, the problem is now trivial.

  • »
    »
    4 years ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it

    Thanks a lot for explaining. Though I am spending a lot of time nowadays trying to learn all the details about FFT, there's always remain some confusion.

    But I have some question though,

    1. So, Let's I have the coefficient $$$a_0, a_1, a_2, a_3 ....... a_n$$$ of a particular polynomial. Now should I just do divide and conquer here like we do in the FFT and evaluate the polynomial for generator $$$g$$$ instead of primitive roots of unity $$$w_n$$$?

    2. In setter solution and tester solution, they used 3 polynomials of $$$p(g)$$$, $$$p(g^2)$$$ and $$$p(g^3)$$$ to derive the solution where $$$g$$$ = generator. What was the use of it? Why not get one single polynomial and derive the whole solution from it?

    Thanks a lot again.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Another thing to note:

    I think they used a generator of $$$2^k$$$ as the replacement of the primitive root of unity $$$w_n$$$ where given $$$mod$$$ is represented as $$$(2^k * c) + 1$$$. So what was the use of generator $$$g$$$ of prime/mod in the solution?