PROBLEM LINKS:
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: