×

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.

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

# SIMILAR PROBLEMS:

Stable Marriage Problem on Spoj

This question is marked "community wiki".

1667
accept rate: 0%

1243837

2

@ Tester- can u please explain the greedy approach in you solution..??

(11 Aug '12, 21:59)
1

Greedy: Simulate the visits to the houses in ascending order by time. For a current visit to a house if it is the last possible one to that house, then that person is locked here. (This is the approach I took but it gave me wrong answer, probably because of some bug I had, or maybe my algorithm is wrong??)

(12 Aug '12, 01:54) 4★

@lazzrov - i applied kinda same..i got WA too..waiting for tester to explain his part

(12 Aug '12, 02:20)
7

The editorial was good but one could more easily understand it with illustration . If you do want an illustration i guess this could help you to learn more easily and quickly.

Before u refer the link relate this to illustration. Just u can treat this problem as case where n people were to be allotted for n houses . Let given time[i][j] indicates rent offered by i'th person to j'th house owner (rent[i][j]) . People prefer to stay at with paying low rents . House owners prefer to allot the house for those who pay high rents. So, satisfying owners preferences you could get answer some sequence X1 and satisfying people preferneces you could get some answer sequence X2 , even sometimes X1 = X2 . There exists a solution for every case .

(12 Aug '12, 02:51)
1

Which testcase will give answer as -1 ??

(12 Aug '12, 05:52)
3

Since the stable marriage problem always has a solution, there is no testcase where answer = -1.

(12 Aug '12, 06:29) 5★
1

It would be great if the setter could make the naming convention more meaningful. Variable such as: ship, mx, my are very poor. It might be trivial to experienced programmers but it's very difficult to newbies to follow.

(13 Aug '12, 04:49) 2★

@lazzrov @shashank_jain - how do you decide "it is the last possible one to that house"? There can be someone supposed to visit the room later, but blocked before the visit. Try to identify the must-happen events(visits), process those greedily by time, and add new must-happen events as needed. (this one reminds me of closed hashing)

(13 Aug '12, 08:15) 5★

@tec You can keep in_degree[] array for the houses. When a house is visited you decrease its value by 1. If it reaches zero then the current friend is blocked in the house, and if it has any houses left that he could've visited, then you must also decrease their value in the in_degree[] array as well.

(13 Aug '12, 13:52) 4★

@lazzrov Then how do you process this input: 3 1 4 7 2 5 8 3 6 9

(13 Aug '12, 14:24) 5★

@tec Starting in_degree[] = {3,3,3}

Time 1: {2, 3, 3}

Time 2: {1, 3, 3}

Time 3: {0, 3, 3}. Because the degree for house 1 is zero, that means that friend 3 is locked here. Also because of the remaining visits 6 and 9, the degrees for house 2 and 3 are also decreased. So now we have {0, 2, 2}

Time 4: {0, 1, 2}

Time 5: {0, 0, 2}. Another zero. Friend 2 is locked in house 2. We have a visit left for house 3, so now its {0, 0, 1}

Time 6: Already processed when we locked a friend at Time 3

Time 7: {0, 0, 0} Another zero. We lock friend 1 in house 3.

Time 8 & 9: Already processed

(13 Aug '12, 19:50) 4★

@setter it would be really helpful for newbies like me if you explained your code a little bit. thanks in advance :)

(31 Oct '12, 23:56) 0★

Please,anyone help me.This problem is consuming my whole night ! Why i am getting wrong answer ?Is it a(1,2,3) possible answer for the given test case?https://www.codechef.com/viewsolution/16987838

(13 Jan, 01:55)
showing 5 of 13 show all
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,258
×1,188
×86
×15

question asked: 11 Aug '12, 15:04

question was seen: 4,508 times

last updated: 13 Jan, 01:58