Seatfriends

SRM 625 · 2013-12-22 · by subscriber

SRM 625 · 2013-12-22 · by subscriber · Dynamic Programming

Show categories

Class Name: Seatfriends

Return Type: int

Method Name: countseatnumb

Arg Types: (int, int, int)

Problem Statement

Hero is preparing a party for his friends. He has a round table with N seats. The seats are numbered 0 through N-1, in order. In other words, seats with consecutive numbers are adjacent, and seat N-1 is adjacent to seat 0.

Hero knows that exactly K friends will attend the party, and that each of them will arrive at a different time. Each time a new friend arrives, Hero has to assign him (or her) one of the empty seats at the table. The friend then sits there for the rest of the party. Hero is not sitting at the table.

For the purpose of this problem, a cluster is a maximal group of people that occupy consecutive chairs. For example, if there are people on chairs 3, 4, 5, and 6, while chairs 2 and 7 are empty, then these four people form a cluster.

At a party, clusters are good: people who sit in a cluster can talk to each other and have fun. A party with too many clusters is bad. Therefore, Hero wants to make sure that at no point in time are there more than G clusters at his table.

For example, let N = 4 and K = 3. That is, we have a table with four seats, and three friends are going to arrive. We will use A, B, and C to denote the three friends (in the order in which they arrive) and a period ('.') to denote an empty chair. So, for example, "ABC." denotes that A got seat 0, B seat 1, C seat 2, and seat 3 remained empty. The configurations ".ABC" and "C.AB" are considered different from "ABC." and from each other: the friends sit in the same order but on different seats.

Continuing our example, let G = 1. That is, we must never have more than one cluster. This constraint restricts the set of possible final configurations. For example, "ABC.", "C.AB", "B.CA", and ".BAC" are all possible, but "A.BC" and ".ACB" are not. (Note that if the final configuration were "A.BC", then the configuration before C arrived was "A.B.", which means that there was more than one cluster at that point in time.)

You are given the ints N, K, and G. Count the number of possible final configurations. Return that count modulo 1,000,000,007.

Constraints

N will be between 2 and 2000, inclusive.
K will be between 1 and N, inclusive.
G will be between 1 and K, inclusive.

Examples

3
2
1
Returns: 6

There are 6 ways how to seat your 2 friends: "AB.", "A.B", "BA.", "B.A", ".AB", and ".BA". All 6 are valid.

4
2
1
Returns: 8

The first friend can take any of the four seats. The second one must then sit next to him (on either side). Thus, there are 4*2=8 valid final configurations.

2
2
1
Returns: 2

5
4
2
Returns: 120

42
23
7
Returns: 917668006

Submissions are judged against all 135 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Seatfriends with a public method int countseatnumb(int N, int K, int G) · 135 test cases · 2 s / 256 MB per case