I used a slightly different recurrence relation. Here’s how it goes:
I build the number of solutions that is the answer to the problem starting from Array Size = 2 and up to N.
Consider 2 types of solutions:
Solutions where last 2 elements are the same. Name this Sols_Same
In this case for Array size 2, we have m solutions, namely where each element from m appears twice successively.
Solutions where the last 2 elements are different. Name this Sols_Different
In this case for Array size 2, we have m x (m - 1) solutions, a choice for m in the 1st Array position, then we’re left with m - 1 choices left that are different from the 1st choice.
Then the recurrence relation will be as follows: Sols_Same(n) = Sols_Different(n - 1) Sols_Different(n) = ( Sols_Same(n - 1) + Sols_Different(n - 1) ) x (m - 1)
For the 1st one, the explanation is that to extend a solution from n - 1 to n where the last 2 elements are the same, I can extend all those from Sols_Different(n - 1) with exactly one possible choice (the one where the last element is duplicated). And also, I can’t extend any solution from Sols_Same(n - 1) to this type.
For the 2nd recurrence relation, the explanation is that for both types of solutions from n - 1, I can extend all solutions from both types with m - 1 possible choices for each, namely the one where I choose an element different from the last one.
Final solution will be Sols_Same(n) + Sols_Different(n). You can construct a matrix for the recurrence relation and compute fast the solution in log(n) time.
For me I think the hard part was figuring out I only need to keep track of the state of the last 2 elements (different or equal).
This is my approach to this problem
let A(n) be valid sequences having first two digits equal to ‘m’.
let B(n) be valid sequences having first digit equal to ‘m’ and second digit different.
let C(n) be valid sequences having first digit different than ‘m’.
You can easily notice that
A(n+1) = B(n)
B(n+1) = C(n)
C(n+1) = (m-1)*(C(n)+B(n))
Our answer is A(n) + B(n) + C(n).
Let t(n) be the number of ways of filling the first n spaces that satisfy the conditions. Now
t(n)=t(n-1)*m-(m-1)*t(n-3), since there will be a case when n,n-1,n-2 are same. So number of ways for that to happen are (m-1)*t(n-3), since these numbers can be anything except a[n-3]. So we subtract this.
I think this recurrence also works but yeah maybe the % is causing issues.
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
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;
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.
@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…
