Unofficial Editorials November Long Challenge (Part 2)

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

For reference check by submissions :

  1. TLE (0-based indexing) : 0 marks

  2. AC (1-based indexing with FAST IO) : 100 marks


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?
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.
just replaced x with s new variable and it worked!!

1 Like

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!! :wink:

@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®, 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

@taran_1407 I do not understand the factpowsum array part

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

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

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

1 Like

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

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

First time about 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 :stuck_out_tongue:

1 Like