PROBLEM LINKSDIFFICULTYEASY PREREQUISITESSimple Math, Repeated Squaring PROBLEMYou are given a list of N integers. Each value in the list is between 1 and 100. You have to respond to T queries of the following type
EXPLANATIONFor each query, iterating through the list between L and R to maintain the modular products is too slow. Of course, we use the fact that each value is between 1 and 100 to our advantage.
Each number has a unique prime factorization. The product of a set of numbers can also be simulated by adding up the frequencies of each prime in all numbers in the set. For example, suppose we have to multiply 36 and 45. 36 = 2^{2}3^{2} 45 = 3^{2}5 36 * 45 = 2^{2}3^{4}5 Thus, we can maintain a table of cumulative frequencies for each of the 25 primes between 1 to 100 for the given list of numbers. When processing a query
These ideas are best presented in the pseudo code below. PSEUDO CODEGiven: N, the number of numbers L[N], the list of numbers P[25], primes between [1, 100] CF[N,25], cumulative frquency for each prime The complexity of answering each query would be O(25 log N). Cumulative Frequencies can be calculated in O(25 * N). CODING COMMENTARYYou can either calculate the primes in thr porgram or hard code the array of primes by calculating it offline. The repeated squaring should take care of the fact that the exponent can be 0. a^{0} should return 1 for any a. Calculating the cumulative frequencies table should be done carefully. The frequencies of the primes for each number between 1 and 100 can be precalculated. Use these frequencies to build the cumulative frequencies table. SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 12 Aug '13, 15:19

Is the setter's solution not up? I am getting a "Page Not Found". answered 12 Aug '13, 16:47
"Page Not Found" when tying to access Setter' Solution
(17 Aug '13, 11:59)
@gamabunta Please look into this!
(28 Aug '13, 16:19)

D&C solution gives TLE. Complexity should be O(lg n) per query. Does anyone know why it is? Maybe in this approach MOD (%) operator is called fewer times... answered 12 Aug '13, 15:39
I don't see how D&C would apply to this problem, furthermore per query time complexity after all those precomputation should be O(25) = O(1).
(12 Aug '13, 15:41)
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 ....
(12 Aug '13, 15:49)
@kingarthurie: My bad :(
(12 Aug '13, 16:00)
If you're doing a naive D&C, query complexity would be Omega(n). Your recurrence would be T(n) = 2 * T(n / 2) + Omega(1). T(n) = Omega(n)
(14 Aug '13, 06:21)

Took me ages to figure the idea! My solution: http://www.codechef.com/viewplaintext/2511516 First, I had a go at it using Python and Java, thanks to the support for big integers. But they gave me TLE. Thinking "out of the box", I tried the naive method. Actually find all products (keeping the modulo) in the given ranges. That too, timed out obviously. Then I figured out that N is only as large as 100. Instead of storing the primes' frequencies. I stored the numbers frequencies itself. A complexity of O(100 log N) per query and O(100 N) for precalculations. But this welcomed me with a shower of TLES. Common, how else can I optimize? Multiplications... modulos... I thought of how to stop myself from looping, even the 100 times, just to avoid those computations. Couldn't find any better solution. I thought, I am having modular exponentiation. If somehow I could increase the exponents, by combining some numbers, then I could further optimize. But couldn't think of how to? One day, thanks to the fundamental theorem of arithmetic, I remembered the prime numbers. Actually, I thought of storing the counts of powers of 2, as counts of powers of 2 itself. And just like that, the thought extended. I was not much thrilled, as the complexity now will be O(25 log N), but notationwise, it is the same as O(100 log N), as both are O(log N). Still, I thought of 75% reduction in the running time. Coded it up, but tests in my local machine could only bring down the running time (on average) from ~8.5 seconds to ~2 seconds per file. And we needed 1 second. But there is nothing bad as not trying. So, I tried, and voila! It was accepted. That is my story of solving CHMOD. What I wonder? Would love to hear from people who cracked this at their first attempt itself. answered 12 Aug '13, 16:23
2
I crack this problem in my first attempt :)
(12 Aug '13, 16:51)
@sandeepandey What was your approach? Is it the same as the one discussed in the editorial?
(12 Aug '13, 16:55)
1
Yeah same approach. A(i) < =100 was big hint for me :)
(12 Aug '13, 17:06)
:D Right! Right! A(i) ≤ 100 was a hint for many (including me). But for me, the idea of prime numbers didn't click before there were a few TLEs. @sandeepandey Thank you for sharing!
(12 Aug '13, 17:12)
1
@tijoforyou same story here. Apart from the fact that A(i) ≤ 100 was a hint i figured out at starting :)
(12 Aug '13, 17:36)
1
Interesting. I used prime numbers in the first go and didn't even notice that storing freqs of 1100 could have been an alternative approach. To answer your question, I started solving the problem by looking at the segment products. I noticed that they'll consists of only primes from 1 to 100 and that's how I came up with the idea of storing prime frequencies. Thanks for this alternative view!
(13 Aug '13, 15:45)
@shantanuag Thank you for your inputs on this. :)
(13 Aug '13, 19:17)
showing 5 of 7
show all

The idea of my solution is to use segment tree to calculate sums in [L, R] interval for log10 values and later convert this to integer applying modulo operation. When I had such sum, first I found how many billions are in result (log10 / 9.0) exponentially multiplied this value and result multiplied with 10^dif where dif is something like real mod after dividing by 9.0 (hope it's clear). answered 12 Aug '13, 15:42
I can up to that idea 2, but this idea give me WA if I'm correct, most probably duo floating point precision problems.
(12 Aug '13, 15:51)
1
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 ;)
(12 Aug '13, 16:10)
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 I, however, managed to find the idea of primes and got an AC.
(12 Aug '13, 16:29)
Using Segment tree was my second approach as storing product of numbers in a product array table was my first approach but I was getting SIGFPE and then latter on WA on both the approaches. What I was thinking is the highest value of mod is 10^9 and during calculation of product or formation of segment tree, i was taking mod of 10^9 + 7 in order to maintain in the size in int.
(13 Aug '13, 08:56)
After then I thought perhaps this is not good idea so I implemented big integers in c++, this was my first handshake with big integers in c++, thanks to the problem I learned how to use big integers but still problems was not solved and got TLE's.
(13 Aug '13, 08:56)
there so much bilions in result such that owerflow in even long double : result = k * 1e9 + x ; result <= 1e200,000 so , k <= ~1e20000
(13 Aug '13, 20:37)
But when using log10, the max sum is 10.000 * 2 ;)
(13 Aug '13, 20:40)
showing 5 of 7
show all

I dont think this question qualifies as an easy one. It requires segment trees and modular exponentiation. Please consider moving it to medium. It took me 3 hours to get to the Algorithm. And only around 900 could solve it over the ten days. answered 12 Aug '13, 20:09
Segmented Trees ? Why do you need that in this ?
(12 Aug '13, 21:55)
@pushkarmishra : hi,could you please elaborate your idea of solving this problem using Segment Tree ?
(14 Aug '13, 09:37)

this is giving TLE anyone plz help http://ideone.com/pawz5b answered 13 Aug '13, 23:25
@v2v4 I just changed the power function (exp in your code) and it is now AC. Here is the link http://www.codechef.com/viewplaintext/2582486 Your code is absolutely correct, it's just that your exponential function performs too much modulus operations. And modulus operations are computationally expensive. Happy Coding.
(26 Aug '13, 21:26)

can sm1 plss check why m i getting WA for my code..... http://www.codechef.com/viewsolution/2529589 i m getting all right answers for as many test cases as i could think of....am i missing sm exceptional case?? answered 14 Aug '13, 02:22

this is giving TLE anyone plz help http://ideone.com/pawz5b
I hate the question where key lies in exploiting the limits.