BLOCKING - Editorial

PROBLEM LINK:

Practice
Contest

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 :slight_smile:

SETTER’S SOLUTION:

Can be found here.

TESTER’S SOLUTION:

Can be found here.

SIMILAR PROBLEMS:

Stable Marriage Problem on Spoj

10 Likes

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

2 Likes

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??)

1 Like

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

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 .

6 Likes

Which testcase will give answer as -1 ??

1 Like

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

2 Likes

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.

1 Like

@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)

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

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

@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

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

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