CRANCBOY - Editorial

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

//