Why does my code give TLE for the first subtask? I did the same modular inverse approach.
https://www.codechef.com/viewsolution/16264031
EDIT: Precomputing the modular inverse worked
Why does my code give TLE for the first subtask? I did the same modular inverse approach.
https://www.codechef.com/viewsolution/16264031
EDIT: Precomputing the modular inverse worked
@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
Hope your first subtask gets passed with this
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
Thanks In Advance…
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.
Link to my solution: CodeChef: Practical coding for everyone
I have done the exact same thing in SEGPROD, yet getting TLE in task #9 could someone please help me?
solution link: CodeChef: Practical coding for everyone
are you going to do part 3 as well?
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 :
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…
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 CodeChef: Practical coding for everyone
AC CodeChef: Practical coding for everyone
just replaced x with s new variable and it worked!!
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
Hey Taran nice work man!!
@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).
Here’s my solution.
PS : Upvote this if you like
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
@taran_1407 : plzz help
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 ?
Thanks mate… Glad someone appreciated especially this one. Took nearly 4 hours!! My longest one (And most interesting too)