Please share your approach for Construct Array [CARR]
I know for a fact that we need to calculate the invalid sequences and subtract from total possible sequence. but how to calculate invalid sequences?
Meanwhile
Please share your approach for Construct Array [CARR]
I know for a fact that we need to calculate the invalid sequences and subtract from total possible sequence. but how to calculate invalid sequences?
Meanwhile
F(1) = m
F(2) = m*m
F(n) = (m-1)*( F(n-1) + F(n-2) ) for n \ge 3
is the recurrence relation for answer.
You can find F(n) in O( log_2(n) ) using matrix exponentiation (Type 2).
But wouldn’t a DP solution exceed time limit?
@2below Oh, ok thanks!
can you breifly explain how that relation came?
Yes I have edited my answer. Check it.
How you thought about this relation. Can you explain please?
@bhanu_3 @anon73162591 @ajraj27
God knows XD
I am still figuring out why this is correct.
@taran_1407 might explain. He is editorialist
Wut! was this a text book problem? Did everyone knew it before?
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
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:
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.
Great man ! Now i guess I’ll have to wait for February CookOff😛 to get my lost ratings (and respect) back
Can you please share your code?