REALSET - Editorial

editorial
, , , ,
21

Really awesome explanation @kevinsogo, I am always amazed by how clever and insightful some top coders can be and this is for sure an inspiration for me to keep working harder on my side to improve :smiley:

Thanks for the amazing story :wink:

3 Likes
22

jaskaran: Except it does not work for {1,1,0}. Read what I wrote again. Your solution answers YES, the correct answer is NO.

23

waw. amazing explaination throughout your trials and errors. thanks a lot, mate !

i’ll try to get AC with your ideas. thank you so much !

2 Likes
24

@kuruma @cyberax Thank you for your comments! I’m glad you liked the post. :smiley:

1 Like
25

@cyberax I will try to explain these questions more clearly and thoroughly. Thanks for your concerning.

1 Like
26

xelios:Why is it giving NO on my compiler but not on IDEONE?

27

@shangjingbo: thanks a lot.

28

@cyberax: updated :slight_smile:

4 Likes
29

Just a note when multiplying two polynomials quickly.

Assume we want to multiply f(x) and g(x) exactly, using FFT. Using double-precision and using e2πi/n as the primitive nth root of unity is too risky because precision errors are very likely to come up.

An alternative is to choose a prime p with a modular 2kth root of unity for a large enough k (i.e. 2k > deg f + deg g) and just calculate f(x)·g(x) (mod p), but instead of using e2πi/n, we use a modular nth root of unity mod p. This avoids precision errors, but an obvious problem is that the coefficients of the product will be reduced mod p.

But let’s say we know that any coefficient of f(x) can have an absolute value of at most F, and any coefficient of g(x) can have an absolute value of at most G. Then we are sure that any coefficient of f(x)·g(x) can have an absolute value of at most F·G·(min(deg f, deg g)+1) (let’s call this quantity M).

So a strategy to calculate f(x)·g(x) exactly is:

  1. Choose a series of primes p1, p2, …, pl such that they all have a 2kth root of unity for a large enough k. Choose enough primes so that p1·p2·…·pl > 2M.
  2. Find f(x)·g(x) mod p1, f(x)·g(x) mod p2, …, until f(x)·g(x) mod pl.
  3. Use the Chinese remainder theorem to reconstruct f(x)·g(x) exactly. Note that you should choose the coefficient with the least absolute value, so you should choose the negative value if necessary, if it has a lower absolute value.

Note that since we have p1·p2·…·pl > 2M, any number has at most one representative modulo p1·p2·…·pl having absolute value ≤ M. Hence, the constructed coefficients are guaranteed to be correct.

If in case you need to calculate f(x)·g(x) modulo some prime P, but you don’t have a control over what P is, then most likely there wouldn’t be a 2kth root of unity mod P, so FFT mod P wouldn’t work. A viable strategy is to calculate f(x)·g(x) exactly first as above, and then reduce it mod P afterwards (I actually used this trick for REALSET, somewhere in this submission. MOD0 and MOD1 are the two primes I chose).

4 Likes
30

I don’t know your platform, so I can’t answer that… but I’d expect the Ideone to be more similar to Codechef testing system…

31

My solution check whether polynomial is divided by Cyclotomic Polynomial order m where m is divisor of n. We just need to check that P(x) * Product[x^(m / d) - 1] mod (x ^ m - 1) == 0, where d is prime divisor of m.

1 Like
32

Precision is usually not a problem. Ever. Out of hundreds of problems that require doubles among thousands I’ve solved, this is the 2nd one where I’m getting WA because of precisions errors.

33

I’ve updated editorial with the detailed explanation of the fastest solution.
The first thing I’ve made after the contest was to understand this solution.
Now I see that I should be more lazy :slight_smile:
It is to better to think more before proceeding to complex algorithms like fast polynomial division.
I’ve spent 10 hours on Sunday to optimize it well enough.
Actually test data are weak and I could easily fail my solution by TLE :stuck_out_tongue:
At some point I even implemented half-GCD based O(n * log2 n) algorithm for calculation of GCD of two polynomials
(see http://cs.nyu.edu/~yap/book/alge/ftpSite/l2.ps.gz for an amazing explanation) but as kevinsogo I gave up with it as well.
The final optimization that allows me to pass is caching DFT values. Since we need to divide P(x) by several polynomials we will calculate its DFT several times. So I saved it and reuse afterwards.

2 Likes
34

@anton_lunyov: thanks for you explain!

35

sum of d * nu(d) is O(n * log(n), because sum of d is O(n) and max(nu(d)) is O(log(n)).

36

thank you for the update ! i tried to understand what did that check() function too… :slight_smile: well done !