GEHA1801 - Editorial







  • Matrix Exponentiation


There are three people (Sherlock, Watson and Mycroft) and N problems. Each problem will be solved by only one person and that can be any of the three people. But there are a few conditions that are to be met. The conditions are:

  • Mycroft can solve at most 1 problem of any 3 consecutive ones.
  • Watson can solve any number of questions but not 2 consecutive (Basically 1 problem of any 2 consecutive ones).
  • Sherlock can solve at most 2 problems of any 4 consecutive problems.

Your task is to find the number of ways they can solve the N problems.


O(logn*64^3) for each test case


Finding the recurrence relation, building up the matrix and using matrix exponentiation to calculate answer for N problems.


Step 1 (Recurrence Relation):

We define a state <b><i>f(n, i, j, k)</i></b> as number of ways of solving <b><i>n</i></b> problems and
	<li><b><i>i</i></b> is a 2 bit number indicating whether the last two problems were solved by Mycroft or not.</li>
	<li><b><i>j</i></b> is a 1 bit number indicating whether the last problem was solved by Watson or not.</li>
	<li><b><i>k</i></b> is a 3 bit number indicating whether the last three problems were solved by Sherlock or not.</li>
In each masked number <b><i>i, j and k</i></b>, if the <b>bth</b> bit from the last is set, then that means that the last bth problem was solved by him, othewise not.

Example say k = (100)<sub>2</sub> : This indicates last problem was solved by Sherlock while 2nd and 3rd last were not.


	<li>If <b><i>j = 0</i></b> then Watson can solve the <b><i>nth</i></b> problem hence:
		<b><i>f(n, i, j, k) += f(n - 1, i, 1, k)</i></b></li>
	<li>If <b><i>i</i></b> has number of set bits < 1 then Mycroft can solve the <b><i>nth</i></b> problem hence:
		<b><i>f(n, i, j, k) += f(n - 1, (i << 2) + 1, j, k)</i></b></li>
	<li>If <b><i>k</i></b> has number of set bits < 2 then Sherlock can solve the <b><i>nth</i></b> problem hence:
		<b><i>f(n, i, j, k) += f(n - 1, i, j, (1 << k) + 1)</i></b></li>


<b>Step 2</b>

Since f(n,*) depends on f(n-1,*) the problem can be converted to matrix exponentiation problem with dimensions corresponding to parameters that are part of *.

Here DP solution uses more than 1 dimension other than n , but they can be combined together into a single parameter.

Let mask be 6 bit variable , 

Least 3 significant bits indicate sherlock's status on last 3 problems 

4th least significant bits indicate watson's status on last problem.

	other 2 bits indicate mycroft's status on last 2 problems.

s = (k>>0)&7;

w = (k>>3)&1;

m = (k>>4)&3;

Now using conditions of recurrence described above we can create the matrix.

<b>Step 3</b>

In a general matrix expo problem we have equation of form <b>A <sub>n</sub> = T A<sub>n-1</sub></b>

A<sub>i</sub> is column matrix with dimension of 2<sup>6</sup> (in this case)

i<sup>th</sup> storing number of solutions with status flag after solving last problem be <b>i</b>

if F(n,i) = ... + x * F(n,j) + ...

<b>T[i][j] = x</b>


  • Author's solution : Link
  • Tester's solution : Link