×

# REALSET - Editorial

Author: Iaroslav Tverdokhlib
Tester: Mahbub
Editorialist: Jingbo Shang

Hard

Circulant Matrix

# PROBLEM:

Given a Circulant Matrix, determine whether it is full rank (i.e. non-zero determinant, or the null space is trivial).

# EXPLANATION:

First of all, we need to know the matrix stated in the problem is a very special type of matrix called Circulant Matrix. There are a lot of properties about the determinant and rank of Circulant Matrix can be found in Wikipedia.

Let's summarize the properties looks relevant to this problem:

where, f(x) = A0 + A1 * x + A2 * x^2 + ... An * x^n.

To avoid the precision problems, we can choose some prime and one of its primitive root instead of the root of unity (it may have chances (really rare, but exists) to fail, but we can choose some different primes to check, e.g. 3 different primes). Also, it will better to try Number Theoretic Transform instead of double-valued FFT in the following steps.

One straight-forward way is to calculate the determinant directly (of course, using FFT or NTT, both setter and tester solved the problem in this way). But a lot of contestants failed due to the precision problem when checking whether a double value is non-zero.

Another way is the check whether "d = 0" i.e. gcd(x^n - 1, f(x)) is some constant. Here we take the later one to solve this problem. Another related knowledge is about Cyclotomic Polynomial.

With this property, we know that x^n-1 can be factorized into some cyclotomic polynomials Phid(x) for every divisor d of n. Actually, for all n between 1 and 30000, the number of divisors, denoted as D, is at most 96 (when n = 27720). Therefore, we can enumerate all possible divisors d and check the cyclotomic polynomial Phid(x) can divide f(x).

Then, the only thing we need to do is the polynomial remainder operation. If we adopt brute-force to do this, it will take O((N-d) * d) time. Directly applying this method (with some breaks) may get TLE. But there is a interesting view to combine this method with the double-valued FFT (like this method can work well when N is a prime). This solution accepted with a further check using this method.

## The fastest and easiest solution (explanation provided by Anton Lunyov)

Let's understand how the fastest and shortest solution to this problem works.
As pointed above we need to check that our polynomial is divisible by Phid(x) for some divisor d of n. Instead of direct calculation of Phid(x) we can do the following trick. Let d has prime divisors p1, ..., pk. Now the crucial observation is the following:

Some polynomial P(x) is divisible by Phid(x) if and only if P(x) * (xd/p1 - 1) * ... * (xd/pk - 1) is divisible by xd - 1.

It follows from explicit formula for cyclotomic polynomial (see second formula there). Indeed the rational function
(xd/p1 - 1) * ... * (xd/pk - 1) / xd - 1
equals to Qd(x) / Phid(x) for some polynomial Qd(x) that is coprime to Phid(x) which yields the result.

Now all is simple. Polynomial computations modulo xd - 1 are straightforward: if P(x) = a0 + a1 * x + ... + am * xm then P(x) mod (xd - 1) = (a0 + ad + a2d + ... ) + (a1 + ad+1 + a2d+1 + ... ) * x + ... + (ad-1 + a2d-1 + ... ) * xd-1 (for clarity see lines 49-50 here). Multiplication by xk - 1 could be made by simple loop and requires only additions and subtractions. And it could be done modulo xd - 1 at the same time (see lines 53-62 here).

So we could easily find the remainder of polynomial division P(x) * (xd/p1 - 1) * ... * (xd/pk - 1) by xd - 1. If it's zero for some d then the answer is YES, otherwise NO.

The complexity of each step is O(n + d * nu(d)), where nu(d) is the number of prime divisors of d. Here we have n because we need first to adjust P(x) modulo xd - 1. Thus, overall complexity is (n * tau(n) + n * log n), where tau(n) is the number of divisors of n. Here n * log n is some estimate of the sum of d * nu(d) over divisors o n (I believe it is so :)). Hence we get super fast and simple solution that requires only additions and subtractions of polynomial coefficients.

Any different ideas and solutions are welcome.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

161446375
accept rate: 0%

19.8k350498541

8

I don't mean to be rude, but this is not what can be expected for an editorial for a HARD problem. There are many concepts to be explained, many difficulties around (how you come to fast discrete fourier transform, how you use the Bluestein to handle cases where N is not a power of 2, how you handle floating point numbers precision, how you handle overflow in recursion, and so on), and you only provide a wikipedia link... I could have done the same. Telling that we can read other contestants code is not a solution, it's a lazy way of not answering the question. I'm kind of disappointed.

(16 Dec '13, 22:56)
2

I think the editorial is in the process of being written, so you shouldn't flame just because you're impatient...

I mean, I hope it is so...

(16 Dec '13, 23:48) 7★
1

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

(17 Dec '13, 10:22)

@shangjingbo: thanks a lot.

(17 Dec '13, 13:07)
4

@cyberax: updated :)

(17 Dec '13, 16:42)

@anton_lunyov: thanks for you explain!

(18 Dec '13, 13:25)

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)).

(19 Dec '13, 09:27)
showing 5 of 7 show all

 9 I initially implemented FFT on real numbers (double, then long double), but I always had precision problems (actually, to be honest, since I was too lazy to implement an FFT algorithm working for any value of N, e.g. N being prime, I used a freely available implementation of Bluestein's FFT algorithm). But I had to implement something very different in order to have my solution accepted. If you think of the values A(i) as coefficients of a polynomial (A(0) + A(1) * x + A(2) * x^2 + ...), then the answer is YES only if this polynomial is divisible by a cyclotomic polynomial Phi_D(X) for some divisor D of N. My implementation of this idea is actually straight-forward: I computed all the cyclotomic polynomials for divisors of N and I checked divisibility with each of them. The important thing here is that cyclotomic polynomials have integer coefficients, so there is no need for using real numbers (thus, any possible precision errors are avoided). answered 16 Dec '13, 21:19 10.0k●26●69●90 accept rate: 18% I also implemented Bluestein's algorithm, also using long double and also had trouble with precision (running time 19 seconds, WA). This problem was probably aimed at failing any common FFT. (16 Dec '13, 21:24) xellos07★ if the polynomial is divisible by a cyclotomic polynomial Phi_D(X) for some divisor D of N.Could you explain that? (16 Dec '13, 21:28) @jaskaran_1: See Wikipedia for the definition and properties of cyclotomic polynomials: http://en.wikipedia.org/wiki/Cyclotomic_polynomial (16 Dec '13, 21:55) @mugurelionut how about using Number Theoretic Transform? (16 Dec '13, 23:33)
 5 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: 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. Find f(x)·g(x) mod p1, f(x)·g(x) mod p2, ..., until f(x)·g(x) mod pl. 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). answered 17 Dec '13, 20:36 1.7k●5●86●142 accept rate: 11% 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. (18 Dec '13, 05:47) xellos07★
 2 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 :) 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 :P 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. answered 18 Dec '13, 12:14 6.7k●62●119●138 accept rate: 12% thank you for the update ! i tried to understand what did that check() function too... :) well done ! (19 Dec '13, 23:33)
 1 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. answered 18 Dec '13, 05:05 130●4 accept rate: 0%
 0 I did the same thing.Find the fft of the n real inputs ie c0,c1,c2,.....,c(n-1) as mentioned in the circulant determinant link. .Now check for each output bool flag=0; for(int i=0;i
 0 This was a frustrating problem. I think the main issue was I had a lot of precision issues, but it was frustrating because I wasn't sure how to modify it to not use doubles (and some accepted solutions even used doubles). During the contest, I thought the fact that the solutions had to be integral made my algorithm wrong, so I wasn't able to come up with an easy fix, which lead to me ultimately giving up on this problem. It was definitely a cool problem. I just have some quick followup questions though. Does the fact that B has to be integral matter? How difficult is it to actually reconstruct a sequence B that works (if one exists)? answered 16 Dec '13, 23:10 7★lg5293 511●2●14 accept rate: 10% 1 Nope. If there's a solution in complex numbers, there's one in integers as well. Proof (a bit short, there's not much space in comments :D): a solution in complex numbers is a pair of solutions in reals that means we can take just the real parts of b-s if there is a solution (in reals now), we can obtain it by running GEM on the above mentioned circulant matrix, but GEM can be performed in rationals only, which gives us a solution in rational numbers if vector B is a solution, kB is also a solution; choose k to be the product of all denominators, and kB is a solution in integers (16 Dec '13, 23:46) xellos07★ Cool thanks :) I was only able to get step 1, but wasn't able to convince myself of step 2 during the contest. It's much clearer now. (17 Dec '13, 00:08) lg52937★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,680
×1,343
×1,186
×334
×16

question asked: 16 Dec '13, 18:56

question was seen: 8,067 times

last updated: 26 Dec '13, 15:22