Level: Medium
Concepts: Matrices, Permanent of matrices
Problem link: http://www.codechef.com/CRNM2014/problems/CRANCBOY
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: http://en.wikipedia.org/wiki/Computing_the_permanent#Ryser_formula