PROBLEM LINK:
Author: Swapnil R. Mehta
Editorialist: Shiva Bhalla
DIFFICULTY:
MEDIUM
PREREQUISITES:
Bipartite Matching
PROBLEM:
N guests are to be seated in a stadium. There are 9 rows in the stadium, numbered from 1 to 9. Each row has certain number of seats, possibly 0. You need to find an arrangement in which guest 1 gets the seat in the best row possible out of his choice. Then you need to assign best seat to guest 2 and so on. All guests need to be seated.
QUICK EXPLANATION:
The problem can be reduced to finding matching in a bipartite graph. This can easily be solved using any bipartite matching algorithm.
EXPLANATION:
At first this problem appears to be a many to one matching problem because same row can be alloted to many guests but we can reduce this problem to bipartite matching if we consider each seat in each row as a single unit.
Lets number the seats from 0 to 100 such that seats in ith (indexing starts from 1) row will get numbers from i*10 to i*10 + (Ai-1). (There will be a few indexes in between which will not be having a seat.)
Let us create a bipartite graph G = (Guests,Seats,Edge) where vertices on left side correspond to n Guests and vertices on right side correspond to the possible seats.
Now we will create a matrix arr[i][j] which will denote whether or not ith guest has a preference for the jth seat ( Edge between vertex i on left side and vertex j on right side of the graph). If a guest has a preference for the kth row than he is assumed to have preference for all the seats in the row , ie. , ith guest will have 1’s from seats 10k to 10k+(Ak-1) in the matrix.
Now all we need to do is to apply any bipartite matching algorithm matching each of the guest with one of the seats of their preference. There is one more thing to be taken care of preference level of rows decreases from 1 to 9 and allotment should be such that guest numbered 1 should be alloted to row of as high preference as possible after that the second guest and so on for this we will start out allotment with the very first guest and try to allot him a seat of as low index as possible, then we do the same for 2nd guest and so on.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
Editorialist’s solution can be found here.