Problem link : contest practice
Difficulty : Easy-Medium
Pre-requisites : Geometry, Number Theory
Problem :
There is a rectangle R on the Cartesian plane. The corner points of R are (0, 0), (0, H), (W, H) and (W, 0).
A simple polygonal chain P is placed in the rectangle. P can be described as following:
- P consists of N points, both coordinates of which are integers;
- The points are indexed with integers from 0 to N - 1;
- X-coordinate of i'th point of P equals to Xi;
-
Y-coordinate of i'th point of P equals to:
- 0, if i is even;
- H, if i is odd.
- X0 equals to 0;
- Xi < Xi + 1 for 0 ≤ i < N - 1
- XN - 1 equals to W.
Your task is pretty simple: calculate the area of R, which is lying under P.
N can be extremely huge in this problem, so it’s impossible to give you array X itself. Instead of this, we will provide some additional variables and arrays, with a help of which you will be able to generate array X inside your program.
We will use additional integer variables M, A, B and IND. Also, additional array D, which consists of M integers and is indexed with integers from 0 to M - 1 will be used.
- 1 ≤ M;
- 0 ≤ A, B, IND < M;
- 1 ≤ Di < 104.
Here’s a pseudocode, which generates array X:
X[0] = 0
for i from 1 to N - 1:
begin
X[i] = X[i - 1] + D[IND]
IND = (A * IND + B) % M
end
</pre>
Explanation
Now the area under the polygonal line can be found by finding the sum of areas of triangles formed by (Xi,0), (Xi+2,0) and (Xi+1,H), where i=2*k (k>=0).
Our answer = (1/2)*H*(X2-X0 + X4-X2 + X6-X4 … XN-1-XN-3)
=(1/2)*H*(XN-1-X0)
=(1/2)*H*W
So, we need to just find W which is equal to XN-1. We are already given H in the question.
How to get 34 points
N is upto 524288 and M is upto 524288. We can easily generate the array X in O(N). XN-1 is W.
How to get (100) points
If we look at pseudo code for generating array X, we can see that IND can have atmost M distinct values. For each value of IND, there will always be a fixed value of next IND because it depends on constants A,B and M. So there will be always a cycle of length atmost M in the values of IND.
So, we first find the length of the cycle(we stop when we reach a value which has already been reached before). Finding cycle will be O(length of cycle). Let’ say the cycle is A1,A1…AK, where Ai denotes the values of IND visited. Let’s say SUM=sum[i=1 to K]{D[Ai]}.
Now, we know that this cycle is completed N/K times(our answer will be SUM*(N/K) after these many cycles) and also first N%K elements of this cycle are included. So, in our answer we also add sum[i=1 to N%K]{D[Ai]}.
Complexity is O(M) worst case.
Note: Using double to store the answer will not pass WALL because of precision problem. Use ‘long double’ instead, or just use ‘long long’ and print “.5” or “.0” manually.
