What is solution idea for the Solving the Practise Contest ? Is it related to finding recurrence and solving in O(log n) using exponentation or can it be solved using combinatorics ?
1 Like
Yes, the problem can be solved by finding a recurrence relation and then using matrix exponentiation. The DP state is:
DP[i][x][y][z] represents the number of ways of distributing i problems such that
- x is the number of problems done by first mod k. (0 <= x < k)
- y=0 means second has not done the current problem and y=1 means the current problem is given to second. (0 <= y < 2)
- z=0 means third has done 0 problems till now and z=1 means that third has done at least one problems till now. (0 <= z < 2)
We made a matrix of 40x40 (10 * 2 * 2) for the matrix exponentiation.
3 Likes