STABLEMP: Getting wa

general
, , ,
1

I submitted this


(http://www.codechef.com/viewsolution/993482) for the [Stable Marriage Problem](http://www.codechef.com/problems/STABLEMP), but I am getting WA. I am unable to figure out the problem with the logic. Some helpful points about the code:

 1. The matrix **w** contains the preferences of the women. An entry w[i][j] stores the preference number of the ith woman for jth man.
 2. The matrix **m** contains the preferences of men, but in a different way. An entry m[i][j] stores the number of the woman that the ith man prefers at jth position in his preference list, i.e, if m[1][2]=5, then the 5th woman is the 1st man's 2nd choice.
 3. The array **wom** contains the list of men that the women are married to. wom[i] contains the number of the man that the ith woman is married to.
 4. The aray **man** contains the list of womean that the men are married to, but in a different way. If man[3]=4, then that means the 3rd man is married to the woman who is his 4th preference.
2

as the problem statement itself is very confusing and lacking some information, i’m sorry to tell you i won’t be able to help. how would you explain the sample test cases provided in the problem page ? i’m curious. thx :slight_smile:

3

@cyberax

From what I understood, initially no man is married to any woman. Then, the first man gets to marry the first woman in his preference list,say woman no. 4. Now, if the 2nd man also has woman no. 4 as his first preference, and if the 4th woman has a higher prefernce for the 2nd man than the 1st man, then man no. 2 gets married to woman no. 4, and the 1st man is married to the next available woman in his preference list. This accepted solution also does the same thing- http://www.codechef.com/viewsolution/702159