my logic is same as the editorial,but it gives TLE.
http://www.codechef.com/viewsolution/3914314
please can someone guide me where i might be wrong
please check submision id 4099624,itās giving wrong answerā¦ CodeChef: Practical coding for everyone please say why itās wrong? On which test case itās wrong ???
I have used precalculation technique . For ex. let 1 2 3 4 5 be array .
Then through precomputation i have made another array . 1 2 6 24 120 . After that in order to cal any query it is :- arra[m]/arr[l-1] where l is lower rage and m is upper ā¦ Is my approach wrongā¦ getting WA many times Could someone help me out. Solution is :- CodeChef: Practical coding for everyone
Please help me out. Tried every optimization I could think of!
What is wrong with this code?
I am getting WA.
Will the segment tree approach work?
I tried but its giving WA.
can anyone help me with the following code. why is it not working i canāt seeā¦please.
https://www.codechef.com/viewsolution/15878086
I got AC only when I converted the exponentiation function from a recursive method to an iterative one. What could be the reason for this?
can anybody whatās wrong in my logic.I am getting wrong answer
I donāt see how D&C would apply to this problem, furthermore per query time complexity after all those pre-computation should be O(25) = O(1).
solution(l, r) = solution(l, m) * solution(m,r), where m is (l+r)/2
something like that should be D&C, the simplest one.
and you are wrong about O(1), it is O(lg n), you have forgotten fast squaring ā¦
I can up to that idea 2, but this idea give me WA if Iām correct, most probably duo floating point precision problems.
Time is not independent to constants. This was time tight solution, and you must use prime decomposition in order to get AC. You did 4 time more job, and your solution was 4 time slower. Usually it is not the problem, but in this problem, 4 times slower running time is a lot.
Truth is, that I didnāt get accepted yet, but I donāt think that there is precision problem. Iāll let you know, when (if) Iāll get AC 
1 Like
Itās probably because your power function is recursiveā¦make it iterative and submit it againā¦Happened same to meā¦
Very tight Time Limit Constraintā¦
Even I thought of segment trees. But then, for each modulo, creating a separate segment tree is wasteful. Having a segment tree with big integers is also wasteful (and probably give memory error).
But I noticed that there are no changes in the array to be made. So, if i have an array prod of bigints, so that prod[i] = product of all number from a[1] to a[i], then product from a[l] to a[r] could be found in O(1) as prod[r]/prod[l - 1]. But the time required to do the math with bigints was too costly, and i got a lot of TLEs.
I, however, managed to find the idea of primes and got an AC.
The O(25 log N) solution takes only 1/4-th of the time that O(100 log N) solution takes. So, that is obviously way faster. Many, I think, failed to figure that out! 
1 Like
I crack this problem in my first attempt 
2 Likes