Unofficial Editorials November Long Challenge (Part 2)

editorial
,
22

@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)?

23

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 :slight_smile:

1 Like
24

@taran_1407 I do not understand the factpowsum array part

25

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

1 Like
26

@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

27

@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 ?

28

Thanks mate… Glad someone appreciated especially this one. Took nearly 4 hours!! My longest one (And most interesting too) :slight_smile:

1 Like
29

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. :smiley: (just joking)

Learnt about Non-classical application of Segment Tree, First time about MI.

Like the problem set but cursed the test cases :smiley:

PS: Delay in delay gift post :smiley:

1 Like
30

We cannot say the problems had weak cases this time I guess :stuck_out_tongue:

First time about MI.

MI?

 Delay in delay gift post :D

:(((((((((((((((((((((((((((

31

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

32

There is no link associated for editorials of first four questions on Click Here.

33 
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 :stuck_out_tongue:

1 Like
34

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. :slight_smile:

35

Oops!!, forgot. Just updating right now

36

Thats quite polite of you :smiley:

37

And generous of that person. :slight_smile:

38

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. :slight_smile:

Thanks for shring your approach though.

1 Like
39

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. :confused:

40

His solution passed. Maybe it’s time to learn efficient implementation of Sparse table.

1 Like
41

But, there are 2e7 queries in the worst case and answering each in log n time would take (2e7 * log n) computations which was failing clearly in C++. Not sure how it passed in python.

I dont know if ‘range product queries’ can be answered in O(1) per query using Sparse Table. In that case it would pass.