Unofficial Editorials November Long Challenge (Part 2)

Hello Guys

I have divided problems into posts according to difficulty. Hope u all don’t mind this. :wink:

This is the part 2 of two posts of unofficial editorials for November Long Challenge.

For editorials of problems VILTRIBE, CLRL, PERPALIN and CHEFHPAL, click here.

This post has editorials for problems SEGPROD and CSUBQ.

Problem SEGPROD

Problem Difficulty : Medium

Prerequisites:Modular Multiplicative Inverse (euclid’s method), Simple maths, and patience.

Problem Explanation

Given an array and a number P (not necessarily prime), Answer range product queries modulo P. (Not as simple as it looks).

Solution

The first thing i want you all understood is the euclid method of finding modular multiplicative inverse, vital to my approach, about which you may read from wikipedia and find the algorithm here.

The naive brute force (not at all successful even for 20 points, due to integer overflow) would be to create a prefix product array (similar to prefix sum array) and for every query L to R, output prefixProd(R) / prefixProd(L-1) and output modulo P. That’s correct, but incapable of giving us 100 points.

So, we move to modular multiplicative inverse (MMI) for help!!. We will to the same thing. Instead of prefix product, we will make an array storing prefix modular product (mod P ofcourse). Now, to answer queries, we are going to answer queries just as prefixModProduct(R)/prefixModProduct(L-1).

This is same as (prefoxModProduct(R) * ModInverse(L-1))%P.

If you have followed the logic upto here and understood MMI from geeksforgeeks page, you have earned 20 points. Hurray.

The reason of only 20 points is that Modular multiplicative inverse of a number A exists only when A and P are co-prime (gcd(A,P)==1). For first subtask, it was given that P is prime and all numbers are smaller than P. From that, it’s obvious that gcd(A, P) is one for every element, so we get 20 points.

Now, for full solution, we will use the same technique, but with a slight change in plan. Now, we will first find prime factors of P (U’ll understand why) and handle numbers in a different way, which will be explained by an example.

Suppose P = 6 and given array is 1 2 3 4 5 6 7 8 9 10

Now, Prime factors of 6 are 2 and 3.

Now, we will handle powers of 2,3 separately and rest numbers separately.

Create an array factors which will have value {2,3} for this example. create a 2d array factorPowSum[NumberOfFactors][N]

factorPowSum array will look like below (explained how to make this below that)

factor 0 1 2 3 4 5 6 7 8 9 10 11

2… 0 0 1 1 3 3 4 4 7 7 8 8 (dots to adjust position, spaces are truncated automatically)

3… 0 0 0 1 1 1 2 2 2 4 4 4

And we will think(it’s necessary) we are given given array 1 1 1 1 5 1 7 1 1 5 11 (all numbers are divided by 2 and 3). Now, you will see that all numbers are co-prime to 6. Now we can use the algorithm to solve the queries for reduced array.

Let’s assign factor 2 to index 0 and factor 3 to index 1.

Creation of factPowSum array

Just assign factPowSum{factorIndex}{0} = 0 and for 0<i<=N

factPowSum{factorIndex}{i} = factPowSum{factorIndex}{i-1} + Power of factor divided from ith number(1-based indexing).

For example, from 8, 3rd pow of 2 was divided, factorPowSum{0}{3} = factorPowSum{0}{4} + 3.

Hope i made the array clear.

Now, consider that we are given only powers of factors of P.

Continuing same example, The same array we were working with now becomes (I know this is lengthy as hell, but I tried making it as easy to understand as possible)

1 2 3 4 1 6 1 8 9 2 1 (Only powers of 2 and 3 are considered from given array).

Now, if someone ask us range query on this array, we can answer each query within O(number of factors of P) time.

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.

// The queries in question are 0-indexed

You are about to lose 100 points if you do this. Shocked!!. Be sure to take modulo after every multiplication so as to lose your AC to Integer overflow, use long long int/long only.

Now you all deserve 100 points in this problem, but you will get TLE because test cases were too tight. Calculating powers with fast modulo exp even takes O(logN) time, which is too much for 10^7 queries. So we calculate powers of factors of P before answering queries and store in an array. I am not going to explain this but it’s easily understandable from my code. In case you need help, feel free to ask.

Added Proof:

lemma: P can have at most 10 different prime factors.

Proof: Try multiplying first eleven prime numbers. The product will be greater than 10^9. but as P <= 10^9, it follows that maximum number of distinct prime factors P can have is 10.

Here’s a link to my


[4]. (Took nearly 30 submissions for 100 points :D)

### Problem [CSUBQ][5]
# 
### Problem difficulty:Medium

###  Prerequisites:Segment Tree, Too much patience unless u r a segment tree expert (msg me if u are, want a talk.)

#### Problem Explanation

An array of Size N and M queries, Tow Integers L and R (L<=R), handle following queries.
 1. update ith value to X.
 2. Find number of subarrays betweeen L and R, whose maximum values lie between L and R. (both inclusive)

#### Solution
 
**One basic formula. (very basic)**

let function c denote c*(c+1)/2 (The number of all the possible contigious subarrays from an array of length c.)

1+2+3+4+5 ... (N-1) + N = N(N+1)/2

Now, take L = 1, R = 10 and given array 2 0 11 3 0 (example given in problem)

(I'm directly taking an array instead of a series of updates to explain it).

Required subarrays between 1 to 5 are {1, 1}, {1,2},{4,4} and {4,5}

An interesting thing to observe is that ans = c(2)-c(1)+c(2)-c(1) (I'll explain how i came up with this.)

**Two Facts:**
 1. Any element > R is never included in any subarray (like element 3).
 2. Any number of elements smaller than L can be included in subarray as long as there is atleast one single element between L and R inclusive.

So, we are going to get 25 points first using this fact.

See [this][6] solution for details. in this solution, inc means consecutive elements till now which are smaller or equal to R, and exc means all consecutive elements < L till current position. Whenever we reach an element >= L, subtract excluded subarray count ( c(exc) ) from count and set exc = 0 and inc++ and whenever u get an element > R, add c(inc), subtract c(exc) and set both to 0. otherwise inc++, exc++.

Ans is count + c(inc)-c(exc).  Got 25 points. This solution runs in O(QN) time.

I hope this logic is clear. Because if it isn't, be sure to read again once, twice, 10 times, 10^2 times, 2^ 10 times (I like this quote :P).

Now, Getting 52 points isn't difficult if You have heard about **square root decomposition**. I have submitted a [solution][7] using this technique too. :P. (I submitted too many solutions for this) I used in this solution apart from the counting technique we discussed above and one thing mentioned below

Cheers, now we got 52 points with this ease, but no longer. Problem setters aren't going to gift 52 points with this ease.

Now, think here, what information about a segment L to I and a segment from I+1 to R we need to find out all required information.

Refer to my [solution][8] (One more solution :P) alongwith to understand what's going on.

Let me help u. You need 8 variables (too much u feel i guess), as follows:
 1. count => The count of subarrays already included in range, except those at borders.
 2. incL => Number of elements from left to leftmost element which is > R. (0 if there's no element > R in range)
 3. incR => Number of elements from right to rightmost element which is > R. (0 if there's no element > R in range)
 4. excL => Number of elements from left to leftmost element which is >= L. (0 if there's no element >= L in range)
 5. excR => Number of elements from right to rightmost element which is >= L. (0 if there's no element >= L in range)
 6. size => size of range
 7. found1 => boolean, which tells whether range contains atleast one element > R.
 8. found2 => boolean, which tells whether range contains atleast one element >= L.

Any ideas how we are going to merge ranges?, it's simple enough.

Consider array 2 0 1 11 3 0 5

Answer of this Problems is c(3)-c(1)+c(3)-c(1) = 6-1+6-1 = 10

Think of this problem in two parts. for elements > R and for elements >= L. 

For first part, consider any element > R as dividing element. for above example, 11 is dividing the total ranges into two sub-ranges of length 3 each.

For second part, consider any element >= L as dividing element. For above example, 2,1,11,3 and 5 are dividing elements, resulting in 2 ranges of length 1. ( {1,1} and {5,5} ).

If you understood this part, You can divide the given problem into two parts, the one dealing with elements to be included, and the one dealing with elements to be excluded.

Here comes the Main part of solution,**The Segment tree**. Now, as you may see, i have used an iterative segment tree,(I messed up recursive one and also, iterative is slightly faster if u take the trouble to understand it) about which you may [read here][9]. I first of all, created a class S (struct equivalent in java) which hold all this info about each segment of tree.

Now, the most important thing is to create a merge function, which will merge two segments into a larger one correctly.

You may see from my code, i have dealt with inclusion and exclusion separately, making my code simpler.

For first part, i check if both sides have element > R (our dividing element) (using boolean found1). if both has, include Left of large range will be outL of left segment and include right will be includeRight of right segment. count will be increase by c(left.incR + right.incL) because they are no longer boundary elements of segment.

In case only one segment has dividing element, incL and incR of output range is assigned accordingly.

Same way for large. And Here we go. We have solved the problem. Bet you didn't realize that. 

All that is left to implement it. And Now, nothing is going to stop you from 100 points except a TLE in one file. (Not Sure, because i had use the following tip to save time.)

Link to My 

10.

PS: This was my first editorial using segment trees. So, i am sorry if any error might have crept in (without my knowledge, of course) Do give your review for this editorial.

As always, i wholeheartedly invite your suggestions and thank for your response to my previous editorials.

PS:Sorry for delay, was held up in something important. Delay gift will be posted as soon as I learn the technique of problem Polynomial. :smiley: Hope you don’t mind delay in delay gift. :smiley:

17 Likes

Aah, was waiting for some unofficial editorials by someone. :smiley: And here it is !

You are doing a really awesome work, bro !! Hats off to such an initiative to help others. The official editorials being provided late, your editorials did really come handy in the last long contest as well!

Thanks a ton, for the editorials mate. :slight_smile:
Keep up the good work!

Happy Coding! :smiley:

2 Likes

CSUBQ, I took 8-9 variables as well.

You cannot say SEGPROD required patience, try it in C++. My code was taking ~4.5 seconds on local machine for worst case I produced, and its a constant TLE for 20 hrs straight on that SINGLE TEST FILE OF FINAL SUB TASK.

Then got AC after a hard day XD

1 Like

You can also solve SEGPROD by Sparse Tables.

Initially, in C++, it was giving TLE in some cases. So, I submitted it in PYPY. Here is the link to the accepted submission. But after the contest, I saw that many contestants have solved it in C++ using sparse tables after optimizing the code.

https://www.codechef.com/viewsolution/16185616

2 Likes

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