Statistics

Problem Statement for "Seatfriends"

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.

Definition

Class:
Seatfriends
Method:
countseatnumb
Parameters:
int, int, int
Returns:
int
Method signature:
int countseatnumb(int N, int K, int G)
(be sure your method is public)

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

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

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

  3. 2

    2

    1

    Returns: 2

  4. 5

    4

    2

    Returns: 120

  5. 42

    23

    7

    Returns: 917668006

  6. 2

    1

    1

    Returns: 2

  7. 2

    2

    2

    Returns: 2

  8. 3

    1

    1

    Returns: 3

  9. 3

    2

    2

    Returns: 6

  10. 3

    3

    1

    Returns: 6

  11. 3

    3

    2

    Returns: 6

  12. 3

    3

    3

    Returns: 6

  13. 4

    1

    1

    Returns: 4

  14. 4

    2

    2

    Returns: 12

  15. 4

    3

    1

    Returns: 16

  16. 4

    3

    3

    Returns: 24

  17. 4

    4

    1

    Returns: 16

  18. 4

    4

    2

    Returns: 24

  19. 4

    4

    3

    Returns: 24

  20. 4

    4

    4

    Returns: 24

  21. 5

    1

    1

    Returns: 5

  22. 5

    2

    1

    Returns: 10

  23. 5

    2

    2

    Returns: 20

  24. 5

    3

    1

    Returns: 20

  25. 5

    3

    2

    Returns: 60

  26. 5

    3

    3

    Returns: 60

  27. 5

    4

    1

    Returns: 40

  28. 5

    4

    2

    Returns: 120

  29. 5

    4

    3

    Returns: 120

  30. 5

    4

    4

    Returns: 120

  31. 5

    5

    1

    Returns: 40

  32. 5

    5

    2

    Returns: 120

  33. 5

    5

    3

    Returns: 120

  34. 5

    5

    4

    Returns: 120

  35. 5

    5

    5

    Returns: 120

  36. 1825

    1

    1

    Returns: 1825

  37. 1473

    2

    1

    Returns: 2946

  38. 372

    2

    2

    Returns: 138012

  39. 1550

    3

    1

    Returns: 6200

  40. 1995

    3

    2

    Returns: 23844240

  41. 30

    3

    3

    Returns: 24360

  42. 1809

    4

    1

    Returns: 14472

  43. 249

    4

    2

    Returns: 1828656

  44. 1274

    4

    3

    Returns: 658030320

  45. 1121

    4

    4

    Returns: 708240850

  46. 825

    5

    1

    Returns: 13200

  47. 1300

    5

    2

    Returns: 242377200

  48. 1039

    5

    3

    Returns: 881988599

  49. 598

    5

    4

    Returns: 28613662

  50. 125

    5

    5

    Returns: 143752804

  51. 89

    6

    1

    Returns: 2848

  52. 716

    6

    2

    Returns: 347589360

  53. 1559

    6

    3

    Returns: 624084216

  54. 160

    6

    4

    Returns: 831518873

  55. 675

    6

    5

    Returns: 605020990

  56. 894

    6

    6

    Returns: 65110581

  57. 481

    7

    1

    Returns: 30784

  58. 1744

    7

    2

    Returns: 813515841

  59. 1933

    7

    3

    Returns: 916411627

  60. 960

    7

    4

    Returns: 70602307

  61. 1043

    7

    5

    Returns: 411440578

  62. 1058

    7

    6

    Returns: 67194312

  63. 1419

    7

    7

    Returns: 948463110

  64. 1294

    387

    1

    Returns: 517423343

  65. 1133

    122

    2

    Returns: 619657076

  66. 1283

    820

    3

    Returns: 920671482

  67. 1836

    128

    5

    Returns: 778608950

  68. 140

    93

    6

    Returns: 82260974

  69. 1105

    851

    7

    Returns: 699885106

  70. 1200

    1122

    295

    Returns: 116399779

  71. 220

    24

    24

    Returns: 746435413

  72. 1040

    787

    286

    Returns: 63613102

  73. 143

    82

    73

    Returns: 862271504

  74. 1754

    289

    222

    Returns: 342370244

  75. 1987

    1545

    989

    Returns: 701439290

  76. 29

    2

    1

    Returns: 58

  77. 1196

    948

    643

    Returns: 809112049

  78. 1738

    565

    160

    Returns: 678877322

  79. 1139

    133

    109

    Returns: 288863401

  80. 1971

    510

    375

    Returns: 340811356

  81. 1304

    997

    925

    Returns: 774981568

  82. 1690

    1321

    565

    Returns: 583950290

  83. 1976

    1723

    118

    Returns: 956589962

  84. 1940

    1811

    1658

    Returns: 15564497

  85. 1082

    838

    760

    Returns: 557122456

  86. 1557

    931

    31

    Returns: 425829267

  87. 1924

    506

    179

    Returns: 877583060

  88. 1500

    1

    1

    Returns: 1500

  89. 1500

    2

    1

    Returns: 3000

  90. 1500

    2

    2

    Returns: 2248500

  91. 1500

    1500

    1

    Returns: 876072731

  92. 1500

    1500

    1500

    Returns: 367552188

  93. 1995

    1

    1

    Returns: 1995

  94. 1995

    2

    1

    Returns: 3990

  95. 1995

    2

    2

    Returns: 3978030

  96. 1995

    1500

    1

    Returns: 550353452

  97. 1995

    1500

    2

    Returns: 722163478

  98. 1995

    1500

    1500

    Returns: 201274744

  99. 1995

    1995

    1

    Returns: 646022887

  100. 1995

    1995

    2

    Returns: 276589060

  101. 1995

    1995

    1500

    Returns: 442383389

  102. 1995

    1995

    1995

    Returns: 442383389

  103. 1999

    1

    1

    Returns: 1999

  104. 1999

    2

    1

    Returns: 3998

  105. 1999

    1500

    1

    Returns: 45692503

  106. 1999

    1500

    2

    Returns: 984021408

  107. 1999

    1500

    1500

    Returns: 163147227

  108. 1999

    1995

    1

    Returns: 588871926

  109. 1999

    1995

    2

    Returns: 351570218

  110. 1999

    1995

    1500

    Returns: 462522926

  111. 1999

    1995

    1995

    Returns: 462522926

  112. 1999

    1999

    2

    Returns: 487901650

  113. 1999

    1999

    1500

    Returns: 100550147

  114. 1999

    1999

    1995

    Returns: 100550147

  115. 1999

    1999

    1999

    Returns: 100550147

  116. 2000

    1

    1

    Returns: 2000

  117. 2000

    2

    1

    Returns: 4000

  118. 2000

    2

    2

    Returns: 3998000

  119. 2000

    1500

    1

    Returns: 669527271

  120. 2000

    1500

    1500

    Returns: 652588908

  121. 2000

    1995

    1

    Returns: 413078464

  122. 2000

    1995

    2

    Returns: 882660179

  123. 2000

    1995

    1500

    Returns: 9169105

  124. 2000

    1995

    1995

    Returns: 9169105

  125. 2000

    1999

    1

    Returns: 609255382

  126. 2000

    1999

    2

    Returns: 745105257

  127. 2000

    1999

    1500

    Returns: 100292593

  128. 2000

    1999

    1995

    Returns: 100292593

  129. 2000

    1999

    1999

    Returns: 100292593

  130. 2000

    2000

    1

    Returns: 609255382

  131. 2000

    2000

    2

    Returns: 745105257

  132. 2000

    2000

    1500

    Returns: 100292593

  133. 2000

    2000

    1995

    Returns: 100292593

  134. 2000

    2000

    1999

    Returns: 100292593

  135. 2000

    2000

    2000

    Returns: 100292593

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: