Can someone please explain the solution to the problem Good Boy Eshwar asked in SHAASTRA-2014 contest?.

1 Like

Define the state to be (indexOfMale,BitMaskOfChosenGirls). The basic idea is to iterate over the set of males until a choice has been made for each one of them. Which means that we look for the possible match for a guy with a girl if she’s not in the `bitmask`

=> if she’s available then set that bit and go for the next guy(index). This way try with all the indices associated with the current `indexOfMale`

. Count 1 if a choice could be made for every guy.

Simply put,

`f(idx,mask) = 1 if idx==N = f(idx+1,mask|(1<<k)) if(mask[k] is not set) for all k in adj[idx] `

Complexity would be `O(N*N*2^N)`

3 Likes