Unofficial Editorials November Long Challenge (Part 2)

@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

1 Like

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

For reference check by submissions :

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

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

2 Likes

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

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)

7 Likes

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(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

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

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