Solution for solving the Practice Contest

acm-icpc
kanpur

#1

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 ?


#2

Yes, the problem can be solved by finding a recurrence relation and then using matrix exponentiation. The DP state is:

DP*[x][y][z] represents the number of ways of distributing i problems such that

  1. x is the number of problems done by first mod k. (0 <= x < k)
  2. y=0 means second has not done the current problem and y=1 means the current problem is given to second. (0 <= y < 2)
  3. 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.