the 25 prime logic was very good trick in this problem…otherwise TLe
can there be overflow in the cumulative frequency if each of it’s elements is int? Also when I logically declared my data-types i got WA solution1and when I changed everything to long long it got accepted solution2. Can any one please tell the reason or point out where is the overflow in the first program? Thanks in advance.
Again, posting here for help…
I’m stuck with this problem. For some test case no. > 100, it’s giving me SIGSEV runtime error…I’ve tried every corner case I can think of…still not getting any leads…
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.