Q3.(a) Haloween party is just finished. You and your friends are still very excited and hope to have another party on Nov 2, 2020. Now, you come up with an idea — social dance party, and you are the coordinator of this party. Assuming there are $n$ men and $n$ women. In this party, each man need to pair with a woman, and you know, each of you have partner preference in your mind. So, you, as a coordinator, you need to pair them so that the ‘pair rate’ is maximized.¶
$n$ men is numbered from $1$ to $n$, $n$ women is also numbered from $1$ to $n$. For each man, it has preference of choosing women, similar for each woman.¶
For example, if man $b$ and woman $g$ is paired, the pair rate equals $1$ if woman $g$ is in man $b$’s preference list or vice versa, and $0$ otherwise.¶
The overall pair rate is the sum of each pair’s pair rate.¶
filename: Q3_a.py¶
input file: Q3_a_input.py¶
output file: Q3_a_output.py¶
sample input: (the first line is the number of men, it is also the number of women, the coming $n$ lines corresponds to the preference list of men from man $1$ to $n$, the last $n$ lines corresponds to the women’s preference list, if a line is $0$, that means the corresponding man or woman has no preference.)¶
3
1 2
0
3
0
3
0
sample output:¶
2
time: 45 seconds¶
Q3.(b) Now, assuming each man and woman will set their preference ranking from $1$ to $n$, if a man $b$ and a woman $g$ is paired, their score will the the multiplication of the rankings. It is obvious that, the sum of the pairing score need to be minimized, what is the minimized value?¶
sample input: (the first line is the number of men, it is also the number of women, the coming $n$ lines corresponds to the priority preference rating of men from man $1$ to $n$, the last $n$ lines corresponds to the women’s priority preference)¶
3
1 2 3
3 1 2
1 3 2
2 1 3
1 2 3
1 2 3
sample output (man 1 – woman 3, man 2 – woman 2, man 3 – woman 1):¶
8
time: 60 seconds¶
In [ ]: