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.
