@l_returns How did this recurrence relation came?
1 Like
How you thought about this relation. Can you explain please?
2 Likes
@bhanu_3 @anon73162591 @ajraj27
God knows XD
I am still figuring out why this is correct. 
@taran_1407 might explain. He is editorialist 
2 Likes
Wut! 
was this a text book problem? Did everyone knew it before?
1 Like
This isn’t a 3D recurrence relation.
Mine with 8*log(n) runs in 0.12 secs
Your’s will be 27*log(n) which should run in 0.405
But does it seem like operator makes it slow ?
Nope 
You need some other skills to get this recurrence without understanding it 
1 Like
Basically f(x) is the number of arrays with length x and arr[x]!= arr[x-1]. Now you can either add a new element or add the same element and then a new element, both in m-1 ways
Like 1 3 4
I can make 1 3 4 4 !4 or 1 3 4 !4
!4 means a number not 4 so m-1 numbers
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).
5 Likes
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.
1 Like
Great man ! Now i guess I’ll have to wait for February CookOff😛 to get my lost ratings (and respect) back
2 Likes
Can you please share your code?
Unlucky me. I honestly saw this post. But just read inclusion exclusion thing and closed it XD
Wasted my time to get recurrence.
1 Like
I also became 5 star again
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.