unlucky me too dont got time to see why I am getting tle in my original solution can you explain my solution link is
please check it
1 Like
dont worry I never reached 5 stars .
once I got the chance in October lunchtime but unluckily it was made unrated . But one day I will reach definitely
2 Likes
DON’T ever use endl
It’s super slow.
Also I think modulo and loops are causing TLE.
Mine is gfg code. Seems like its quite fast.
ohk I first looked to find it on geeks but I thought that why everytime on geeks we must experiment other resources too so I found this code but I commited a mistake but my star was saved at border ]
1802…
I had TLE until I added “&” after the parameter type in my multiplication operator for matrices. This passes the arrays by pointers but then deals with them as normal.
But, I also made one more change. I removed this mod I highlighted from the mult.
If you already have A[i][k], B[k][j] and C[i][j] mod 10^9 + 7 and ≥ 0, then this mod operation is unnecessary for long long matrices.
C[i][j] = (C[i][j] + A[i][k] * B[k][j] % mod) % mod;
What would go wrong with the following formula?
Formula:
Where gives all possible sequences and
gives all the unacceptable sequences for all 1…M integers.
1 Like
Done. 
2 Likes
Hi,
I arrived at the same recurrence to solve the problem. I referred to a different article on geeksforgeeks https://www.geeksforgeeks.org/matrix-exponentiation/ regarding the implementation. Both your code and my code feel the same to me. Can you please point out (if possible) if there is any difference you are able to find in my solution. Thanks.
1 Like
@l_returns
Dude… Can you explain how did you get this correct without knowing exact proof ?
Did you take nap in between and it came to your dream right ?(i do not thing so)
LOL…
1 Like
You’ll know if you’re saved or stuck in next contest XD
Just see answer for few test cases and solve it 
1 Like
Nice, expected answer 
1 Like
@l_returns is right. Sometimes solving for small test cases will give you the idea of formula… I’ve done it before, it doesn’t always work but experienced coders might get an idea of recurrence
1 Like
ya but hope good for future always I think by the way you are a great coder can you help me out solving my problem currently. what I am facing?
problem:- I know these basic and somewhat advanced data structures and algorithms required for solving cp questions some too advanced like HLD or Offline Queres or FFT’s might be missing but can You give me a correct approach for how to practice more and more problems with right available stuff and guide me in right direction as per my performance you can take your time to answer that because it is a serious question . I want to improve more and reach at a nice level of cp. Moreover can you help me in choosing out right source for practicing among heaps of available online.
i am highly grateful to you in helping me for months on this discussion forum
2 Likes
I saw this problem now.
I use good-ways/bad-ways method of dp, and here is my solution if it helps :-
https://www.codechef.com/viewsolution/29189211
Applying matrix-expo on it should give 100, AC I feel. @anon73162591
2 Likes
I think you should try some codefores and some Codechef contests and obviously long challenge. Just keep participating and upsolve after it ends. Upsolving will help a lot. I have seen that most of the coders ( including me ) don’t have that energy or motivation to upsolve problems after a contest. If you keep that energy and motivation then I believe you’ll perform much better than others.
I don’t practice at all. I just directly participate in contests. Idk if it affects my performance but this is what I did. Don’t have much time and motivation to practice.
2 Likes
I found a way to derive this recurrence from editorialsit’s explanation.
Let f(n, 2) denote the number of arrays of length n such that last 2 elements are same, and f(n, 1) denote the number of arrays of length n such that last 2 elements do not match.
Using the editorial it is clear that:
1.f(n,1)=(m−1)∗(f(n−1,1)+f(n−1,2)) (i)
2. f(n,2)=f(n−1,1) (ii)
3. The solution to the problem is f(n,1)+f(n,2) (iii)
Let us denote the solution to the problem by F(n). Then using (iii)
F(n) = f(n,1)+f(n,2) (iv)
Consider the equation (i) f(n,1)=(m−1)∗(f(n−1,1)+f(n−1,2))
Replacing n by n-1 gives f(n-1,1)=(m−1)∗(f(n−2,1)+f(n−2,2))
Hence equation f(n,2)=f(n−1,1) becomes f(n,2)=(m−1)∗(f(n−2,1)+f(n−2,2))
Plugging these new values in the equation (iv) gives,
F(n) = (m−1)∗(f(n−1,1)+f(n−1,2)) + (m−1)∗(f(n−2,1)+f(n−2,2))
F(n) = (m−1)∗F(n-1) + (m−1)∗F(n-2) (using the equation (iv))
F(n) = (m−1)∗(F(n-1) + F(n-2))
As far as the base cases go, F(1) = m and F(2) = m*m
And hence we get a Fibonacci linear recurrence with different coefficients.
The transformation matrix would be \begin{bmatrix} 0 & 1 \\ m-1 & m-1 \end{bmatrix}
And the coefficient matrix would be \begin{bmatrix} m \\ m^2 \end{bmatrix}
Hope this makes the derivation part clearer.
1 Like
Hope this helps
Hope this will help you