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