Unofficial Editorials November Long Challenge (Part 2)

I did the same thing in c++ but got tle.
Used extended euclid for modular inverse.
Precomputed powers of prime factors uptill the max of each.
Still for the 3rd subtask i got tle.
Link to my solution:CodeChef: Practical coding for everyone

In this i even tried using an array instead of vectors but still tle

Some people implemented sparse table in different language and still got accepted.
Does this mean that language is what matters and not logic.

I also solved CSUBQ using seg tree. But my approach was a little bit different. It is easy to see that:
the number of subarrays with maximum array element in [L,R] is equal to difference of subarrays with all elements <=R and all elements < L. We can use 3 elements each in node to answer the 2 queries.

Here is a link to my solution. I use recursive seg tree and did not need any optimizations. I also added an additional variable in the node that stores size of node to make code simpler.

4 Likes

I tried solving CSUBQ little differently. For every index in the array i stored how many subarrays can be formed starting from that particular index and made a segment tree out of it.

Whenever i needed to update the array i made 6 cases to update the segment tree - if element smaller than ‘L’ replaces element in 1)range 2) greater than ‘R’; element in range replaces element 3)smaller than ‘L’ 4)greater than ‘R’ and element greater than ‘R’ replacing element 5)in range 6) smaller than ‘R’

For querying the range from x to y, i calculated how many subarrays are present in this range having starting point in x to y and i subtracted elements after y from the range accordingly.

To make the program easier i calculated next index greater than ‘R’ ,next index in range, previous index greater than ‘R’ and previous index in range for every element that is queried or updated.

The above solution works fine for first 3 subtasks but gave TLE for the last one although the complexity isn’t more than Qlogn. Can someone help me out here


[1]


  [1]: https://ideone.com/yDX2FD

I solved the SEGPROD problem using SQRT Decomposition and segment tree. Precomputed (each buckets product from range i to j, also precompute prefix and sufix of each bucket) out of query loop and answered each query in constant time. This approach had one flaw, that is, if L and R are both in same bucket, so I used segment tree for this case, and luckily it worked out.
Here is the link to my solution -


[1]


  [1]: https://www.codechef.com/viewsolution/16232677
1 Like

Why does my code give TLE for the first subtask? I did the same modular inverse approach.
https://www.codechef.com/viewsolution/16264031

EDIT: Precomputing the modular inverse worked :smiley:

1 Like

@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