How did you guys solve Construct Array [CARR]

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? :slightly_frowning_face:

Meanwhile

8 Likes

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

10 Likes

But wouldn’t a DP solution exceed time limit?

@2below Oh, ok thanks!

1 Like

can you breifly explain how that relation came?

1 Like

Yes I have edited my answer. Check it.

2 Likes

@l_returns How did this recurrence relation came?

1 Like

How you thought about this relation. Can you explain please?

2 Likes

Why does this code give TLE. Is there some problem with matrix exponentiation?

@bhanu_3 @anon73162591 @ajraj27
God knows XD
I am still figuring out why this is correct. :pensive:
@taran_1407 might explain. He is editorialist :smiley:

2 Likes

Wut! :laughing: 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 :stuck_out_tongue:
You need some other skills to get this recurrence without understanding it :wink: :stuck_out_tongue:

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:

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

if you would have googled out during the contet time
solution on stack overflow

My code : https://www.codechef.com/viewsolution/29167114