KGP16A-Editorial

general
, , , ,
1

PROBLEM LINK:

Contest
Practice

"Seatter"-
(Will you get the pun? You wont! :stuck_out_tongue: )
Tester- Kamil Debowski , Animesh Fatehpuria
Editorialist- Abhishek Pandey

DIFFICULTY:

HARD

PRE-REQUISITES:

Dynamic Programming (3-D OR memoization+2-D)

PROBLEM:

There are N seats in a theatre, and each of the N people have a preferred seat Seat[i]. Now, each of person also has a preferred direction D_i. He will enter the theatre, go to his preferred seat Seat[i]- if its unoccupied, he will occupy it, else he will go to his preferred direction D_i and occupy first unoccupied seat. If all seats are occupied in that direction, he will exit the theatre. Given preferred seats, we need to find number of ways to assign directions D_i such that no one leaves the theatre.

QUICK EXPLANATION:

We can do this either by 3-D dynamic programming, or by memoization and 2-D dp.

For 3-D dp, let dp[k][i][j] represent when seating first k people in interval [i,j]. Our base case is, dp[a][b][c]=1 whenever b > c, i.e. whenever start of interval is greater than end of interval. We can prove that its always possible to get at least 1 assignment of direction so that no one leaves the theatre.

Then, our recurrance relations are-

               long long & me = dp[k][i][j];
				if(!(i <= a[k] && a[k] <= j)) {
					me = dp[k-1][i][j];
					continue;
				}
				for(int t = i; t <= j; ++t) {
					me += dp[k-1][i][t-1] * dp[k-1][t+1][j] * (t == a[k] ? 2 : 1);
				}

The 2-D recursive approach will be discussed in detail in the editorial. It has same base case. Its recurrance relation is-

if(PeopleObtained==0 and personSeated==seatsToFill)//If we can seat Last person entering interval [i,j] at current seat.
        {
            val+=solve(start,i-1)*solve(i+1,end)*(i==arr[lastPerson]?2:1);
        }

EXPLANATION:

This is actually a hard question. So far, only four people have done it in practice!! I will recommend reading the editorial of the question Optimal Partition first in case dp is not your piece of cake. I have given links to refer to there, adn tried to give reader an insight to intuitive dynamic programming.

The editorial will focus in the recursive, 2-D dp approach as its more intuitive and easier to adapt to. Once you get the states and their relation of this one, the 3-D dp should become clearer.

Consider the interval [i,j]. In the implementation, you will see, only the intervals which can be completely filled are used in calculating answers (intervals which cannot be completely filled contribute nothing to answer). Hence, the first thing you must keep in mind is, that the interval [i,j] is such that, given current preferences of seats, it is guaranteed to be completely filled.

We make a 2-D dp table dp[n][n], where dp[a][b] stores the number of assignments for interval [a,b]. The base case is, if a>b then answer is 1 . Meaning, dp[a][b]=1 where a > b.

Let p be the last person who will be able to get a seat in interval [i,j] before its completely filled up.

Now, we will follow this algorithm-

  1. Find lastPerson. lastPerson is the last person to get a seat in interval [i,j] before all the seats in the interval get occupied.
  2. Now, for each seat from [i,j], check if the lastPerson can be seated on the current seat, say k.
  3. If lastPerson can be seated on seat k, then- Number of direction assignments in interval [i,j] += Number of direction assignments in interval [i,k-1] \times Number of direction assignments in interval [k+1,j]. If k is the preferred seat, then its occupied irrespective of direction given to lastPerson, so we multiply answer by 2 for this case. Meaning, if k is preferred seat, then, Number of direction assignments in interval [i,j] += Number of direction assignments in interval [i,k-1] \times Number of direction assignments in interval [k+1,j] \times2
  4. Update conditions and values which check if lastPerson can be seated on next seat.

The only thing left is now, how to find if lastPerson can be seated on seat k? Recall from question that-

"This means that on the ith person’s turn, he/she first checks seats S_i if it is available. If it’s available, then he/she sits there, otherwise he walks into the direction specified by D_i and sits on the first seat available in that direction. "

We will say, lastPerson can occupy the seat k in at least 1 direction assignment, if its not occupied before his turn (how to assign directions so that its lastPerson can occupy it can be referred from above algorithm, step 3).

Now, a seat will be left unoccupied if and only if-

  1. Its not the preferred seat of any person coming before lastPerson.
  2. We arent faced with a situation where seat k must be occupied due to Pigeonhole principle (a+1 people to be seated on a seats \implies at least 1 will occupy seat right outside the interval, which will be seat k), or in other words, each person coming before lastPerson is seated at a seat which is not k.

You can refer to Editorialist’s solution to see how it is realized.

SOLUTION:

In case anythings not clear from editorial, do refer to the solutions, which are commented and follow descriptive variable naming for greater clarity. Kamil’s 3-D approach which solved the question in mere 40 lines is also given for interested ones to look :).

Editorialist’s (C++)
Kamil’s (C++)

CHEF VIJJU’S CORNER :smiley:

1.3-D dp questions are a bit infrequent in normal contests. Hence, whenever they come, the contestant is perplexed for a while on what to apply. The constraints for such problems are too low to think of solution in terms of O({N}^{2}) (or problem isnt at all in terms of such solutions) etc. and too high to think in terms for O({2}^{N}) by techniques like meet-in-the-middle. From now on, you guys should know- if the constraints of N are \le100, then 3-D dp might be what you are looking for!

2.Some nice problems I came across are listed below-
a.Chef And Fibonacci Array
b.Coloring Trees