EVENPOLY - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

HARD

EXPLANATION

Reduce all coefficients of the polynomial modulo 2 and view the polynomial as having coefficients in a field of size 2 (i.e. the field of integers modulo 2) from now on. Then the question becomes whether or not this reduced polynomial is identically 0 over this field. Now, if we try an assignment of 0/1 values to the variables, we can efficiently evaluate the polynomial by computing the determinant using any standard algorithm (e.g. Gaussian elimination) in O(d^3) time. If the determinant happens to be non-zero then the polynomial is certainly not identically 0.

Now, there are some polynomials over integers mod 2 that evaluate to 0 for all possible variable assignments while the polynomial itself is not identically 0. The first test case describes the polynomials x^2+x which has roots at both x = 0 and x = 1 (again, modulo 2). This is where the Schwartz-Zippel lemma helps tremendously. This lemma says that the fraction of possible inputs to a non-zero multivariate polynomial of degree d over a field of size F is at most d/F. If we extend the field from 2 elements to a field with 2^r elements for a suitably chosen r and view our polynomial as being over this field, then if we try random variable assignments from this larger field and compute the determinant, then the probability of the determinant being 0 when the polynomial itself was not is at most d/2^r. The maximum number of variables in any matrix entry is at most 100 and the size of the matrix is at most 100 so the degree of any polynomial is at most 10,000. Using r = 30 should be more than enough to essentially guarantee the right answer, especially if multiple iterations are performed.

For those who haven’t seen how to implement finite field arithmetic before, the elements of a field of size 2^r can be viewed as polynomials of degree < r whose coefficients are integers modulo 2 where arithmetic occurs modulo some irreducible polynomial of degreer. Inverses can be computed using Euclid’s extended gcd algorithm applied to polynomials over a field, though it is possible to solve this particular problem without using inverses. There are efficient algorithms to generate irreducible polynomials of degree r for any r > 0, but you could just hard-code one of degree 30. I found mine online.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.