Biggest Brain Moment was the biggest oof for me personally. I think i need this entire time before the next LC just to grasp and implement this question only.
1 Like
This problem is trivial if you can do a1729 dimensional fourier transform.
I scribbled 50 pages of notes on my notebook before giving up and going for the plain O(n^2) complexity solution.
ā(Pi - Pj) For all 1<i ,j<N i!=j can also be evaluated. By divide and conquer in a different way.
Building sub-product tree built during multipoint evaluation. Then sending for computation of the left child to the right node for multipoint evaluation. P for evaluation in Q
P =ā( x-pi) 1 < i <= n/2 with
Q= ā( x-pj ) n/2+1 < j <= n.
Similarly throughout the sub product tree . Going down for every left and right child. So
T(N ) = 2 T( N/2 ) + N * (log N) ^ 2
Here N is 4e4 because you donāt have to calculate the last node. and there are multiple NTTās involved in each single step that gives a very heavy constant to each step.
Now many of you may think this is straight forward TLE. But that is not the case if you doing everything right. Like first off not copying template of someone else.
This is mostly involves optimization of multipoint evaluation so if you donāt actually know how it works it would be hard for you to understand.
-
Writing NTT Fully optimized with roots precomputed.
-
Middle product optimization while calculating inverse. Exactly N size NTTās are used instead of 2N.
-
And use of only 5 NTT for calculation of inverse. Cause one transformation is useless in between.
-
Using brute force for calculation of modulo when N< 120 to 250 cause even after optimization modulo operation consists of 11 NTT ( 5 Inverse + 6 later) . Which gives a higher constant when n is small. So brute force is better.
-
If left and right children are small in number say of order of 100 then directly calculation of P*Q for all the iās and jās in N^2 .
CodeChef: Practical coding for everyone Submission with 2.08 sec. I donāt know if it was intended by the setters to be solved like this or not.
Thatās how you do it bois.
And who said It is O (N * ( log N ) ^ 3 ) I donāt know how to calculate the complexity but computation of sub-product tree is N * 2 log N. The Next complexity Iām not sure I donāt actually know how to solve this T ( N ) = 2 T( N/2) + O ( N * ( log n ) ^ 2 ) But Iām quite sure it is not ( N * (log N ) ^ 2) Correct me if Iām wrong . It is just that it is having a very very very high constant. Because of the 11 or 12 NTTās involved at each stage. And 12 is very close to 17 which is actually another Log N I guess 
. But optimizing it hard enough to get an AC with this evil complexity is one way to go. By the way I donāt understand why sending Fā ( x ) for multipoint evaluation in F ( x ) gives the answer for each point it would be great help if someone explains it in detail.
5 Likes
Good job. This is exactly the approach mentioned by me above, also explored by other folks too. However, I didnāt know that it is possible to optimise it so heavily so that it gets AC.
1 Like
Well thereās your AC solution. Under TL. 
1 Like
With regards to your doubts on the time complexity, there is a version of the Master Theorem for solving recurrences, which states that if we have:
T(n) = a.T(\dfrac{n}{b})+f(n) and f(n) is \Theta(n^{log_ba} . log^k(n)), then the solution for
T(n) is \Theta(n^{log_ba} . log^{k+1}(n)).
So your recurrence is exactly \Theta(N.log^3N).
Awesome Man. God level Math. JEE revisited.
I did manage to implement a O(n*log^2(n)), solution, but it was nowhere near the required time complexity. Its very easy to understand and quite trivial. However, it just doesnāt run in 2.5 seconds. If the time limit was 3 seconds, maybe it would have passed. Here it is. Actual code starts from line 569. We just interpolate a polynomial, differentiate it and the take product of itās multipoint evaluations.
1 Like
I used the fact that this problem can be reduced to finding the square of the product of all the contiguous subarrays of an array. We first convert the product that we want into this product of all contiguous subarrays by multiplying(and dividing) by an appropriate number of Xās ((n-1)n(n+1)/3 to be exact.
Then finally, finding square of product of all contiguous subarrays is just interpolating a polynomial f, whose zeros are exactly the elements of the negative cumulative sum array of the modified array. Differentiate f to get fā and evaluate fā at exactly those points at which f was interpolated and voila you magically get the required product. My mind was blown at this moment. Do this with a pen and paper if you havenāt been able to follow.
I just failed at optimizing my code. It was really close though. I tested it a lot on my PC and it was close to 2.5 seconds, but alas codechef gods didnāt bless me.
Can some one please tell me where do people get fast libraries from? I always struggle with this.
I am a beginner to competetive programming. Can any one please tell me how to implement operations on polynomials. I mean do we need to write the code from scratch or is there any inbuilt library to do so.
I use this library. There a link to a github repo in there. Check it out. Its not optimized a lot, but gets the task done in most cases(Not for this task though, the TC were too strict)
I want to know how to use this library. Do I need to copy the code?
Check out my first message in this topic. It contains link to my submission which will help you see how this library is used.
Is there any video explanation available for this problem ??
please click on the links given in the editorial
Hey, the links are definitely good resources to learn stuff but the library is not very efficient. I saw some people used other libraries in the contest, so asked the question.