help in solving STABLEMP

help
,
#1

problem : https://www.codechef.com/problems/STABLEMP

code : https://ideone.com/Kl9S4w

approach : in the men and women array i store the position of the desired women(i.e. for that men what is the position(priority) of xth women) and then store all the possible pairs and then try to sort that pairs using the information from the table. I have sorted on the basis of priority of marriage for the selected two person and then just select greedily.

please tell me where i am thinking wrong!

please tell the correct approach!

#2

The problem isnt there. If you comment the women’s line and keep mens line, then also runtime error goes away. If you commend build and sort lines, then also it goes away. You will have to rely on seeing how your code is executing on that TC. Its most probably some out of index thing with the build function, the input taking loops seem ok.

#3

Hi @pk301,

The line that you mentioned in the question is not giving the RE. You need to improve your cmp function as it is the one resulting in the RE. Have a look at this code.

The output of this code shows you that your sort method goes into an infinite loop due to error in cmp function.

1 Like
#4

by commenting the build line only it still showing RE!

#5

it went away on my machine. Undefined behaviour is weird :confused: . Let me see. BTW, what about the sort function? Is your cmp function error free?

#6

i think yes, because i use the same cmp and had done bubble sort and it works fine there !

#7

i have also noticed that by doing the same ‘cout’ but can you please tell me the reason why this func is not working properly?(i have added the problem link in the question).

#8

Try making the “<=” sign as “<”. My instinct says it should work fine :p. I feel its a case of

"I am getting true here, so put swap their places"

and then "I am again getting true. Lets swap again"

And then "Lets swap again, I am getting true"

And then
.
.
.
.
upto infinity (proved via Mathematical Induction) :p
2 Likes
#9

thanks a ton for this. RE goes away :slight_smile:

#10

can anyone please tell me the approach how to solve this question ?

#11

If I recall correctly, I came across this marriage problem while reading about bi-partite graphs. This is actually a standard question. Of course, you can make your own ad hoc approach, but the main aim is to familiarize you with standard method. In case you didnt give that a read, please do.

1 Like
#12

@vijju123 thanks again for this! helped me a lot :slight_smile:

can you please tell me the source where from you read graphs?