FUNAGP - Editorial

bit
editorial
funagp
hard
may14
segment-tree

#1

PROBLEM LINK:

Practice
Contest

Author: Devendra Agarwal
Tester: Sergey Kulik
Editorialist: Lalit Kundu

DIFFICULTY:

HARD

PREREQUISITES:

Binary Indexed Trees/Segment Trees
Mathematics and Number Theory

PROBLEM:

Given fixed parameters R, p1, p2 (p1,p2 are primes) and array A, perform three operations:

* 0 S D X Y: Add an AGP with the start term of S, the common difference of D, common ratio of R from the X-th to the to Y-th element of A.

* 1 X g: A[X] = (A[X])g modulo p2.

* 2 X Y: Output (A[X] + … + A[Y]) modulo p1.

Array A can have upto 105 elements and upto 105 queries.

EXPLANATION:

We can see AGP as an infinite AGP. To add an AGP from [X,Y] is equivalent to adding 2 infinite AGP’s which are:
(a) Start Term = S, Common Difference = D and Starting from X.
(b) Start Term = −(S + (Y − X + 1) * D) * RY-X+1, Common Difference = −D * RY-X+1 and starting from Y+1.

Now the solver can use any data structure such as BIT/segment tree. But since BIT are easy to implement and efficient, I will discuss the approach using BIT.

Supose that using BIT, we somehow solve queries 0 and 2, how can we solve query 1 efficiently. Here we keep two BIT, one is modulo p1 (say BIT1) and other modulo p2 (say BIT2). For query 1 ie. 1 X g

// read respective values at X   
var1=read(BIT1,X)     
var2=read(BIT2,X)     

// update to make both indexes 0   
update(BIT1,X,-var1)    
update(BIT2,X,-var2)    

// update to add new values    
update(BIT1,X,var2^g mod p2)    
update(BIT2,X,var2^g mod p2)   

Now, we have to answer queries 0 and 2. Let us analyse the situation after just one addition of query 0 (which is added at X, as we have broken 1 AGP into 2 infinite AGp’s).

Let us find sum of all elements from 1 to J.

image1

Multiplying with R, we get

image2

Subtracting above 2 equations, we get

image3

image4

Simplifying, we get

image5


Let image6

Let image7

Let image8

Note:

(a) BADD, T and Z are independent of query point J.
(b) image9

By using Fact (a), we can store BADD, T and Z in the BIT (as it is independent of query point) in the update query 0 and use fact (b) for query of type 2.

Solution is not yet complete as we need to augment our data structure with yet another field ADD, which keeps the constant addition of the value in the index. This is used intially and for query 1. So, the output of query 2 changes from (b) to:

© image10

Wait, the solution is not yet over! What if (R-1)2 is not coprime to prime numbers, then we won’t be able to find INVERSE of it and hence our solution will fail. In this case, the problem transforms to AP as R mod prime = 1 mod prime.

Solve for AP in the similar idea using data structures.

Complexity of solution is O( N * log(N) ) intially, plus O ( log(N) ) for each query. So overall complexity is O( (N+Q)* log(N)).

See setter’s solution for implementation details using the above idea.

ALTERNATE SOLUTION:

(as told by @triveni)
There was no need of computing any kind of inverse modulo or such things at all to solve this problem, using the method that I followed. Even if p1 and p2 are not primes, this problem can be solved very easily using the same approach. I used Segment Tree data Structure. In my opinion, the hardest part to solve this problem is to find the sum of the AGP in efficiently. It is said in the editorial, we need to compute Modulo((R-1)**2).

But actually we can do something better here.

sum(i) = S + (S+D)*R + (S+2D)*R^2 + (S+3D)*R^3 +…+ (S+(i-1)*D)*R^(i-1)

=>sum(i) = (S + SR + SR^2 + SR^3 + SR^4 +…) + (0 + DR + 2DR^2 + 3DR^3 + 4DR^4 +…)

=>sum(i) = S(1 + R + R^2 + R^3 + R^4 +…) + D(0 + R + 2R^2 + 3R^3 + 4R^4 +…)

=>sum(i) = S * X(i) + D * Y(i)

Now, what one can do is pretty simple. Just pre-compute the value of X(i) and Y(i) for all 1<=i<=N.


Hence, it becomes pretty easy. Here is my solution using segment tree approach http://www.codechef.com/viewsolution/3844832.

This method doesn’t assume anything about primeness of p1 and p2.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Setter’s solution


#2

May i know, for which testcase, it failed
http://www.codechef.com/viewsolution/3872050


#3

There was no need of computing any kind of inverse modulo or such things at all to solve this problem, using the method that I followed. Even if p1 and p2 are not primes, this problem can be solved very easily using the same approach. I used Segment Tree data Structure. In my opinion, the hardest part to solve this problem is to find the sum of the AGP in efficiently. It is said in the editorial, we need to compute Modulo((R-1)**2).

But actually we can do something better here.

sum(i) = S + (S+D)R + (S+2D)R^2 + (S+3D)R^3 +…+ (S+(i-1)D)R^(i-1)

=>sum(i) = (S + S
R + S
R^2 + S
R^3 + S
R^4 +…) + (0 + DR + 2DR^2 + 3DR^3 + 4DR^4 +…)

=>sum(i) = S(1 + R + R^2 + R^3 + R^4 +…) + D(0 + R + 2R^2 + 3R^3 + 4R^4 +…)

=>sum(i) = S * X(i) + D * Y(i)

Now, what one can do is pretty simple. Just pre-compute the value of X(i) and Y(i) for all 1<=i<=N.


Hence, it becomes pretty easy. Here is my solution using segment tree approach http://www.codechef.com/viewsolution/3844832.

This method doesn’t assume anything about primeness of p1 and p2.


#4

If (R-1)^2 is coprime with P we still need to get R^(-X+1) but R might not be coprime with P in which case R^(-X+1) does not exist. I didn’t get how this solution deals with it. For instance, R = 9 and P = 3, if we got a query with X = 9, won’t we need 9^-8 mod 3?


#5

@all
As we all know there are many ways to solve this problem .we can use any of the two available data structures BIT/segment tree.
BIT solution is described by @darkshadows and an easy approach is descibed by triveni to handle complex part in this question
but i dont know why i am only able to get AC using triveni’s approach and if i am using modulo inverse approach i am continuously getting WA.

can any one check this solution and tell me where is the problem http://www.codechef.com/viewsolution/3902074

+1 to the problem setter
+1 to the darkshadows for providing approach using BIT
+1 to the triveni


#6

^I’m in exactly the same situation. Maybe it has to do with this part “What if (R-1)2 is not coprime to prime numbers”. Though my solution http://www.codechef.com/viewsolution/3900035 (solved using sqrt-decomposition) gives a WA regardless.
Surprisingly no AC solution uses square root decomposition.

Also some cheating cases:
http://www.codechef.com/viewsolution/3875556
http://www.codechef.com/viewsolution/3878413


#7

Report cheating cases to admin via mail.


#8

Can you explain in detail how to solve when (R-1)^2 is not comprime to prime nos? How does the problem transform to an AP?


#9

(R-1)^2 not coprime to a prime p means that gcd(p,(R-1)^2) > 1. However, since p is prime, that means gcd can only be p, so p|(R-1)^2. This is equivalent to saying R = 1 mod p, which means that
S+(S+D)R + (S+2D)R^2 + … + (S+nD)R^n = S+(S+D)+(S+2D)+…+(S+nD) mod p


#10

As p1 and p2 are primes , there are 2 cases(considering only p1)

Case 1: p1 is a prime , p1 divides R , in that case the series becomes S

Case 2: p1 is a prime , R is coprime to p1 , so you can find inverse modulo.


#11

@triveni

very good solution that you have provided i also stucked in the same part but the way you solved it is amazing …


#12

great solution


#13

got it, thanks!


#14

I have also added this solution to editorial, thanks for the approach!


#15

Hi kodos,

You are getting Wrong Answer for the test case

1

3 2 2 17 2

0 0 0

0 1 1 1 3

2 1 3

Answer should be 0 and you are getting 4


#16

Hi miiitd6979672,

        I think you have implemented the brute force solution to the problem which is not expected to pass because in worst case, total number of iterations will shoot up to (10^5) * (10^5).

#17

@all @darkshadows Please explain the complexity of query type 0 . By my understanding, if query of type 0 starts from 1 and end at N then updating the bit will be of O(N * logN ) [No of elements to update * complexity of one update], so if there are M queries of type 0 then compelity can be M * N * logN which will exceed the time limit.


#18

@all @darkshadows Please explain the complexity of query type 0 . By my understanding, if query of type 0 starts from 1 and end at N then updating the bit will be of O(N * logN ) [No of elements to update * complexity of one update], so if there are M queries of type 0 then compelity can be M * N * logN which will exceed the time limit.


#19

@devuy11 can you please explain this ?