Level: Medium
Concepts: Matrices, Permanent of matrices
Problem link: CodeChef: Practical coding for everyone
The question asks you to determine the permanent of the matrix in disguise. It can be calculated using Ryser’s method in O(n^2 * 2^n) time but it needed to be optimised to run in O(n * 2^n) time by processing the sets in gray code order.
Useful links: Computing the permanent - Wikipedia