Problem 202 Dancing Pairs
Back to General discussions forum
My algorithm:
separate the female group with choices == 1
S = [p for p in pars if length(p[2])==1]store the female group in the array variable named
pairedF; store also the group of males in this group to the array varible namedpairedMfor s in S push!(pairedF,s[1]) push!(pairedM,s[2][1]) endfrom the group of females with choices > 1, remove the males in
pairedMS = map(Tmp) do tmp t = Int[] for m in tmp[2] m ∈ pairedM && continue push!(t,m) end tmp[1],t endthis will be the new set where the new S will be formed
S = [s for s in S if length(s[2])==1]Repeat 1 to 4 until there is no more.
The expected answer is 720. I submitted the answer of 733. Which is the length of the pairedF or females put into process.
More likely I am wrong because of the wrong algorithm.
How does one approach this problem?
Two observations:
- What if each (remaining) lady has at least two choices?
- What if two ladies have the same single choice? Do you split the gentleman in half? :)
With regard to possible algorithms, you can think of this as a graph in which you want to match the set of ladies with the set of gentlemen, and the edges are the expressed preferences. Such a graph is also called bipartite.
First paired are those with only one choice. They are the set processed and stored in pairedF, to be excluded in the next set to be processed. The males in this set is stored in the pairedM array, to be excluded in the next set to be processed.
The next set to be processed are those with the females excluded. The Julia script for that is
Tmp = [p for p in pars if (p[1] ∉ pairedF)]The remapping of that next set goes like this:
S = map(Tmp) do tmp t = Int[] for m in tmp[2] m ∈ pairedM && continue push!(t,m) end tmp[1],t endThen I do the procedures 1 to 3 until there is no more female sets to process.
To: gardengnome
I did as you recommended. I applied graphs bipartite to find maximum matching. I solved the problem. Thanks.