Unofficial Editorials February Long Challenge (Part - 2)

editorial
, , , , ,
61

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

62

Well, you won’t have that much time for a problem.

and if you had, RIP your rating if the problem is out of first 3.

63

Hard for you to remain masked, now that you are a moderator too, an active contributor.

64

I have posted an answer because it wouldn’t fit in comment.

65

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.


66

@vijju123, please help with LaTex, Matrix isn’t getting right.

67

And what if I skip first 3 and dive at 5? Still RIP :frowning: :3 :stuck_out_tongue: XD

68

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?

69

Well, if u skip first 3, either u r too genius if u manage AC, and then solve others.

If u didn’t get AC in 5th and didn’t attempt, i will take it as intentional rating drop.

PS: I posted an answer below, but couldn’t get the LaTex right…, please help!!

70

Read about fermat’s little theorem, which states that if p is prime, then modular inverse of x can be found as x^(p-2) modulo p.

If p is not prime, but gcd(x, p) ==1 we may use extended euclid euclid algorithm.

All methods explained here https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/

1 Like
71

Sorry, didnt notice! Will do right away

72

Done @taran_1407 - sorry for delay.

73

Since I am a moderator, I cannot be masked lol. Else who will people go to resolve queries? XD People will be like “And the legend says that there is some strange force- called a moderator- which looks after the forums. Unseen to the eye, nobody has ever seen or heard any of him” XDXD

1 Like
74

Your conclusion that there are points for all the y-values isn’t true.

Construct a polygon with vertices:


10000   11111111
20000   22222222
40009   44454444
50018   55575555
50027   55585555
30045   33383333
20045   22272222
10036   11151111
   18      20000
    9      10000

There are just 13 internal grid points, which are at


10009 11121111
10018 11131111
10027 11141111
20009 22232222
20018 22242222
20027 22252222
20036 22262222
30009 33343333
30018 33353333
30027 33363333
30036 33373333
40018 44464444
40027 44474444
1 Like
75

why 10 , 11112 will not lie inside

this was

from geeks from geeks, i just check for for (10 ,11112) and its showing yes as output ?? why ?

76

Read comments there. The code and procedure given at geeksforgeeks for point inside a polygon is incorrect. I know because I had to write an editorial, and that thing failed on edge cases.

1 Like
77

@vijju123 i have check for most points… yes this g4g code is totally wrong … gives wrong output in most cases …