PROBLEM LINK:
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Graph theory, Graph matchings, Stable Marriage Problem
PROBLEM:
There are N people and N houses. Each person will visit each house at some time
according to a predefined schedule. We need to find a distinct house for each
person so that when that person visits that house, he is locked in there.
Further this allotment should be done in such a way that once person A is locked
in house H at time T, no other person visits house H after time
T.
Your task is to find such an allotment of houses.
QUICK EXPLANATION:
Model this problem in stable marriage problem. Use Gale-Shapley algorithm to
solve it.
DETAILED EXPLANATION:
This is one of my personal favorite problems from this contest. At its heart it
is a semi-standard problem which is taught during several algorithm courses but
is concealed nicely.
The best way I can think of to explain the solution of this problem is to
directly introduce the Stable Marriage Problem and then model our problem in
terms of SMP.
Let’s say there are N men and N women. Each man has rated each women and each
women has rated each man. Now we want to make N couples out of these N
men and N
women matching a man to a woman.
We also want our match making to be stable. What does that mean? Let’s say
M1 is
married to W1 and M2 is married to W2. If M1 prefers W2 over
W1 and W2 prefers
M1 over M2, M1 and W2 could as well break their current marriages and marry with
each other. So we want our match making to be stable such that no man and no
woman have an incentive to break their marriages and marry each other. More
formally for all (M1, W1) and (M2, W2) pairs, either M1 prefers
W1 over W2 or W2
prefers M2 over M1. It can be shown that a stable marriage system always
exists.
Now when we know what is SMP, let’s start to model this problem. All friends can
become men and all houses can become women. This part is simple. What we want
here is also a matching. But we need to create preferences of both people and
houses and that too in such a way so that constraints of this problem change
into constraints of stable marriage problem.
Let’s say a friend F prefers house H1 over house H2 if he visits
H1 first in
his own schedule. Also house H prefers friend F1 over friend F2 if
F1 visits H
after F2 does.
We’ll now prove that constraints of the problem are identical to the constaints
of SMP and any solution set of SMP is same as solution set of this problem. Let’s
look at this image before moving forward.
Claim 1 : If an allocation exists that matches constraints of the problme, that
allocation is also a solution to SMP assuming the preferences defined above.
Proof : Assume if possible this allocation is not a solution to SMP. This
implies there exists matched pairs which can be broken to marry each other.
Let’s say F1 and H2 want to marry after breaking their current marraiges
(F1,H1) and
(F2, H2). What it means is that F1 prefers H2 over H1 and also
H2 prefers F1
over F2. This means that : T3 < T1 and T3 > T2
These two together mean that T2 < T3 < T1.
But this is a contradiction to the fact that given allocation satisfied
constraints of the given problem. Why? Because F2 has settled in house
H2 at
time T2. F1 settles at time T1 and as T3 < T1, he goes to house
H2 at time T3
but at that time both F1 and F2 would be in house H2.
Hence our assumption was wrong => Every solution to given problem is a solution
to SMP.
Hence proved.
Claim 2 : Every solution to SMP under the preference set as described above is a
solution to our problem as well.
Proof : Assume this is not the case. There exists some SMP solution which is not
a solution to our problem => In this solution some friend visits other friend
after he has settled. Without loss of generality, assume that F2 is the friend
and he goes to home H1 where F1 is already settled. As F2 is still moving, he
has not settled => T4 < T2. Also as F1 has already settled, T1 < T4. These two
together imply that T1 < T4 < T2. But this violates the fact that given
allocation
was a solution to SMP problem as now F2 and H1 can break their current marriages
and marry mutually.
So our assumption was wrong => every solution to SMP is indeed a solution to our
problem.
Hence proved.
From claim 1 and claim 2, solution set of this problem is same as solution set
of stable marriage problem. You can read about SMP in detail at Wikipedia or your favorite algorithm text book.
Of course one din’t need to know SMP explicitly to solve this. Our tester wasn’t aware of SMP and he still came up with a similar greedy solution on his own 
SETTER’S SOLUTION:
Can be found here.
TESTER’S SOLUTION:
Can be found here.
