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