Unofficial Editorials November Long Challenge (Part 2)

editorial
,
94

Use 1 based indexing everywhere. Or use approach in editorial- thats the only way :frowning:

95

I have used the approach in editorial (given above)…
I don’t get how 1-based indexing would help??

96

Try using bit shift instead of dividing. and instead of % 64 use & 63

97

He meant the Official Editorial. The Complexity is larger this way. You can also refer to this DS

98

thanks for sharing such a great solution :slight_smile:

i understand it but unable to implement it! I have first created sqrt(N) blocks and then for each blocks another sqrt(N) …(as mentioned) but facing problem on how to map them to appropriate index during query. can you please explain a little bit how did you map indices in the inner levels ?

99

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…

100

@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.

101

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.

1 Like
102

that thing is ok but when u do that portion prefixModProduct®/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

103

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?

1 Like
104

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.

1 Like
105

plzz check here where i am doing wrong PIxj0c - Online C++0x Compiler & Debugging Tool - Ideone.com ignore the upper headers and commented portion plzz

106

hey in your above logic ModInverse(L-1) here i have to pass arguments to the function Modinverse(premoduloproduct[L-1],p) like this !

107

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.

1 Like
108

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

109

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

110

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.

1 Like
111

ya i just confused in them gcd(a,p) have to be 1 in both cases ok … :slight_smile:
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 ??

112

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.

1 Like
113

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