# WALL - Editorial

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.

Solutions : setter tester

1 Like

The practise section link for this problem seems to be broken!!

There should have been at least a warning for the precision problem in double

4 Likes

But if I donāt try to find cycle , I just calculate the cumulative value upto m , cause after m it is gauranteed cycle , and store the cumulative area upto m.

Now final area will be cumulativeArea[m-1]*((n-1)/(m-1)) + cumulativeArea[(n-1)%(m-1)]

Is this formula OK ? I got WA but donāt know whether its a precision problem or my formula is wrong.
Hereās my submission

Well, just printf("%lld.%d\n",sol/2,sol&1?5:0) and see if it passes the tests

I canāt calculate the cumulative area then if I store the areas in double array.

@neo i agree

1 Like

@neo i also support

1 Like

my approach is same as of approach mentioned above but donāt know why it is giving wrong answer ,
i have tried using double, long long int and long double.
But in all the case it is giving wrong answer

( using double)-- http://www.codechef.com/viewsolution/4673362

(using long double)āhttp://www.codechef.com/viewsolution/4676624

(using long long int)āhttp://www.codechef.com/viewsolution/4676661

guaranteed existing cycle, yes. guaranteed cycle from initial value of IND, no. Youāll fail in the case like a cycle 0->1->1->1->1 (This is the case of sample input 1, you should have studied sample input)

1 Like

Can you lease explain the approach betterā¦?!! That would be really helpful.

Why does this gave RTE? If uāll remove comment on line 5 itāll work, but dont understand why defining it as S[n+1] doesnāt work when I am going max till n.

but I didnāt fail in sample I/O , I failed later 33 and 33 points

I implemented the cycle finding algorithm mentioned in the 100 points section. It still gives TLE for subtasks 2 and 3.

Submission: http://www.codechef.com/viewsolution/4677228

I did exactly the same thing as in the editorial but was not able to pass a single case. Can anyone help me there should be some silly error that i could not find even after giving it a lot time.

Submission : http://www.codechef.com/viewsolution/4675630

I did the same as mentioned in the editorial for 100 pts but getting a SIGSEV for last two test cases.Please help me out to identify my error.

Submission : http://www.codechef.com/viewsolution/4680368