Approach for the question Crime Management (codeforces 107 D)

I cannot understand how to solve this problem using matrix exponentiation and also how should i calculate the transition matrix.
And more specifically this paragraph in editorial :

“The key step to solve the problem now is to notice that each transition from the solution for the first k crimes to the solution for the first (k + 1) crimes can be seen as multiplying the vector of the current state by the transition matrix. Once all possible transitions are converted to the matrix form, the problem can be solved by raising the matrix into n-th power. Raising the matrix into large power can be done efficiently using matrix exponentiation: on some steps instead of computing Ai + 1 = Ai· A0 one can compute A2i = Ai· Ai.”

I mean what transition matrix to multiply.

Question Link: http://codeforces.com/problemset/problem/107/D

Editorial Link: http://codeforces.com/blog/entry/2514

Thanks in Advance!!

1 Like

Can anyone please help!!

1 Like

Any hint would be helpful!!!

1 Like

Ohk ,i got it.

Just in case if anyone would need help,i am telling.

See there can be atmost 123 different combinations of that crimes,so lets say i calculate all of them.So combinations could be (2,1,1),(1,3,1),(0,0,0)

We want the value of (0,0,0) after n crimes.Lets say we have input for crimes as

A 3

B 3

C 3

Now lets define dp,dp(curr)(x,y,z) = dp(prev)((x-1+A)%A),(y-1+B)%B,(z-1+C)%C). ---------(1A)

So lets say to calculate dp(2,2,2)=dp(1,2,2)+dp(2,1,2)+dp(2,2,1)

Now lets hash the vectors(or number them)

Lets say (2,2,2) is 0,(1,2,2) is 1,(2,1,2) is 2 ,(2,2,1) is 3

Lets say dp(prev)(1)=3,dp(prev)(2)=4,dp(prev)(3)=1,dp(prev)(0)=1

So now lets represent 1A in matrix form

Prev=

 0.  1.  2.  3


[1.  3.  4.  1]

Just to make u understand the transition matrix lets say dp(0)=dp(1)+dp(2),dp(1)=dp(2)+dp(3),dp(2)=dp(3)=0

(This is actually column transposition)

So we can have a transition matrix as

Trans=

[
0 0 0 0
1 0 0 0
1 1 0 0
0 1 0 0
]

So curr = prev*trans

So this could be considered the vector after 1 crime,so after n crimes

If init is the vector after 1 crime
Curr=init*pow(trans,n)

1 Like