Unofficial Editorials November Long Challenge (Part 2)

editorial
,
19

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)

7 Likes
20

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

21

Hey Taran nice work man!! :wink:

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