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

×

can someone share their Approach to POLYEVAL?

I was astonished after seeing this problem as this problem basically asks to calculate the convolution of the given polynomial with a constrained K. I know about fast fourier transform to multiply two polynomial in O(nlogn) but there we used the idea of nth roots of unity in place of some random K, to reduce the input size by half in each level of recurrence. But, if we are constrained to choose a paricular K, how to sample N points in better than O(N^2)!!! Also what does it means to "design" a DFT which works on some particular Modulo?

asked 13 Jul '16, 15:41

sandeep9's gravatar image

3★sandeep9
4782827
accept rate: 4%

edited 20 Jul '16, 11:52

admin's gravatar image

0★admin ♦♦
19.8k350498541


Look at all possible remainders of $x^2$ modulo the given prime. How many different remainders exist?

Do the same with $x^4$, $x^8$ etc. How many remainders exist?

My approach uses this and it's almost brute force.

link

answered 13 Jul '16, 16:05

xellos0's gravatar image

7★xellos0
5.9k54292
accept rate: 10%

I did not use FFT / NTT in this problem. I used similar insight from @xellos0 's insight. I recursively decomposed a polynomial into four polynomials in terms of $x^4$ and used unordered_map to save the result for each decocmposition. I continued decomposition until I only have one term (constant term). The number of possible remainders when the function $x^4 mod 786433$ is repeatedly applied is reduced drastically every application which gives an opportunity for memoization / DP. I don't know how to prove this mathematically, but I tried creating a program which counts the number of possible remainder and indeed this is true for powers of two. Notice that the decomposition would produce a tree with four childs, and so I used 4-ary heap-like indexing. https://www.codechef.com/viewsolution/10762921

You can decompose a polynomial into four polynomials in this way:

$A(x) = A_{4k}(x^4) + x A_{4k+1}(x^4) + x^2 A_{4k+2}(x^4) + x^3 A_{4k + 3}(x^4)$

IN the formula above, $A_{4k}(x^4)$ are the coefficients that are multiples of $4$, $A_{4k+1}(x^4)$ are the coeffiients that are multiples of $4$ but $+1$.

We can also decompose a polynomial into $8$ polynomials in terms of $x^8$. I think I would have gotten faster running time if I used higher power such as $8$ because the number of remainders reduce even faster.

I hope the logic is sufficiently understandable, let me know if there is something unclear with my explanation.

link

answered 14 Jul '16, 01:29

mightymercado's gravatar image

4★mightymercado
2816
accept rate: 11%

edited 14 Jul '16, 05:04

A better solution with O(n (log n)**2) is given here: https://www.student.cs.uwaterloo.ca/~cs487/handouts/script07.pdf

I tried implementing this, however it was tle probably due to higher constants in multiplication in NTT/FFT. It was taking around 12 seconds for the worst case -_-

link

answered 13 Jul '16, 15:46

vsp4's gravatar image

6★vsp4
1.2k138
accept rate: 28%

edited 13 Jul '16, 15:48

Same approach is described in Cormen Book too. But it seems hard to code.

(13 Jul '16, 15:54) apptica5★

Please look here http://e-maxx.ru/algo/fft_multiply if you don't speak Russian (like me) use Google Translate.

link

answered 13 Jul '16, 19:52

damian_great's gravatar image

1★damian_great
1
accept rate: 0%

link

answered 13 Jul '16, 20:38

iamstg's gravatar image

5★iamstg
1064
accept rate: 16%

link

answered 13 Jul '16, 20:40

iamstg's gravatar image

5★iamstg
1064
accept rate: 16%

@xellos0 prime^1/2, prime^1/4 etc. right ? but stilll i didn't get it can you explain further ?

link

answered 13 Jul '16, 22:46

ashwanigautam's gravatar image

3★ashwanigautam
187213
accept rate: 0%

No prime, every x up to the modulo.

(14 Jul '16, 05:29) xellos07★
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:

×334
×4

question asked: 13 Jul '16, 15:41

question was seen: 2,544 times

last updated: 20 Jul '16, 11:52