I would not always say to avoid recursive ones, but constraints were too tight for this problem. Iterative is a little bit faster, for ur power left function.
U may try making it iterative.
Try using arrays in place of vectorsā¦
Hopefully that works because arrays tend to be faster than vectors.
Mate, ur complexity may be QlogN, but in some problems, u also have to take care of constant factor associated, which i believe, is the reason of tle.
are you going to do part 3 as well?
@codent47 Always consider using iteration instead of recursion wherever possible. Infact you can do that for all your three power functions, I am pretty sure, it would pass then. And also consider using Fast I/Os in such questions where TL is too strict.
Also try using arrays instead of vectors, vectors are a bit slower than arrays.
1 Like
I read the comments and came to know that many people were doing the same thing as suggested in the editorial,but still getting TLE.
I was having the same problem during the contest. And finally the only thing which solved my problem was 1-based indexing.
Because of 1-based indexing the if-else condition in query part (for checking left > 0 or not) can be avoided and hence the total time will decrease by some factor within the query. And there you go AC. Hope it helps 
For reference check by submissions :
2 Likes
Honestly, I feel that setter and tester were extremely wrong in setting the time limit. I wonder how much time setterās code takes to run, cause if its something like 3.8-3.9seconds, then time limit is wrongly put.
Saying because, languages like java etc. got accepted (time bonus), while c++ got tle.
1 Like
Can anybody tell me why my this code got WA for CSUBQ problem? It was a just simple algorithm to pass first two test cases by seeing the pattern but it failed donāt know why. link
Nice use of binary search. @eugait
Really @vijju123??
Is this the case?? Are the solutions with same approach but different languages are getting different verdicts?? This is a matter of serious concern as this would cause unfair advantage to some. I would really hate this if something of this sort happens.
I guess this need strict action. Perhaps it should be made responsibility of problem tester to solve the problem with same approach using c++, python(PYPY or CPYTH) and Java, for these three languages are most popular ones. Hope this matter wonāt go unnoticed.
Maybe vectors are the reason. Rest i didnāt exactly got the gist of your solution. Maybe u should try same solution using arrays, or add a bit of explanation about ur approach
I am not able to solve any of the last three problems (full solution). But i have texted someone to explain me approach of POLY. Whenever that person replies, iāll solve the problem and then write editorial.
Waiting for that personās reply.
If you can find anyone willing to explain his approach to me, i would be glad to write an editorial on any of last three problems and give him due credit as well.
I have done everything that is told in the tutorials and still getting tle. Can anyone suggest any modification?
solution: https://www.codechef.com/viewsolution/16269941
Thanks in advanceā¦
Setterās solution runs in 2.5 secondsā¦horror
@vijju123, Unluckily, That person got some unavoidable reasons, keeping that person busy, because of which I cannot do an editorial on POLY unless anyone else is willing to help me.
Sorry for inconvenience.
@taran_1407 you donāt necessarily have to make 2 segment trees. Since the working of the 2 segment trees is exactly the same, I made a class for segment trees and used 2 objects of that class as mentioned above. It made the code look clean and simple. Hereās the code.
Mate, i too used one segtree only. Thanks for sharing.
1 Like
just see that minute difference in my code to get rid of TLE in task 9.took me 8 hours of continuous effort to find it.
TLE https://www.codechef.com/viewsolution/16259177
AC https://www.codechef.com/viewsolution/16260183
just replaced x with s new variable and it worked!!
1 Like
I would like to describe the fastest solution for SEGPROD that I came up in O(N log N + Q). Letās use SQRT-decomposition and divide array in sqrt(N) buckets of size sqrt(N), for each bucket letās calculate product for each prefix and for each suffix. And for each pair of buckets x <= y letās calculate a product of all elements between them in buckets F[x] * F[x+1] * ā¦ * F[y], where F[i] - product of elements in i-th bucket. All these operation can be done in 2*N+sqrt(N)*sqrt(N) = 3*N ticks. Letās answer for queries, suppose that l and r not in the same bucket, hence answer can be calculated in O(1) <-> use some precalculated suffix production in l-th bucket multiply it by some precalculated prefix production in r-the bucket and multiply all of it by precalculated F[idx(l)+1] * F[idx(l)+2] * ā¦ * F[idxĀ®-1], where idx(x) denotes number of bucket where x is placed. But what if l and r in the same bucket? We can use SQRT decomposition one more time!! Letās split every bucket into sqrt(sqrt(N)) buckets, and for every bucket-bucket will precalculate the product on the prefix, on the suffix and product for every pair of bucket-buckets inside the bucket, now we have 6*N operations, letās split every bucket-bucket into sqrt(sqrt(sqrt(N))) buckets and for every pair of bucket-bucket-bucket use the same procedure as above. Then if query is in the same bucket-bucket-bucket(, r-l <= sqrt(sqrt(sqrt(N)) ~ 5, and we can find the production simply. T(N)=3*N+sqrt(N)*T(sqrt(N)) for precalculating and answer in O(1)
7 Likes