siddhi's blog

By siddhi, history, 5 years ago, In English

Can some explain how to go about this question.

https://www.codechef.com/OCT19A/problems/JIIT

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it