### 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.