WALL - Editorial

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.

Solutions : setter tester

1 Like

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

8 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

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
here is link

( 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

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.

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

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

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

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.

but I didn’t fail in sample I/O , I failed later 33 and 33 points

I followed the same approach as in the editorial but still WA. please help https://www.codechef.com/viewsolution/25036941