@prakhar17252
I think u should precompute the modular multiplicative inverse for all elements of answer array.
Since size of array is only 10^6 so complexity 10^6(logN)
However in worst case of urs,complexity is O(210^7logN) which exceeds the Time limit
can someone please tell me where else should i optimize my code, i tried so many times but couldnt get AC, getting TLE on the third subtask CodeChef: Practical coding for everyone
I have done everything you have done in SEGPROD but still didn’t get AC. I was getting TLE int task1 of of subtask3.
Can you suggest some changes which might fetch me an AC.
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
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
I have done everything that is told in the tutorials and still getting tle. Can anyone suggest any modification?
solution: CodeChef: Practical coding for everyone
Thanks in advance…
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)
Great editorial. But I am having difficulty in understanding square decomposition solution of CSUBQ, what is array found used for in your code ? @taran_1407
@taran_1407 bro, it may be my immaturity in knowledge, since I have just gone through the MMI concept on GeeksforGeeks, but I can’t understand how will it give the desired answer in O(1)?
I solved CSUBQ(after contest) using 2 Fenwick trees cuz i am no expert with segment tree and Fenwick seemed easy to implement with need of just handling the merge or break segment conditions with if else blocks.
So what i did is, maintained 2 maps for storing the index of consecutive blocks and the length of array from that index(array-1 is 1 when element is <= R ; array-2 is 1 when element is < L) .
I used Fenwick to store sum of segments from 1 to any index, thus on querying i’d do something like let a = --map.upperbound(r), b= --map.upperbound(l)(i.e. decrement both upperbounds),
then ans = a - b;(mind me for the syntax her) after that, decremented the unnecessary part of segments
For a 1-query used lowerbound on both maps, accordingly merged or break the segments.
For a 2-query just used lowerbound on both maps, accordingly decremented the unnecessary part of segments and printed the answer .
My code would seem lengthy because i didn’t make any function for the merge or break part and cuz of the repeated if else blocks(sorry).
Well, I tried doing everything… converting vector to array…making euclidean iterative… still can not get to pass that 9th test case… any help would be appreciated…-Link to solution
@taran_1407 for the 20 points as explained above in SEGPROD QUESTION in case when we calculate an prefix product array and 0 comes then all the subarrays gets zero in which that element comes and in that case SIGFPE AND WA definitely comes . PLZZ Explain your approach for 20 points first i am not gettting it THAT PREFIX PART PORTION AND THEN prefixprodarr[Ri]/pparr[Li-1] i n case 0 comes we cant do this i am right or wrong plzz clarify
This is simple, just refer to factPowSum array and give it a try. Read further only after a try.
let ans = 1.
for every factor of P, ans = ans*pow(factor, factPowSum{R+1}-factPowSum{L}).
Now, combining above two sub-problems, we get answer of query as
let ans = (prefixModProd(R+1)*MMI(L) * product(pow(factor, factPowSum[R+1]-factPowSum[L])) )%P.
i write code for the above implementation as
shown below
ans=1;//fact pow sum for the first array
for (std::set<ll>::iterator it=factors.begin(); it != factors.end(); ++it)
{
for (i = 0;i<allfactPowSum.size(); ++i)
{
if(Li>0)
{ans=(ans*(modexp(*it, allfactPowSum[i][Ri]-allfactPowSum[i][Li-1])))%p;}
else ans = (ans*(modexp(*it, allfactPowSum[i][Ri])))%p;
}
}
at the last
ans = (prefixModProd(R+1)*MMI(L) * product(pow(factor, factPowSum[R+1]-factPowSum[L])) )%P.
should be applied in an loop along with calculation of every factor or just outside the loop once ?
I know, the 9th file. But learnt something knew from Both these problems. That trust problem testers to make your programs work in worst complexity cases. (just joking)
Learnt about Non-classical application of Segment Tree, First time about MI.