Unofficial Editorials February Long Challenge (Part - 2)

editorial
, , , , ,
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
23

Check out my solution. Oh shit, I forgot adding links, right?

24

Thanks!!!

25

You sure its not O({log_N}^{2}) ? Because that solution got big TLE on its face.

26 
exceeded memory to store nx

What?

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?

Yes. Getting involved with decimals was all you needed to spend an eon on this problem and still be unable to crack it. Way too many round errors.

27

Well, real comedy was with me- random getting 70 points XDXD

28

@taran_1407 in ur second solution for <=1e6 how you deal with fraction parts.

29

I have represented d/l as d*modInverse(l), added that part in editorial too. Forgot to aad earlier.

1 Like
30

Well, for this problem, i wrote the solution, and submitted and woah, got 100 points in one go. Frankly, i was sure my implementation was right, but i wasn’t sure if my idea will work in tight bound cases.

And

There’s nothing bad in swallowing pride to ur code as long as ur code gets AC.

31

Broken clock alone kept me busy whole contest, than all other problems combined. So much it troubled me, that i didn’t get time to explore lucas theorem for more than 10 points, when i could have got 50 because i got the same idea as editorial 2 hours before end of contest.

32

I too messed up with fractions (includes creating my own fraction class) but kept getting overflow WA. only last day i took modInverse.

33

I would recommend you to read about modular arithmetic (especially modular multiplicative inverse). If we have a rational p/q, it can also be stated as p*(1/q) and (1/q) is same as modular multiplicative inverse.

I know this will appear confusing at first sight, but first read about modular multiplicative inverse.