×

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. ;)

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

This post has editorials for problems SEGPROD and CSUBQ.

Problem SEGPROD

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.

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 Code. (Took nearly 30 submissions for 100 points :D)

Problem CSUBQ

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

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. :D Hope you don't mind delay in delay gift. :D

3.2k1135
accept rate: 22%

(14 Nov '17, 00:30)

Oops!!, forgot. Just updating right now

(14 Nov '17, 00:37)

@taran_1407 I have asked a question for SEGPROD. It will be really helpful if you could help me debug my code and telling me where I am wrong.

(14 Nov '17, 01:05)
3

No need for square root decomposition to get 52 points (CSUBQ). :P

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

(14 Nov '17, 10:14) 3★

Nice use of binary search. :) @eugait

(14 Nov '17, 19:01)

@taran_1407 There is no binary search.

(14 Nov '17, 22:15) 3★

@eugalt, I'm not much in c++, but i thought lowerbound function uses binary search. Correct me if I'm wrong. :)

(15 Nov '17, 00:39)

@taran_1407 There is lower_bound() function in the algorithms library which uses binary search on an iterator range. Here it's a map/set method with the same name.

(15 Nov '17, 01:42) 3★

Oops. My mistake :D

(15 Nov '17, 20:54)
showing 5 of 9 show all

 4 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. answered 14 Nov '17, 01:18 616●1●10 accept rate: 29% 2 Exactly what I did, except that I used 2 segment trees one for elements >= L and one for elements > R. (14 Nov '17, 01:25) 1 Thanks to both of u for sharing ur approach... Though ur approach was nice, But to tell the truth, this is my first ever segtree non classical problem which i managed to solve. 2 segtree would be too much for first timers... (14 Nov '17, 15:24) @taran_1407 you don't necessarily have to make 2 segment trees. Since the working of the 2 segment trees is exactly the same, I made a class for segment trees and used 2 objects of that class as mentioned above. It made the code look clean and simple. Here's the code. https://www.codechef.com/viewsolution/16233573 (14 Nov '17, 20:13) 1 Mate, i too used one segtree only. Thanks for sharing. :) (14 Nov '17, 20:15) 1 I too used segment tree, but my approach is kind of a standard one. Just save positions of maximum left and the right element which is < R and merge the segments. https://www.codechef.com/viewsolution/16163632 (17 Nov '17, 01:09)
 2 Aah, was waiting for some unofficial editorials by someone. :D 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. :) Keep up the good work! Happy Coding! :D answered 14 Nov '17, 00:08 251●6 accept rate: 3% 1 Thanks mate.. Glad someone appreciated especially this one. Took nearly 4 hours!! My longest one (And most interesting too) :) (14 Nov '17, 00:12)
 2 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. answered 14 Nov '17, 00:46 1.0k●5 accept rate: 14% 1 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. :) Thanks for shring your approach though. (14 Nov '17, 00:48) You are answering each query in (log {R - L + 1}) time using sparse table ? That is log n in the worst case. I tried using sparse table too, in C++. But even the first subtask did not pass. :/ (14 Nov '17, 00:49) 1 His solution passed. Maybe it's time to learn efficient implementation of Sparse table. (14 Nov '17, 00:51) But, there are 2e7 queries in the worst case and answering each in log n time would take (2e7 * log n) computations which was failing clearly in C++. Not sure how it passed in python. I dont know if 'range product queries' can be answered in O(1) per query using Sparse Table. In that case it would pass. (14 Nov '17, 00:56) 1 I am amazed too. (14 Nov '17, 01:05) @jaideeppyne Yes, my solution is O(NLogN + QLogN). But I've submitted it in PYPY, it's time limit is same as that of Python i.e. 5x that of C++. However, PYPY is significantly faster than Python. So, in the end, my solution passed just within the time limits. (14 Nov '17, 01:20) showing 5 of 6 show all
 2 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 :) For reference check by submissions : TLE (0-based indexing) : 0 marks AC (1-based indexing with FAST IO) : 100 marks answered 14 Nov '17, 18:01 851●3●16 accept rate: 30% 1 Honestly, I feel that setter and tester were extremely wrong in setting the time limit. I wonder how much time setter's code takes to run, cause if its something like 3.8-3.9seconds, then time limit is wrongly put. Saying because, languages like java etc. got accepted (time bonus), while c++ got tle. (14 Nov '17, 18:24) Really @vijju123?? Is this the case?? Are the solutions with same approach but different languages are getting different verdicts?? This is a matter of serious concern as this would cause unfair advantage to some. I would really hate this if something of this sort happens. I guess this need strict action. Perhaps it should be made responsibility of problem tester to solve the problem with same approach using c++, python(PYPY or CPYTH) and Java, for these three languages are most popular ones. Hope this matter won't go unnoticed. (14 Nov '17, 19:13) Setter's solution works in 2.5 sec holy shit :O O_O (15 Nov '17, 20:05) Oh by god.... @vijju123 Well, I hope you convey this suggestion to admin. There should be proper testing in these three languages at least. No one should ever get undue advantage just because of a particular language. Hope once again, This matter won't go unnoticed. (15 Nov '17, 20:40)
 1 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 answered 14 Nov '17, 00:09 12.6k●1●4●25 accept rate: 19% 1 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. :D (just joking) Learnt about Non-classical application of Segment Tree, First time about MI. Like the problem set but cursed the test cases :D PS: Delay in delay gift post :D (14 Nov '17, 00:14) We cannot say the problems had weak cases this time I guess :p First time about MI. MI? Delay in delay gift post :D :((((((((((((((((((((((((((( (14 Nov '17, 00:25) 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 (14 Nov '17, 00:30) 1 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 :p (14 Nov '17, 00: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. :) (14 Nov '17, 00:36) Thats quite polite of you :D (14 Nov '17, 00:42) And generous of that person. :) (14 Nov '17, 00:44) @vijju123, Unluckily, That person got some unavoidable reasons, keeping that person busy, because of which I cannot do an editorial on POLY unless anyone else is willing to help me. Sorry for inconvenience. (14 Nov '17, 20:05) showing 5 of 8 show all
 1 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 - code answered 14 Nov '17, 03:45 27●2 accept rate: 33% That's great (14 Nov '17, 15:24)
 1 @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 answered 14 Nov '17, 08:29 988●8 accept rate: 21%
 1 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 https://www.codechef.com/viewsolution/16259177 AC https://www.codechef.com/viewsolution/16260183 just replaced x with s new variable and it worked!! answered 14 Nov '17, 21:54 11●1 accept rate: 0% Happens, mate. You are not the first one for this, nor you will be the last. I too wasted nearly 12 submissions (WA Segment tree ones) on CSUBQ because of a variable mistake. Just changed variable and got AC. (15 Nov '17, 20:44)
 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 :) answered 16 Nov '17, 01:42 76●2 accept rate: 7% Great... Its just that i haven't worked with fenwick tree, because segtree usually serve the purpose. (16 Nov '17, 14:26)
 1 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 answered 21 Nov '17, 22:49 5★kush2327 11●2 accept rate: 0% Use 1 based indexing everywhere. Or use approach in editorial- thats the only way :( (21 Nov '17, 22:59) I have used the approach in editorial (given above).. I don't get how 1-based indexing would help?? (21 Nov '17, 23:01) kush23275★ Try using bit shift instead of dividing. and instead of % 64 use & 63 (22 Nov '17, 00:38) He meant the Official Editorial. The Complexity is larger this way. You can also refer to this DS (22 Nov '17, 00:39) Guess, I need to use the DS you described. Also, could you please explain a little about the cal function written in your LVGFT code. How are you finding m1,m2? You could explain in LVGFT editorial.. (22 Nov '17, 20:39) kush23275★ @kush2327 - Even I dont know why 1 based indexing helps, except that the codes using those did 9th test case in 3.6-3.9 seconds. Someone said that its because "Less "%" operations are performed this way" but I dont know how correct it is. (22 Nov '17, 20:42) showing 5 of 6 show all
 0 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:https://www.codechef.com/viewsolution/16214170 In this i even tried using an array instead of vectors but still tle answered 14 Nov '17, 00:55 988●8 accept rate: 21% i don't have much experience in c++, but i guess % is taking your time. % take same time as division takes, which is O(N^2) , N being number of digits. May be that's what causing TLE. Replace value%N with if(value>=N)value%=N Hopefully all tle turn into AC. (14 Nov '17, 00:59) Or you may try iterative version of gcd Extended. (14 Nov '17, 01:00) I tried the iterative version also. I think i should try that modulus part. Thanks ,any more optimisations can be done? (14 Nov '17, 01:03) I hope that would suffice. Else see fast solutions of other coders. (not mine though, it just passed on borderline :D ) (14 Nov '17, 01:06) Thanx a lot!! I did around 120 submissions and couldnt figure this thing. Will always keep this in mind. (14 Nov '17, 01:17) I did only 30. :D (15 Nov '17, 20:50) showing 5 of 6 show all
 0 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 code answered 14 Nov '17, 02:30 1 accept rate: 0% Mate, ur complexity may be QlogN, but in some problems, u also have to take care of constant factor associated, which i believe, is the reason of tle. (14 Nov '17, 15:30)
 0 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 :D answered 14 Nov '17, 07:56 60●3 accept rate: 0% Great. Often when queries are 10^7, pre calculation is vital (14 Nov '17, 15:25)
 0 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 https://www.codechef.com/viewsolution/16231600 Thanks In Advance.. answered 14 Nov '17, 11:32 0●1 accept rate: 33% Maybe vectors are the reason. Rest i didn't exactly got the gist of your solution. Maybe u should try same solution using arrays, or add a bit of explanation about ur approach (14 Nov '17, 19:17) I divide the problem in three subtasks. general is the function of third subtask. i take out all the prime from p. I precalculate those prime power 10e6. then I build the dp array with the leftovers and calculate mmi. afterwards i check for the common prime powers seperately. (17 Nov '17, 21:29)
 0 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: https://www.codechef.com/viewsolution/16263438 answered 14 Nov '17, 11:45 5★codent47 1●1 accept rate: 0% I would not always say to avoid recursive ones, but constraints were too tight for this problem. Iterative is a little bit faster, for ur power left function. U may try making it iterative. (14 Nov '17, 15:27) 1 @codent47 Always consider using iteration instead of recursion wherever possible. Infact you can do that for all your three power functions, I am pretty sure, it would pass then. And also consider using Fast I/Os in such questions where TL is too strict. Also try using arrays instead of vectors, vectors are a bit slower than arrays. (14 Nov '17, 17:25) lohit_974★
 0 I have done the exact same thing in SEGPROD, yet getting TLE in task #9 could someone please help me? solution link: https://www.codechef.com/viewsolution/16254283 answered 14 Nov '17, 13:17 105●4 accept rate: 0% Try using arrays in place of vectors.. Hopefully that works because arrays tend to be faster than vectors. (14 Nov '17, 15:29)
 0 are you going to do part 3 as well? answered 14 Nov '17, 16:32 5★skyhavoc 121●6 accept rate: 0% I am not able to solve any of the last three problems (full solution). But i have texted someone to explain me approach of POLY. Whenever that person replies, i'll solve the problem and then write editorial. Waiting for that person's reply. :) If you can find anyone willing to explain his approach to me, i would be glad to write an editorial on any of last three problems and give him due credit as well. (14 Nov '17, 19:20)
 0 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 answered 14 Nov '17, 18:52 11●1 accept rate: 0% Well, an algorithm is always simple to its writer. :) It would be a bit easier for me as well as other very helpful contributors to help u if u explain your logic a bit. what does array arr do in your solution. It would help others to help u. :) (15 Nov '17, 20:49)
 0 I have done everything that is told in the tutorials and still getting tle. Can anyone suggest any modification? solution: https://www.codechef.com/viewsolution/16269941 Thanks in advance... answered 14 Nov '17, 19:51 1 accept rate: 0% Setter's solution runs in 2.5 seconds....horror (14 Nov '17, 19:59) May be U should try iterative versions of exponentation and mod Inverse, as they tend to be slightly faster. (15 Nov '17, 20:46)
 0 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 answered 15 Nov '17, 01:35 5★rj25 189●4 accept rate: 0% found[i][0] tells whether ith block contains atleast one value > R and found[i][1] tells whether ith block contains atleast one value >=L. (15 Nov '17, 20:43)
 0 Hey Taran nice work man!! ;) answered 15 Nov '17, 08:48 839●3●10 accept rate: 10% Thanks mate!! (15 Nov '17, 20:42)
 0 @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)? answered 15 Nov '17, 22:43 1●1 accept rate: 0% Well, Complexity of complete program will be O(Q*num) where num is number of prime factors of P. (15 Nov '17, 23:40) Lemma: A number upto 10^9 can only have at most 10 distinct prime factors. Proof: Try multiplying first 11 smallest prime numbers. The product exceeds 10^9, but P is <= 10^9. So, num <= 10. (15 Nov '17, 23:42)
 0 @taran_1407 I do not understand the factpowsum array part answered 18 Nov '17, 03:15 23●5 accept rate: 0% Can you explain a little bit more (18 Nov '17, 03:16) Well, consider given array 2, 4, 1, 8 (taking powers of two to simplify my example). let P be 32, so that the prime factor of P is 2. FactPowSum array wiil be 0 1 3 3 6 It is just the sum array of array 1 2 0 3 ( which denote largest powers of 2 which divide ith number) Read about sum arrays from http://www.geeksforgeeks.org/prefix-sum-array-implementation-applications-competitive-programming/ Hope that helps (18 Nov '17, 12:01)
 0 @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 answered 14 Dec '17, 21:21 21●4 accept rate: 0% 1 First thing, I would request you to share your solution link along with query. It will help me understanding the problem u are facing in a better way. Second thing, For first subtask, we are given P is a prime and all A[i] between 0 to P-1. This implies gcd(A[i], P) = 1 for all elements of given array, Ryt??. From here, i am using the fact that we are required to output the product modulo P. Here, i am using modular multiplicative inverse to solve our problem. (14 Dec '17, 22:03) that thing is ok but when u do that portion prefixModProduct(R)/prefixModProduct(L-1). here if any element in an array comes zero let suppose 3 element then after that element all subarrays elements product should be zero in our PREFIX PRODUCT ARRAY and then this thing will not work plzz clear this (14 Dec '17, 22:11) 1 Suppose we have small values of A[i], so that there's no risk of overflow. That is.. A[0]A[1]A[2] .... A[N-1] <= 1e18. In this problem, we can make a prefix product array of given array, and For [l,r] query, answer will be (prefixProd[r]/PrefixProd[l-1]). But for larger values of A[i], we will face overflow problem, so i stored prefix modular product. But now, we cannot perform the divide part. Consider following array: 1 2 3 4 5 6 and P = 113 Prefix modular product array will be 1 2 6 24 7 42. Right? (14 Dec '17, 22:12) 1 So we use modular multiplicative inverse, as explained at wikipedia and geeksforgeeks (links above). Using this concept (a/b)mod P = (a*inv(B))modP. So now, we can maintain prefix Modular product and inverse of prefix Modular product, to answer all queries of subtask 1 in O(1) time. Answer of query (l,r) being (prefixModProduct[r]*inversePrefixModProduct[l-1]) mod P. Hope that clarifies. (14 Dec '17, 22:16) plzz check here where i am doing wrong https://ideone.com/PIxj0c ignore the upper headers and commented portion plzz (14 Dec '17, 23:25) hey in your above logic ModInverse(L-1) here i have to pass arguments to the function Modinverse(premoduloproduct[L-1],p) like this ! (15 Dec '17, 00:43) 1 We are precalculating all ModInverses. No, For calculation of ModInverse, modInv[i] = exp(premoduloproduct[i], P-2, P). exp is modular exponentation function, returning (a^b)%P. (15 Dec '17, 01:33) thnkss bro i have understood we have to use modular exponentiation here but where is the concept of extended euclideans algo comes here for calculation of MMI of prefixmodproduct[Li-1] under modulo p (15 Dec '17, 14:05) can u plzz explain this thing breifly i ma not getting it CREATION OF AN FACT POW SUM ARRAY 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. factPowSum{factorIndex}{i} = factPowSum{factorIndex}{i-1} + Power of factor divided from ith number(1-based indexing). (15 Dec '17, 15:59) 1 When P is prime, MMI of A can be computed as (A^(P-2)) mod P. This is called fermat's little theorem. When P is not prime, we have to use extended gcd algorithm to find MMI. (15 Dec '17, 16:00) ya i just confused in them gcd(a,p) have to be 1 in both cases ok .. :) plzz can u clear my doubt in factpowsum portion by taking an small example u say factpowsum[factorindex][2]=factpowsum[factorindex][1]+power of factor divided from ith number(1 based -indexing) But later than when u solve this in editorial ** For example, from 8, 3rd pow of 2 was divided, factorPowSum{0}{3} = factorPowSum{0}{4} + 3. Hope i made the array clear. ** i just cant see where have u used the above stated condition and how ?? (15 Dec '17, 16:25) 1 I guess you wrote the example wrong. If 4th term is 8, factPowSum[0][4] = factPowSum[3] + 3. This way, when we have a range query (l, r), we know that 2^(factPowSum[r] - factPowSum[l-1]) is the part of final product. Hope that clarifies. (15 Dec '17, 17:44) 1 2 3 4 1 6 1 8 9 2 1 (Only powers of 2 and 3 are considered from given array). plzz explain this how this comes from the array 1 2 3 4 5 6 7 8 9 10 after considering the powers of 2 and 3 ans = (prefixModProd(R+1)*MMI(L) * product(pow(factor, factPowSum[R+1]-factPowSum[L])) )%P. and in this statement what product signifies the final ans of all the factors..!!? (15 Dec '17, 19:06) 1 The idea behind splitting input array 1 2 3 4 5 6 7 8 9 10 into two different arrays 1 2 3 4 1 6 1 8 9 2 1 and 1 1 1 1 5 1 7 1 1 5 11, is that we can write product queries (l,r) of input array as product of (l,r) queries in both reduced arrays. So, For second array, all the elements are co-prime to P, thus, MMI using gcd extended can be used to answer (l,r) queries of this array. (15 Dec '17, 19:27) 1 For array 1 2 3 4 1 6 1 8 9 2 1, factPowSum array will be factor = 2, index = 0 => 0 0 1 1 3 3 4 4 7 7 8 8 factor = 3, index = 1 => 0 0 0 1 1 1 2 2 2 4 4 4 (l,r) query for this array = for all factors , prod = (prod*factor^(factPowSum[r] - factPowSum[l-1]))%P. (15 Dec '17, 19:27) ya that i understanded clearly but how to split the original array in to these diff arrays in terms of powers of factors of p. ? (16 Dec '17, 12:15) 1 I create factpowsum array along with taking input, and directly store reduced array im A. Please refer my solution.. (16 Dec '17, 16:02) i am not getting ur solution as i am not a java programmer please u tell me the logic how to convert the array 1 2 3 4 5 6 7 8 9 10 in to the arrays in terms of powers of factors of p which are 1 2 3 4 1 6 1 8 9 2 1 (for power of 2) 1 1 1 1 5 1 7 1 1 5 11(for powers of 3) this is the last thing i am not abl to understand how to do plzz help ! (21 Dec '17, 19:45) for(int i = 1; i<= N; i++){ long long x; cin>>x;//Number read for(int j = 0; j< fcount; j++){  fsum[j][i] = fsum[j][i-1];//cumulative sum value taken till (i-1)th number. while(x%factor[j] == 0){//till x is divisible by factors x/=factor[j]; //divided by factor. fsum[j][i]++; //Increased fsum value for jth factor at ith number. }  pcount = max(pcount, fsum[j][i]); //used later, pcount tells maximum power of any factor to be pre-computed. } (22 Dec '17, 04:27) base[i] = x; //Since all factors are divided from x, now base is storing reduced array, reduced value of x. prod[i] = (prod[i-1]*base[i])%P; //prefix modulo product modInv[i] = modInverse(prod[i], P); //inverse of prefix modulo product } (22 Dec '17, 04:27) showing 5 of 20 show all
 0 @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::iterator it=factors.begin(); it != factors.end(); ++it) { for (i = 0;i0) {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 ? answered 21 Dec '17, 22:20 21●4 accept rate: 0% you should first calculate (product(pow(factor, factPowSum[R+1]-factPowSum[L]))%P) and then multiply it with (prefixModProd(R+1)*MMI(L)) (21 Dec '17, 22:31)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×13,929
×300

question asked: 14 Nov '17, 00:00

question was seen: 3,978 times

last updated: 22 Dec '17, 04:27