Unofficial Editorials February Long Challenge (Part - 2)

editorial
, , , , ,
3

For BROCLK-

I used simple formula.

Suppose we want to calculate cos(nx), then-

Even n-

Just use cos(nx)=2{cos}^{2}(n/2)x-1 . We know cosx and hence we can find numerator and denominator in logN time.

Odd n-

Notice that denominator portion for cos(nx) (unreduced form-numerator and denominator not in lowest term) is nothing but {L}^{n}. Now we use-

Cos(nx)+cos(x)=2*cos((n+1)/2x)*cos((n-1)/2x)

The RHS of denominator is nothing but case of even n, which we did earlier. The only thing to do is to subtract cos(x). Now, notice that cos(x)=D/L. I already know the final denominator, I just need to know the numerator part. Its nothing but D* DenominatorOf(cos((n+1)/2x)*cos((n-1)/2x)) [I think you guys guessed the denominator by now? :3 :stuck_out_tongue: )

Solution- CodeChef: Practical coding for everyone

For POINPOLY-

LOL this was a rollercoaster for comedy as I solved it. Initially, I was like “MEh, Geometry. GGWP I give up.”

But, just for fun’s sake, I decided to experiment out and submitted a random solution which passed for 70 points. Then my next few hundred submissions were spent on trying to grab those 30 points.

What I did was-

Assume large N. We know that since no 3 points are collinear, there must be difference of at least 1 in y coordinate for any 3 points, else y=k is a line passing through them. This means, if N is large, the diagonally opposite vertex is kind of “far” from the original one. So just take their mid point - it will lie inside the polygon.

Yeah, thats it, no checks on if point is inside or etc. The only thing to know is “how far” you want, or “how far” will hold good.

The principle assumptions of this approach is-

  1. The polygon is wide enough so that difference of +-0.5 does not affect the answer (in case the (X_1 + X_2) or(Y1+Y2) is odd.
  2. The polygon is convex, not concave.

The only place it failed was a specific case for N=10, which was narrow. For that I had to include a check that for small polygons actually check if it lies inside or not. :confused: Yeah, sad but had to swallow my pride :frowning:

3 Likes
4

For BROCLK we can also do this,
Lets say i want to calculate

cosnx ,n can be expressed in binary form,
So lets say cos5x=cos(x+4x)

So just calculate cosx,cos2x,…cos(log(n)(x)). ,
And also calculate sinx,sin2x,sin4x,…
(Sin2n=2sinn*cosn (Keep the irrational separate))
Now solving ,

cos(7x):

First cos3x=cosx.cos2x - sinx.sin3x

(Take care that sinx is irrational,but multiplication of two sin is rational)

Sin3x=cosxsin2x + sinxcos2x

After this calculate cos7x=cos(3x+ 4x)

My solution: CodeChef: Practical coding for everyone

3 Likes
5

  1. *How did we reduce the cos(tx)L to p/q form? I am having some problem in understanding this part. Is it by changing for eg 0.56 to 56/100 then dividing by common gcd i.e 14/25?

  2. And we search for a formula for cos(nx) because of exceeded memory to store nx right?

Thanks.

6

i have tried both approach dividing into triangles and simply using whole polygon:

  1. Approach 1:simply using polygon

in simply using whole polygon approach first i checked it contain sufficient point or not by using pick’s theorem then calculated maxY and minY and then start sweeping line to adjacent point on boundary of polygon and calculating all points on line by using bresenham line points generating algorithm and checking inclusion also…by this i passed top 6 subcases passed in less time limit and got TLE for last 2.link text

  1. Approach 2:dividing whole polygon into triangle

as said in editorial i divided polygon into triangle and used triangle inclusion test not that Area test for inclusion given in editorial because i feel it will give answer true(for inside) when point is in boundary which will give wrong answer.and similarly find points inside triangle as in previous approach(rotating line point to next point)…but this give large TLE on face only top 2 test case passed.and after testing time taken by traingle inclusion i found out it is taking too much time than fast polygon inclusion test.link text

**After contest over i saw some solutions and find that this question did a comedy with me. it is not a medium problem as tags are saying(binary search…etc.) and can be bypassed easily with some observations.link text
**

7

For POINPOLY , a simple technique is to find the centroid of the polygon and then simply finding the mid pts of each of the vertices and the centroid. This gave 70 pts and somehow failed for testcase 1 which turned out to be N=10 when I checked with assertions.That case had to be dealt separately.

1 Like
8

for POINPOLY : I have another observation and it worked but i don’t know whether it’s fully correct or not(may be the test cases are weak)?

My observation : since all the co-ordinates have integer value, so, minimum height of the polygon can be (n - 4)/2 . How? : since the polygon is convex so, maximum two points have same y co-ordinate and similarly in worst case the upper part(the farthest from this point) has also two points having same y co-ordinate and now since we are considering the farthest point so, we can assume that there are almost equal number of points on both side of the line(line joining the farthest point) and so, we have atleast (n - 4)/2 points having different y co-ordinates and at worst case their differences are ‘1’. so, minimum height will be (n - 4)/2. Now, the solution is easy as we have to find only N/10 (far less than ~ N/2 points and we know that our line lies completely inside the polygon. so, we can iterate on integer y co-ordinates and get our points. Now, the question arises what about x co-ordinate ? How do we claim that it’s value is also an integer? Well, for this what i have done is I started from middle point and go on traversing in both direction one by one and i thought that this works because we are considering two farthest points and similarly we can claim that the width of the polygon at the middle is at worst (N - 4)/2 and hence truncating to the nearest x co-ordinate will not make the point lie outside the polygon!

If someone will find something wrong then please let me know :slight_smile:

1 Like
9

For POINPOLY I tried to find out points only on lines joining vertices because there will be N*(N-1)/2 lines so I can easily get floor[N/10] points. For finding points on lines joined by integral points, I used the slope of lines. But the problem is when I implemented this solution I got WA for only second last case. @taran_1407 it would be really helpful if you could find the bug in my code or point out a mistake in my approach (Link to my JAVA Solution). During the contest, I solved the problem by Shuffling my set of points that I had collected while traversing on lines in hope that my code is printing some wrong points not all and it got AC. Here is code with shuffling for N=11 and which got AC.

10

for CARPTUN
I have used the logic of pipelining, where the process which takes longest time decides the overall time spent.
so calculate the toll which takes longest time. and multiply it with (c-1) cars

11

For POINPOLY, I used the fact that centroid lies inside the triangle. And with PHP I proved that [n/10] distinct lattice points exists. But when implementing it I faced some issues.
My first


[2],I couldn't find the mistake. (Can you find?, Thanks in advance) 
But when I rewire the code, I used long long every where instead of int, it passed. Here's my

3

12

@xerefic long is required as we r storing upto 10^9 values

13

Have a look at this solution of Pointpoly problem (it’s not mine) CodeChef: Practical coding for everyone

14

Can anybody please elaborate on converting the cos(t*x)*L into p/q… @vijju123 @taran_1407

15

For broken clock I used the formula :
cos (x+y)=2cos(x)cos(y)-cos(x-y). So when n is odd, it broke down to
cos(n/2+(n/2+1))=2cos(n/2)cos (n/2+1)-cos(1).
So I was saved from matrix expo., instead just a simple recursion worked, with just saving the already computed values in a map avoiding recalculation.

My POINPOLY solution is same as yours.
And yes, great editorials :slight_smile:

2 Likes
16

Hello Community,
Here is my first effort in making a editorial, and contributing to community.
Problem Link :CodeChef: Practical coding for everyone
Please do have a look :
PERMPAL Unofficial Editorial - editorial - CodeChef Discuss

1 Like
17

Can anybody help me figure out what is wrong with logic I have implemented for the problem CAR-PAL TUNNEL? I am getting a WA.link text

18

Matrix Exponentation

See the equation (T(n) means \cos nx for current problem.)

\begin{pmatrix} T(n) \\ T(n-1) \\ \end{pmatrix} = \begin{pmatrix} a & b\\ c & d \\ \end{pmatrix} * \begin{pmatrix} T(n-1)\\ T(n-2)\\ \end{pmatrix}

Now, for every linear recurrence, we have to fill this matrix with suitable values of a,b,c and d So as to make LHS = RHS.

For current problem, our recurrence is \cos(N∗X)=2∗cos(X)∗cos((N−1)∗X)−cos((N−2)∗X)

The values in Transformation Matrix shall be filled so that this equation is always satisfied. Then we will find (T-1)th power of this transformation matrix T, then

\begin{pmatrix}\cos nx \\ \cos (n-1)x \\\end{pmatrix} = {\begin{pmatrix} a & b\\ c & d \\ \end{pmatrix}}^{T-1}* \begin{pmatrix} cos x\\ cos 0\\ \end{pmatrix}

This way, we get our solution to recurrence. Also, the size of transformation matrix is the number of previous values needed to calculate current value.

This was all about Matrix Exponentation in brief. You can find more about Matrix Exponentaion from following links.

19

static long modInv(long b){
long p = MOD-2, out = 1;
while(p>0){
if((p&1)==1)out = (outb)%MOD;
p>>=1;
b = (bb)%MOD;
}
return out;
}
@taran_1407 can you explain how you take modInverse?

20

Part 3: Editorial of Chef and Land Labeling will be posted, if you people drop a comment below.

1 Like
21

The irrational was the downer for me. I decided to stick to all cos :3

22

Yeah for me too,bt didnt know anything except these basic formulas

1 Like