GEHA1801 - Editorial

PROBLEM LINKS:

Practice

Contest

DIFFICULTY:

Medium

PREREQUISITES:

  • Matrix Exponentiation

PROBLEM:

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.

COMPLEXITY : 

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

CORE IDEA BEHIND THE PROBLEM :

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

EXPLANATION :

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
<ul>
	<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>
</ul>  
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.



<b>Recurrences:</b> 

<ul>
	<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>

</ul>

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

SOLUTION LINK:

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