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

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 :frowning:

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
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

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