Can someone explain the solutions for the problems WORKCHEF and POLYEVAL in July16?
WORKCHEF can be solved using digit dp.
Let F(x) be the number of numbers from 1 to x satisfying the condition of the question.
Then for the range [l,r], the answer is F®-F(l-1).
The dp portion–Start from the most significant digit, you need to keep 3 things while recursing from the most significant digit to the least significant digit.
A) the digits from 1-9 present in the current number(this can be done using a mask (0-511)).
B)the modulus of the current number 2520(the LCM of 1,2,3,4,5,6,7,8,9). this allows us to calculate the modulus of the current number with all of 1,2,3,4,5,6,7,8,9
C)Is the current number(consisting of the first n significant digits) less than the desired number or equal at that state.If less then adding any number from 0-9 cannot make the current number larger than the desired number because we are starting from the most significant digit.
Ifcurrent number(consisting of the first n significant digits) is equal then we can only add from 0 to the (digit equal to that of the desired number)-1, if for the next state the number has the be lesser.
We can add the (digit equal to that of the desired number) and set isequal state to be true
Finally when we reach the state of n significant digits where n is equal to the number of digits in the desired number then we evaluate using the mask and the modulus 2520, the digits present in that number and
the divisibilty with those digits retuning 1 if the number meets the condition
5 Likes
I had a similar solution before but it got tle so I had to use an optimisation. I worked modulo 504 and considered digit 5 separately. Any idea how can I make my tle solution pass the final subtask? https://www.codechef.com/viewsolution/10790386
Polyeval problem can be solved in NlogN complexity using NTT(Number Theoretic Transform). NTT is a version of FFT where instead of using complex numbers , we use a generator (say g) in our FFT algorithm.
If you are uncomfortable with cube root of unity and FFT , I would advise to be thorough with it (you can learn it from any source of your choice) and then learn NTT else it would be difficult. The most general algorithm for FFT is Cooley-Tukey algorithm. The one problem here is that the famous version of Cooley-Tukey algorithm is devised for numbers equal to power of two. Here, we are given a field which is not a power of two.First of all,the answer to x=0 will always be the constant in the polynomial. Then to handle the rest of query which can be from 1 to 786432, it is easy to notice that 786433-1 = 786432 = 2^18 * 3…which is a highly composite number…keeping this in mind , we can apply the mixed - radix algorithm by padding(extending) the polynomial upto 786432 terms. Then , suppose our polynomial is:
A0 + A1x + A2x^2 + A3*x^3 +…
We can divide the polynomial into three polynomials by grouping coefficient as (A0,A3,A6,…),(A1,A4,A7,…),(A2,A5,A8,…)
Let P1(x) = A0 + A3x + A6x^2 + …
P2(x) = A1 + A4x + A7x^2 + …
P3(x) = A2 + A5x + A8x^2 + …
Answer for our final P(x) = P1(x^3) + xP2(x^3) + x^2P3(x^3)
Now, note that P1(x), P2(x) , P3(x) all have 2^18 terms and hence can be solved using classic cooley tukey algorithm for powers of two.
NOTE ON CHOOSING THE GENERATOR G:
In an FFT algorithm , the generator is a complex number(w) also called the nth cube root of unity.
It has the property w^n = 1 where n is the number of terms to be used in the FFT. This FFT’s output gives value of polynomial at P(w^0),P(w^1),…P(w^n).
In our modified FFT algo(NTT) , we use g such that:
g^n p = 1 , here p=786433 and we choose n=p-1 so that we can cover all elements from 1 to 786432
So, g^(p-1) p = 1 for any number.
Now , we need to choose our g such that there is a bijection between (g^0 to g^(p-2)) and (1 to p-1) so that all the evaluations at P(1)…to P(p-1) are satisfied.
This is satisfied by g if it follows the Lagrange Theorem, where g^(n/r) % p != 1 for every prime factor r of n. Here n = 786432 and its prime factors are 3,2. So now we can easily choose our g and use it instead of w in our Cooley - Tukey Algorithm(which you can learn from the source of your choice)
But remember the g is for 786432 so it should not be used for FFT of 2^18. There we will have to use g’=(g^3) % p as our basic generator since we want P1(x^3) , P2(x^3), P3(x^3)
6 Likes
Nice explanation! I will try to implement it my way and if i get stucked somewhere i will drop a comment
1 Like
for sure…if you need more help, comment
I also have similar solution but I kept all the remainders mod 2,3,4,5,6,7,8,9 in a string of length 8 lol. I got AC with max running time of ~4.6s with a lot of optimizations.
Great explanation !
1 Like
For POLYEVAL:
I did not use FFT / NTT in this problem. 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.
Can You please provide a link or explanation to Lagrange’s Theorem.?? “Now , we need to choose our g such that there is a bijection between (g^0 to g^(p-2)) and (1 to p-1) so that all the evaluations at P(1)…to P(p-1) are satisfied. This is satisfied by g if it follows the Lagrange Theorem, where g^(n/r) % p != 1 for every prime factor r of n.” in reference to this line.
1 Like
Search about primitive roots.
You need a to know group theory to know Lagrange’s Theorem:
http://web.science.mq.edu.au/~chris/techniques%20of%20algebra/CHAP14%20Lagrange’s%20Theorem.pdf
Here you will find detailed explanation of Lagrange’s Theorem.
What you want to know basically is:
According to Lagrange’s theorem:
In a finite group the order of any element will be a divisor in the order of the group. Here, order of group is number of elements in the group.
Therefore an element a is a generator of the multiplicative subgroup of Fp
with n elements iff
a^(n/r) = 1 mod p for every prime factor r of n.
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??