Statistics

Problem Statement for "TheBoardingDivOne"

Problem Statement

John and Brus are going to board a plane.

The boarding can be described using the following simplified model. There are 2 * n cells numbered from 1 to 2 * n from left to right. There are n seats in the plane numbered from 1 to n. The seat i is located near cell n + i. There are n passengers numbered from 1 to n. Initially they stand in some order in cells 1, 2, ..., n. The order can be described using a permutation p[1], p[2], ..., p[n] of integers from 1 to n, where p[i] is the number of the passenger who initially stands in cell i. It is known that passenger i wants to take seat i during boarding.

The boarding process can be divided into primitive steps, each of which takes exactly 1 second. During each step, we can check all passengers from right to left and determine for each passenger what he/she will do according to the following rules:
  • Denote the number of the passenger we're currently checking as X and the current cell of this passenger as Y.
  • If Y < n + X and cell Y + 1 is currently empty, the passenger will move to this cell. It takes him exactly one step to complete this move, so at the beginning of the next step he/she will be in cell Y + 1.
  • If Y < n + X, cell Y + 1 contains a passenger and the passenger at cell Y + 1 will perform a move during the current step, the passenger at cell Y will also move to the next cell during the current step (exactly as described in the previous rule).
  • If Y < n + X, cell Y + 1 contains a passenger and the passenger at cell Y + 1 will not move during the current step, the passenger at cell Y will skip the current step (so he/she will still be in cell Y in the beginning of the next step).
  • If Y = n + X, it means that the passenger in cell Y has reached the cell near which his seat is located. Therefore he will take a seat and it takes 74 steps to do it. So cell Y will be occupied during steps S, S+1, ..., S+73 (where S is the number of the current step) because the passenger at this cell will be taking his/her seat. In the beginning of step S+74 this cell will become empty because the passenger has completed taking the seat.

The boarding time is defined as the number of steps performed until each passenger has taken his/her seat. Obviously, the boarding time can depend on the initial order of passengers. For example, if p[1] = 1, p[2] = 2, the boarding time is 76 (during the first two steps both passengers reach the cells with their seats, and during the next 74 steps they simultaneously take their seats). And if p[1] = 2, p[1] = 1, the boarding time is 151 (after one step passenger 1 will reach the cell with his/her seat, during the next 74 steps he/she will take his/her seat and passenger 2 will wait until it's finished, and then passenger 2 will need 76 more steps to reach the required cell and take a seat).

You are given a int[] pattern that imposes some restrictions on the initial order of passengers (described by permutation p). This int[] contains exactly n elements. If pattern[i] (1-based) is an integer between 1 and n, inclusive, it means that p[i] must be equal to pattern[i], and if pattern[i] is -1, it means that p[i] can be an arbitrary integer between 1 and n, inclusive.

The initial order of passengers is considered to be good if the boarding time for this order is not greater than boardingTime. Return the number of good initial orders of passengers that match the given pattern.

Definition

Class:
TheBoardingDivOne
Method:
find
Parameters:
int[], int
Returns:
long
Method signature:
long find(int[] pattern, int boardingTime)
(be sure your method is public)

Constraints

  • pattern will contain between 2 and 18 elements, inclusive.
  • Each element of pattern will be either -1 or between 1 and n, inclusive, where n is the number of elements in pattern.
  • For each X between 1 and n, inclusive, there will be at most one occurrence of X in pattern.
  • boardingTime will be between 2 and 222, inclusive.

Examples

  1. {-1, -1}

    100

    Returns: 1

    Here we have two possible permutations. In case of (1, 2) the boarding takes 76 seconds and in case of (2, 1) it takes 151 seconds.

  2. {-1, 2, -1}

    222

    Returns: 1

    The only one good order is (1, 2, 3).

  3. {2, 1, 3, 5, 4, 6}

    155

    Returns: 1

    Only one order matches pattern and the boarding for it takes exactly 155 seconds.

  4. {-1, -1, -1, -1, -1, -1, -1}

    198

    Returns: 233

  5. {-1, -1}

    110

    Returns: 1

  6. {-1, -1, -1, -1, -1, -1}

    52

    Returns: 0

  7. {-1, -1, -1, -1}

    98

    Returns: 1

  8. {-1, -1, -1, -1, -1, -1, -1, -1}

    157

    Returns: 92

  9. {-1, -1, -1, -1, -1, -1}

    158

    Returns: 88

  10. {-1, -1}

    151

    Returns: 2

  11. {-1, -1, -1, -1, -1}

    156

    Returns: 33

  12. {-1, -1, -1, -1, -1, -1, -1}

    155

    Returns: 1

  13. {-1, -1}

    151

    Returns: 2

  14. {-1, -1, -1, -1}

    155

    Returns: 13

  15. {-1, -1, -1, -1, -1, -1, -1}

    158

    Returns: 199

  16. {-1, -1, -1, -1, -1, -1}

    157

    Returns: 82

  17. {-1, -1, -1, -1}

    154

    Returns: 12

  18. {-1, -1, -1, -1, -1}

    157

    Returns: 34

  19. {-1, -1, -1, -1, -1}

    153

    Returns: 1

  20. {-1, -1, -1}

    151

    Returns: 1

  21. {-1, 5, 2, 4, 3, -1}

    159

    Returns: 0

  22. {4, -1, -1, 3}

    155

    Returns: 1

  23. {-1, -1, 4, 2}

    155

    Returns: 1

  24. {-1, 4, -1, 1, -1, -1, 5}

    160

    Returns: 3

  25. {-1, 2, 3, 4, 5, -1}

    159

    Returns: 1

  26. {1, -1, -1, -1}

    155

    Returns: 5

  27. {1, -1, -1, -1, 5, -1, -1, 8}

    160

    Returns: 10

  28. {-1, 2, -1, -1, -1, -1}

    155

    Returns: 8

  29. {1, -1, -1, 4, 5, -1}

    159

    Returns: 2

  30. {-1, -1, 3, -1, 5, -1}

    158

    Returns: 2

  31. {-1, -1, -1, -1, 8, 2, -1, -1}

    157

    Returns: 0

  32. {-1, -1, 5, -1, -1, 1, 8, -1}

    160

    Returns: 2

  33. {-1, -1, -1, -1, -1, -1, -1, -1}

    157

    Returns: 92

  34. {-1, -1, -1, -1, 8, -1, -1, -1}

    156

    Returns: 0

  35. {-1, -1, -1, -1, -1, -1, 3, -1}

    160

    Returns: 25

  36. {1, 2, 3, 4, 5, 6, 7, 8}

    222

    Returns: 1

  37. {1, 2, 3, 4, 5, 6, 7, 8}

    82

    Returns: 1

  38. {5, 3, 6, 4, 8, 2, 1, 7}

    222

    Returns: 0

  39. {1, 2, 3, 4, 5, 6, 7, 8}

    81

    Returns: 0

  40. {-1, 2, 3, 4, 5, -1, -1, 8}

    157

    Returns: 2

  41. {-1, -1, 3, -1, -1, 6, 7, 8}

    162

    Returns: 4

  42. {-1, 2, -1, 4, -1, 6, 7, -1}

    163

    Returns: 1

  43. {1, 2, -1, -1, 5, 6, -1, -1}

    161

    Returns: 4

  44. {-1, -1, 3, -1, -1, 6, -1, 8}

    159

    Returns: 4

  45. {-1, -1, 3, -1, 5, 6, -1, -1}

    156

    Returns: 1

  46. {1, 2, -1, 4, 5, -1, -1, -1}

    160

    Returns: 5

  47. {-1, -1, -1, -1, -1, -1, -1, -1}

    222

    Returns: 610

  48. {-1, -1, -1}

    22

    Returns: 0

  49. {-1, -1}

    2

    Returns: 0

  50. {-1, -1, -1, -1, -1}

    67

    Returns: 0

  51. {-1, -1, -1}

    150

    Returns: 1

  52. {-1, -1}

    170

    Returns: 2

  53. {-1, -1, -1, -1, -1}

    195

    Returns: 34

  54. {-1, -1}

    194

    Returns: 2

  55. {-1, -1, -1, -1, -1, -1, -1, -1, -1}

    172

    Returns: 1597

  56. {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    150

    Returns: 1

  57. {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    156

    Returns: 1

  58. {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    182

    Returns: 196418

  59. {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    189

    Returns: 1346269

  60. {-1, -1, -1, -1, -1, -1, -1, -1, -1}

    193

    Returns: 1597

  61. {-1, 2, 3, 4, 5, -1, -1, 8, -1, 10, 11, 12, -1, -1}

    165

    Returns: 4

  62. {1, 2, -1, -1, -1, 6, -1, -1, 9, -1, 11, -1, 13, 14, -1}

    166

    Returns: 10

  63. {1, 2, -1, -1, 5, 6, -1, -1, 9, 10, -1, 12, -1}

    165

    Returns: 4

  64. {1, -1, 3, -1, -1, -1, 7, -1, -1, -1, 11, -1, 13, 14, -1, -1}

    175

    Returns: 44

  65. {1, 2, -1, 4, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, 15}

    172

    Returns: 1597

  66. {-1, -1, -1, -1, -1, -1, 11, -1, -1, -1, -1, 12, -1, -1}

    165

    Returns: 0

  67. {-1, -1, -1, -1, -1, -1, -1, 3, -1, 1, -1, -1, -1, -1, -1, -1, -1}

    179

    Returns: 0

  68. {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, -1, -1, -1}

    174

    Returns: 5408

  69. {-1, -1, -1, -1, -1, -1, -1, 9, -1, -1, 6, -1, -1}

    162

    Returns: 2

  70. {-1, -1, -1, -1, -1, -1, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    181

    Returns: 223276

  71. {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    222

    Returns: 9227465

  72. {-1, -1, -1, -1, -1, -1, 12, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    222

    Returns: 776212

  73. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}

    222

    Returns: 1

  74. {1, 17, 15, 2, 14, 4, 12, 8, 6, 11, 13, 16, 18, 3, 9, 10, 5, 7}

    222

    Returns: 0

  75. {-1,-1,6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    178

    Returns: 1704292

  76. {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    176

    Returns: 9142502

  77. {1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    222

    Returns: 3524578

  78. {1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    172

    Returns: 2788771

  79. {2,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    222

    Returns: 3524578

  80. {2,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    174

    Returns: 3348734

  81. {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,17}

    222

    Returns: 3524578

  82. {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,17}

    176

    Returns: 3494986

  83. {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,18}

    222

    Returns: 3524578

  84. {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,18}

    171

    Returns: 2232858

  85. {-1,3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    222

    Returns: 3190383

  86. {-1,3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    172

    Returns: 2626405

  87. {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,16,-1}

    222

    Returns: 2692538

  88. {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,16,-1}

    177

    Returns: 2684199

  89. {-1,-1,5,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    222

    Returns: 2268649

  90. {-1,-1,5,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    173

    Returns: 2100968

  91. {-1,4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    222

    Returns: 2236950

  92. {-1,4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    170

    Returns: 879452

  93. {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,18,-1}

    222

    Returns: 2178310

  94. {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,18,-1}

    177

    Returns: 2176490

  95. {-1,-1,4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    222

    Returns: 2090981

  96. {-1,-1,4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    172

    Returns: 1805853

  97. {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,15,-1,-1}

    222

    Returns: 2056916

  98. {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,15,-1,-1}

    173

    Returns: 1875500

  99. {-1,-1,-1,6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    222

    Returns: 1802355

  100. {-1,-1,-1,6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    178

    Returns: 1802344

  101. {-1,-1,-1,7,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    222

    Returns: 1731056

  102. {-1,-1,-1,7,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    172

    Returns: 1444292

  103. {-1,-1,6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    222

    Returns: 1704444

  104. {-1,-1,6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    170

    Returns: 609331

  105. {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,14,-1,-1,-1}

    222

    Returns: 1571344

  106. {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,14,-1,-1,-1}

    177

    Returns: 1566096

  107. {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,14,-1,-1}

    222

    Returns: 1571344

  108. {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,14,-1,-1}

    177

    Returns: 1561376

  109. {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,15,-1}

    222

    Returns: 1542687

  110. {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,15,-1}

    179

    Returns: 1542265

  111. {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,13,-1,-1,-1}

    222

    Returns: 1500500

  112. {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,13,-1,-1,-1}

    175

    Returns: 1436379

  113. {-1,-1,-1,-1,8,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    222

    Returns: 1461152

  114. {-1,-1,-1,-1,8,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    175

    Returns: 1457578

  115. {-1, -1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 18, -1, -1 }

    222

    Returns: 36864

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: