# BLOCKING - Editorial **URL:** \ **Category:** editorial\ **Tags:** aug12, editorial, graphs, matching\ **Created:** [August 11, 2012, 3:04pm UTC](https://discuss.codechef.com/t/blocking-editorial/474 "2012-08-11T15:04:59Z")\ **Posts on this page:** 14\ **Page:** 1
**Author:** ![nikhil\_adm](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@nikhil\_adm](https://discuss.codechef.com/u/nikhil_adm)\ **Post date:** [August 11, 2012, 3:04pm UTC](https://discuss.codechef.com/t/blocking-editorial/474/1 "2012-08-11T15:04:59Z")
### PROBLEM LINK: [Practice](http://www.codechef.com/problems/BLOCKING) [Contest](http://www.codechef.com/AUG12/problems/BLOCKING) ### 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](http://www.codechef.com/download/pic.jpeg) 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](http://en.wikipedia.org/wiki/Stable_marriage_problem) 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](http://www.codechef.com/download/Solutions/2012/August/Setter/BLOCKING.cpp). ### TESTER’S SOLUTION: Can be found [here](http://www.codechef.com/download/Solutions/2012/August/Tester/BLOCKING.c). ### SIMILAR PROBLEMS: [Stable Marriage Problem on Spoj](http://www.spoj.pl/problems/STABLEMP/) ---
**Author:** ![shashank\_jain](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shashank_jain/32/163_2.png) [@shashank\_jain](https://discuss.codechef.com/u/shashank_jain)\ **Post date:** [August 11, 2012, 9:59pm UTC](https://discuss.codechef.com/t/blocking-editorial/474/2 "2012-08-11T21:59:55Z")
@ Tester- can u please explain the greedy approach in you solution…?? ---
**Author:** ![lazzrov](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@lazzrov](https://discuss.codechef.com/u/lazzrov)\ **Post date:** [August 12, 2012, 1:54am UTC](https://discuss.codechef.com/t/blocking-editorial/474/3 "2012-08-12T01:54:15Z")
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??) ---
**Author:** ![shashank\_jain](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shashank_jain/32/163_2.png) [@shashank\_jain](https://discuss.codechef.com/u/shashank_jain)\ **Post date:** [August 12, 2012, 2:20am UTC](https://discuss.codechef.com/t/blocking-editorial/474/4 "2012-08-12T02:20:18Z")
@lazzrov - i applied kinda same…i got WA too…waiting for tester to explain his part ---
**Author:** ![phanindhar](https://discuss.codechef.com/user_avatar/discuss.codechef.com/phanindhar/32/118_2.png) [@phanindhar](https://discuss.codechef.com/u/phanindhar)\ **Post date:** [August 12, 2012, 2:51am UTC](https://discuss.codechef.com/t/blocking-editorial/474/5 "2012-08-12T02:51:45Z")
The editorial was good but one could more easily understand it with illustration . If you do want an illustration i guess [this](http://mathsite.math.berkeley.edu/smp/smp.html) 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 . ---
**Author:** ![sakuag333](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@sakuag333](https://discuss.codechef.com/u/sakuag333)\ **Post date:** [August 12, 2012, 5:52am UTC](https://discuss.codechef.com/t/blocking-editorial/474/6 "2012-08-12T05:52:15Z")
Which testcase will give answer as -1 ?? ---
**Author:** ![neil\_812](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@neil\_812](https://discuss.codechef.com/u/neil_812)\ **Post date:** [August 12, 2012, 6:29am UTC](https://discuss.codechef.com/t/blocking-editorial/474/7 "2012-08-12T06:29:42Z")
Since the stable marriage problem always has a solution, there is no testcase where answer = -1. ---
**Author:** ![tyrant](https://discuss.codechef.com/user_avatar/discuss.codechef.com/tyrant/32/437_2.png) [@tyrant](https://discuss.codechef.com/u/tyrant)\ **Post date:** [August 13, 2012, 4:49am UTC](https://discuss.codechef.com/t/blocking-editorial/474/8 "2012-08-13T04:49:28Z")
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. ---
**Author:** ![tec](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@tec](https://discuss.codechef.com/u/tec)\ **Post date:** [August 13, 2012, 8:15am UTC](https://discuss.codechef.com/t/blocking-editorial/474/9 "2012-08-13T08:15:12Z")
@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) ---
**Author:** ![lazzrov](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@lazzrov](https://discuss.codechef.com/u/lazzrov)\ **Post date:** [August 13, 2012, 1:52pm UTC](https://discuss.codechef.com/t/blocking-editorial/474/10 "2012-08-13T13:52:10Z")
@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. ---
**Author:** ![tec](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@tec](https://discuss.codechef.com/u/tec)\ **Post date:** [August 13, 2012, 2:24pm UTC](https://discuss.codechef.com/t/blocking-editorial/474/11 "2012-08-13T14:24:33Z")
@lazzrov Then how do you process this input: 3 1 4 7 2 5 8 3 6 9 ---
**Author:** ![lazzrov](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@lazzrov](https://discuss.codechef.com/u/lazzrov)\ **Post date:** [August 13, 2012, 7:50pm UTC](https://discuss.codechef.com/t/blocking-editorial/474/12 "2012-08-13T19:50:38Z")
@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 ---
**Author:** ![patronus](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@patronus](https://discuss.codechef.com/u/patronus)\ **Post date:** [October 31, 2012, 11:56pm UTC](https://discuss.codechef.com/t/blocking-editorial/474/13 "2012-10-31T23:56:41Z")
@setter it would be really helpful for newbies like me if you explained your code a little bit. thanks in advance 🙂 ---
**Author:** ![ehsan\_sshuvo](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@ehsan\_sshuvo](https://discuss.codechef.com/u/ehsan_sshuvo)\ **Post date:** [January 13, 2018, 1:55am UTC](https://discuss.codechef.com/t/blocking-editorial/474/14 "2018-01-13T01:55:31Z")
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?[CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/16987838)