Optimizations at it’s peak.
This Long Challenge was a complete lesson of Time Complexities. 
1 Like
Time complexity ignores constant optimizations 
This Problem taught me that division is a costly opertaion
@vijju123 I got passed in 0.66
I feel it is because of the way you are using difference arrays
i used one division operation though
You can see my solution if you want-> https://www.codechef.com/viewsolution/23337676
Can this be done in O(N log(N))?
We use the fact that circulant matrix multiplication with a vector is fast if we use FFT. I could do it if instead of the floor function, there was normal division(floating points). Any known fix for this? This constraints at first glance seemed to be asking to implement this O(N log(N)) solution
2 Likes
I learned that it is bad to use ceil… even wrote in the solution https://www.codechef.com/viewsolution/23438371
Agreed. Either the TL should have been more relaxed, or they should have included testcases for maximum constraints.
Yes, please can someone tell if we can do some trick for floor function for using FFT or karatsuba?
have a look at my solution: it taking 1.5*10^8 loops in the worst case, with three divisions
Codechef is cheating xD
I just created a sample input with maximum constaints (with random arrays). Tester’s solution takes 2.056 secs, but mine is 0.4 secs (Code::blocks execution time). A little partial score would be nice. Here is my easy solution on C++: https://www.codechef.com/viewsolution/23560514
1 Like
I did something similar to this. Made use of the fact that the floating point division can at max be larger than the floor division by N. But I couldn’t get an AC on all test cases. TLE on 2 while all others passed in 0.23.