Can someone explain their approach to the question JIIT from the October Long Challenge. Thanks in advance:)


Matrix multiplication

I tried something like this :

Rather than applying Q operations row-column, I considered performing Q operations on rows and columns independently. What I needed to calculate was Dp[Q] vector ith index would denote the number of permutations of Q length with exactly i elements with odd frequencies.

I came up with this recurrence:

DP( n, i) = i*DP( n-1, i-1) + (N-i)*DP( n-1, i+1)

But failed in this approach because I could not do that within Time Limit with Matrix Exponentation.

Cayley - Hamilton can be applied to solve this problem.
Firstly, the matrix for matrix multiplication is a tridiagonal matrix, and have a characteristic polynomial that can be found in O(n ^ 2).
Call our matrix M. From the polynomial M ^ (N + 1) can be represented in terms of M ^ 0 -> M ^ N. Our job is to find M ^ Q.
2 ways:

  • Find representations of matrices from M ^ (N + 1) -> M ^ 2N by the first N + 1 matrices, then use fpow. Complexity is N ^ 2 * logQ
  • Calculate the remainder of the polynomial x^Q with the found characteristic polynomial and this is our answer. Complexity is NlogNlogQ, overall N ^ 2 for a test.

The first way is sufficent for 90 points, and the second way is for 100

1 Like

Thank you :slight_smile: