Stable Marriage Problem

"This problem always has a solution and your task is to find one." does that mean that a test case could have two answers?

Yes.

my code is taking around 2.7 sec on my laptop for n==500.

Still while submitting am getting Time Limit Exceeded

I have checked the corner cases and i dont think my code will go in infinite loop in any of them.

P.S. am assuming n > 0

Any pointers is much appreciated. submission Id: 115016

Is the preferences of women/men given sequentially (1,2,3,4 ... so on) as shown in problem sample input?

or coult it be like this too?

4 4 3 1 2
1 4 3 1 2
3 1 3 4 2
2 2 1 3 4

@admin for the case where n=7, isn't

1 4

2 7

3 1

4 6

5 5

6 3

7 2

a solution?

"if a man m prefers some woman w more than his wife, and w prefers m more then her husband a new marriage occurs between w and m. If w prefers her husband more, then she stays married to him."

in case of n=7 and m=2, the solution given is w=5.

man 2 prefers woman 5 over his wife, however woman 5 prefers her own husband over man 2.

how is the solution correct?

This problem should be in the "Easy" section.

I am getting a WA , working fine for test cases above , any corner cases , i even tried to add an extra n in last solution.

Something that i may be missing ??

any hints ?? corner cases ?? code worrks fine for above cases .

still looking for workarounds ..

I dont seem to find any corner cases in this one . I am getting WA , code is working for above two test cases .

@admin -  isn't the point made by Shreyas above correct ? isn't the second test case incorrect ? Kindly reply.

Shreyas' point makes no sense. Man 2's wife IS woman 5, so how could he prefer woman 5 to his wife?

Thanks for reply Stephen....but how can you say man 2's wife is 5? It is just that 2's first preference is 5. I am assuming in the beginning that (before this input) ith man is married ith woman, is that assumption correct ?

You have to decide who marries who in a way that satisfies the conditions. In the sample output, man 2 is married to woman 5, and doesn't prefer any other woman who prefers him to their husband. I'm not really sure what you're asking.

got you, thanks...I am getting correct answer for the above inputs but it's giving wrong answer here. some corner test cases may help.

Since it is very easy to check whether an output is correct or not, you can generate your own test cases and check your answer is correct very easily, even for n=500. There aren't really any corner cases that are more special than others.

"If w prefers her husband more, then she stays married to him."

But where is it given that i'th woman husband is j'th man ?

You have to output a set of marriages that is stable; ie where nobody would marry somebody else due to those conditions.