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)
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.
Like the problem set but cursed the test cases
PS: Delay in delay gift post
We cannot say the problems had weak cases this time I guess
First time about MI.
MI?
Delay in delay gift post :D
:(((((((((((((((((((((((((((
I had to find someone ready to explain me their approach (I haven’t solved the problem myself yet, nor know how to). I found someone few minutes ago…
I cannot really ask that person to explain right now, not at 12:30 am. I will post as soon as i get their approach
There is no link associated for editorials of first four questions on Click Here.
I cannot really ask that person to explain right now, not at 12:30 am. I will post as soon as i get their approach
Yes, I understand. Anyone will be bewildered if he has to explain one of hard problems of long at 12-2am at night
I know you would be surprised, but that person was willing to, but i myself had to refuse. I can’t trouble that person at this time even if that person is willing to help me.
So, hopefully only a small delay.
Oops!!, forgot. Just updating right now
Thats quite polite of you
And generous of that person.
I appreciate your approach but as a great coder said, everyone likes his own code even if other’s code is too beautiful to be disliked.
Thanks for shring your approach though.
You are answering each query in (log {R - L + 1}) time using sparse table ? That is log n in the worst case.
I tried using sparse table too, in C++. But even the first subtask did not pass.
His solution passed. Maybe it’s time to learn efficient implementation of Sparse table.