You are not logged in. Please login at www.codechef.com to post your questions!

×

POLYEVAL - Editorial

5
3

PROBLEM LINK:

Practice
Contest

Author: Sergey Kulik
Tester: Praveen Dhinwa
Editorialist: Praveen Dhinwa

DIFFICULTY:

med-hard

PREREQUISITES:

fft, advanced maths

PROBLEM:

You are given a polynomial of degree $N$. You have to evaluate the polynomial at some $Q$ points modulo 786433.

EXPLANATION:

Look at the special modulo
The special modulo 786433 gives you an hint for using some sort of FFT algorithm. We have $786433 = 1 + 3 * 2^{18}$ and 786433 is a prime.


Let us learn some basics before proceeding towards FFT algorithm
The field $\mathbb{Z}/p$ is a set of numbers $\{0, 1, \dot, p - 1\}$ where $p$ is a prime with both addition and multiplication operations being mod $p$ operations. Additive inverse of each element in the set will be $0$, and the multiplicative inverse of each non-zero element will also exist. This is due to the fact that each non-zero element in the set will be co-prime to $p$, as $p$ is prime. In fact it will be unique and can be found by solving the equation $a b = 1 \mod p$.

Let ${\mathbb{Z}/p}^{+}$ denote the group of non-zero elements $\{1, 2, \dots, p - 1\}$, i.e.$\mathbb{Z}/p - \{0\}$. This group is a cyclic group. A group is called a cyclic group if it can be generated by a single element. In other words, $g, g^2, g^3, , g^(p - 1)$ will cover all the elements of the group. Note that $g^p = g$. Such an element $g$ is called generator of the group. For example, in group ${\mathbb{Z}/5}^{+} = \{1, 2, 3, 4 \}$, $g = 2$ is a generator. We have $2^1 = 2 \mod 5$, $2^2 = 4 \mod 5$, $2^3 = 3 \mod 5$, $2^4 = 1 \mod 5$. Note that these cover {2, 4, 3, 1}, i.e. all the elements of the group. You can see that each element of this group can be written as powers of $g$. Also see that $3$ is also a generator of the group as $3^1 = 3 \mod 5$, $3^2 = 4 \mod 5$, $3^3 = 2 \mod 5$, $3^4 = 1 \mod 5$. However $g = 4$ is not a generator of the group as $4^1 = 4 \mod 5$, $4^2 = 1 \mod 5$, $4^3 = 4 mod 5$, $4^4 = 1 \mod 5$, which covers only the elements $1, 4$.

You can find one such generator for the group ${\mathbb{Z}/p}^{+}$ (for $p$ = 786433) using a simple bruteforce. You can iterate over each number $g$ from 1 to $p-1$ and check whether the $g^i$ spans all the elements of the group or not. Luckily for this modulo, you can afford to spend $\mathcal{O}(p \, log p)$ time for checking a number being generator or not, because you will soon hit a generator at $g = 10$. You can run this program offline on your computer in 1 or 2 minutes and find one such generator.

In fact, there is a better algorithm than simple bruteforce for checking whether a number is generator or not. For a given $g$, you just have to check whether all the $g^d mod p$ where $d$ is a divisor of $p-1$ are all distinct values or not.


Towards the FFT algorithm
Let us revisit the concept of use of FFT in evaluation of some polynomial of degree at max $n$ at $n$ points in $\mathcal{O}(n \, log n)$ operations.

**Let us take a small example Let us take an example to understand about FFT better. Suppose the polynomial be $x^3 + 3 * x^2 + 4 * x + 5$. We want to evaluate it at four points $\omega, {\omega}^2, {\omega}^3, {\omega}^4$, where $\omega$ is a primitive $4$-th root of unity, i.e. $\omega^4 = 1$, and there does not exist any $i < 4$, such that $\omega^i = 1$. In other words, $\omega$ is a generator of the corresponding group.

Let us divide the polynomial into two parts - the polynomial made of coefficients of even power of $x$ and other of odd powers of $x$. In our case, these polynomials will be $x^3 + 4 * x$ and $3 * x^2 + 5$, respectively.

$$P(x) = $x^3 + 3 * x^2 + 4 * x + 5$$ $$P_{odd}(x) = $x^3 + 4 * x$$ $$P_{even}(x) = $3 * x^2 + 5$$

$$P(x) = x * P_{odd}(x^2) + P_{even}(x^2)$$

Note that now both the polynomials $P_{odd}(x)$ and $P_{even}(x)$ are having only even powers of $x$, i.e. they can even be considered polynomials in $x^2$. So, instead of evaluating them on $x$, let us evaluate them on $x^2$.

$$P(x) = x * P_{odd}(x^2) + P_{even}(x^2), \text{where } P_{odd}(x) = x + 4$$

Let us see what happens with set of points $x$ where we want to evaluate the polynomail when we change $x$ to $x^2$. The set of elements of $x^2$ for the given $x$ will be ${\omega^2, {\omega}^4, {\omega}^6, {\omega}^8 }$.

Note that we have $\omega^4 = 1$, so this set will be ${\omega^2, 1, {\omega}^2, 1 }$. You see that this set has only two distinct elements in it, $1$ and $\omega^2$.

Now you can recursively evaluate the both the polynomials $P_{odd}(x)$ and $P_{even}(x)$ at these two points and combine their them to get an evaluation for each of the four original $x$ values.

Regarding the time complexity, you can notice that in the recursion, both the sizes of the polynomial and that of number of points to evaluate become half in each iteration, which gives a time complexity of $\mathcal{O}(n log n)$ ($n = 4$ for our case).


**Let's do FFT for general $n$**
If you understood the prevoius example, you have kind of understood the idea behind FFT. Let us generalize the same thing for a general $n$. For our discussion, we are considering $n$ to be a power of $2$. If the polynomial does not have degerees in form of two's power, we can append the polynomial by adding zero coefficient higher degrees. Notice that this will never increase the size of the polynomial by more than twice.

Let $P(x)$ be the polynomial we want to evaluate at $\omega, { \omega}^2, \dots, {\omega}^n$ points, where $\omega$ is a primitive $n$-th root unity. Notice that the set $\omega, { \omega}^2, \dots, {\omega}^n$ contains all distinct elements.

$$ S = {{ \omega}, { \omega}^2, \dots, {\omega}^{n - 1}, {\omega}^{n} }$$ $$ S^2 = { {\omega}^2, { \omega}^4, \dots, {\omega}^{2 * n} }$$ $$ S^2 = { {\omega}^2, { \omega}^4, \dots { \omega}^{2 * (n / 2 - 1)}, { \omega}^n, { \omega}^{2 * (n / 2 + 1)}, \dots, {\omega}^{2 * n} }$$

Note that ${\omega}^n = 1$. $$ S^2 = {{\omega}^2, { \omega}^4, \dots, { \omega}^4, { \omega}^{2}, \dots, {\omega}^{n} }$$ $$ S^2 = { {\omega}^2, { \omega}^4, \dots, {\omega}^{n)} }$$

Note that $S^2$ has size $\frac{n}{2}$.

Also notice that ${({\omega}^2)} ^ {\frac{n}{2}} = 1 \mod n \implies {({\omega}^2)} ^ {\frac{n}{2}} = 1 \mod n / 2$.

Pseudo Code
Let us see the pseudo code:

evaluate(Poly, points): if (points.size() == 1): // Evaluate the polynomial using Horner's method. else: divide the polynomial into two parts, evenPoly and oddPoly depending on parity of coefficients. Let points' denote the set of new points on which we want to evaluate. Each element of points' will be square of corresponding element in points. evaluate(evenPoly, points') evaluate(oddPoly, points') // Evaluate the polynomial at points with help of above.

Setter's and Tester's Solutions:

Setter's solution
Tester's solution

This question is marked "community wiki".

asked 19 Jul '16, 22:47

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53136170
accept rate: 20%

edited 22 Jul '16, 00:15


You call this simple? I think there must be a number to the relative hardness of the problem, based on number of attempts, the rating of coders who attempted it, those who got it right, those who couldn't, etc. 'Simple' is like too much! :P

link

answered 20 Jul '16, 10:00

sahilarora.535's gravatar image

4★sahilarora.535
1235
accept rate: 0%

Since 786433=1+3∗2^18 and 786433 is a prime I used NTT by first dividing P(x) in three parts as P(x) = P0(x^3) + x*P1(x^3) + x^2P2(x^3) and then used NTT for polynomials P0, P1 and P2. In this way I computed values of P(x) at all x mod 786433 (except P(0) which is equal to coefficient a0).

link

answered 20 Jul '16, 01:28

n1t1n_153012's gravatar image

5★n1t1n_153012
311
accept rate: 0%

Here's my solution, no FFT required.

eval(P,x[]): # returns map x : P(x)
    if P = constant: return map [a : constant for a in x]
    P(a) = P1(a**2)+a*P2(a**2)
    x2 = set [(a**2)% for a in x]
    y1 = eval(P1,x2)
    y2 = eval(P2,x2)
    return map [a : (y1[a**2]+a*y2[a**2])% for a in x]

Tada!

It turns out that the number of different values of $x^{2^k}\ \%$ is approx. $mod/2^k$, and since the degrees of polynomials $P_1,P_2$ are halved everytime you go deeper in the recursion, the time complexity is $O(mod\log^2{mod})$.

That second logarithm is annoying, but we can improve it by using the fact that the set $x2$ depends only on recursion depth and not on the polynomials, and then the small value of $mod$ to replace map access (by value) with array access (by index). It's sufficient to use two arrays for each recursion depth, then, which gives us $O(mod\log{mod})$ in both time and memory.

BTW, difficulty Simple? ( ͡° ͜ʖ ͡°)

link

answered 20 Jul '16, 01:48

xellos0's gravatar image

7★xellos0
5.9k54292
accept rate: 10%

Hi Xellos0, "It turns out that the number of different values of $x^{2^k}$ % is approx $mod/2^k$", this fact you can prove directly using FFT. Instead if you see the pseudo code that I have shown in the editorial, it directly maps to yours except the generator part, which can be omitted too if one wants :)

(20 Jul '16, 02:58) dpraveen ♦♦4★
2

Oh, yeah, it is. I just didn't think of FFT at all, expecting it to have a "simpler" solution, wrote a a bruteforce and modified it until it passed.

(23 Jul '16, 20:06) xellos07★

As always, the links to Setter's and tester's solution aren't working! Please look into it. Thank you

link

answered 19 Jul '16, 23:34

shariquemohd's gravatar image

4★shariquemohd
17417
accept rate: 11%

Can anybody explain this part of the problem setter's solution:

pw[0] = 1;
for(int i = 1; i < (1 << 18); i++)
    pw[i] = (pw[i - 1] * root) % mod;
for(int i = 0; i < (1 << 18); i++) {
    ans[pw[i]] = a[i];
    ans[pw[i] * 10 % mod] = b[i];
    ans[pw[i] * 100 % mod] = c[i];
}
link

answered 24 Jul '16, 20:23

sdnr1's gravatar image

6★sdnr1
111
accept rate: 0%

edited 24 Jul '16, 20:23

Not able to access any solution.Please update the links.

link

answered 19 Jul '16, 23:34

abhibansal53's gravatar image

2★abhibansal53
1
accept rate: 0%

Just asking, was anybody able to solve this using general multipoint evaluation ?? Or is it even practically feasible for this problem ?

link

answered 21 Jul '16, 20:04

divyansh13's gravatar image

4★divyansh13
61124
accept rate: 0%

@dpraveen ♦♦ In line 116 in your code, you have done REP(add, 3), when add is the name of the function you have used to add modulo mod. It's creating a confusion, please replace it with another variable name.

link

answered 28 Jul '16, 12:45

sahilarora.535's gravatar image

4★sahilarora.535
1235
accept rate: 0%

Heading ##Can anyone explain step-by-step the functioning of fft function in setter's soln ??

And also the importance of 786433 ??

Explanation with an example would be helpfull

I am new at this

link

answered 14 Aug '16, 10:20

siddhantg's gravatar image

4★siddhantg
1
accept rate: 0%

edited 14 Aug '16, 10:24

Why is it needed to decompose in 3 polynomials ?? Can we concat 2^18 zeroes so that final polynomial becomes of 2^20 numbers which is perfect square and do NTT?? @n1t1n_153012

link

answered 17 Mar '17, 22:15

manjunath1996's gravatar image

4★manjunath1996
1287
accept rate: 8%

edited 17 Mar '17, 22:28

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,643
×1,173
×334
×142
×22

question asked: 19 Jul '16, 22:47

question was seen: 7,007 times

last updated: 17 Mar '17, 22:28