Can someone explain their approach to the question JIIT from the October Long Challenge. Thanks in advance:)
4 Likes
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 