Statistics

Problem Statement for "SkewedPerspective"

Problem Statement

NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.

Cat Taro has the following building blocks: unit cubes of different colors (none of them black) and black rectangular prisms with dimensions 2x1x1. The number of cubes of each color is given as a int[] cubes. For example, if Taro has 5 red cubes, 1 yellow cube, and 2 blue cubes, then cubes={5,1,2}. The number of black prisms is given by int B.

Taro is using the blocks to build w adjacent towers of blocks (some possibly empty), as shown on the right side of the picture below. Taro will always place the rectangular prisms vertically. In other words, each prism will look like two black unit cubes placed one on top of the other. Taro is not required to use all of the blocks when building the towers. However, he must use at least one block (a cube or a prism).



Rabbit Hanako is looking at Taro's towers from the left side of the room. To him, the towers seem as a single tower, as shown on the left side of the picture above. More precisely, at each height i Hanako sees the color of the block at height i in the leftmost tower that has such a block. Hanako's view can be described as a sequence of colors, giving the colors of each 1x1 square seen by Hanako in the order from bottom to top.

Taro and Hanako now wonder how many different non-empty views can Hanako see. (Two views are different if either their heights differ, or for some height the colors seen at that height differ.) You are given the int[] cubes, the int B, and the int w. Return the number of different non-empty views modulo 1,000,000,007 (10^9 + 7).

Definition

Class:
SkewedPerspective
Method:
countThem
Parameters:
int[], int, int
Returns:
int
Method signature:
int countThem(int[] cubes, int B, int w)
(be sure your method is public)

Constraints

  • w will be between 1 and 8, inclusive.
  • cubes will contain between 0 and 50 elements, inclusive.
  • Each element of cubes will be between 1 and 50, inclusive.
  • The total sum of the elements of cubes will be between 0 and 50, inclusive.
  • B will be between 0 and 10, inclusive.

Examples

  1. {1,1}

    1

    2

    Returns: 19

    The 19 possible views are:

  2. {1}

    1

    2

    Returns: 5

  3. {1}

    3

    2

    Returns: 19

    The 19 possible views are:

  4. {}

    5

    5

    Returns: 5

    As we only have black prisms, each possible view will only contain black squares. The five possible views have heights 2, 4, 6, 8, and 10.

  5. {1}

    5

    5

    Returns: 39

  6. {7,7,7}

    0

    8

    Returns: 301226488

  7. {50}

    10

    8

    Returns: 665146241

  8. {}

    0

    8

    Returns: 0

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

    10

    8

    Returns: 199658209

  10. {9}

    2

    6

    Returns: 466

  11. {5,14,13}

    7

    3

    Returns: 781975497

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

    2

    5

    Returns: 463846336

  13. {1,1,1,1,2,1,1,1,1,1}

    0

    1

    Returns: 54745760

  14. {1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1}

    8

    3

    Returns: 714102776

  15. {6,8,6,6,11,10}

    7

    6

    Returns: 596093234

  16. {4,3,4,2,3,2,6}

    6

    3

    Returns: 961213759

  17. {}

    9

    2

    Returns: 9

  18. {1,1,5,2,1,1}

    8

    2

    Returns: 749928331

  19. {1,1,1,2,1,2,2,1,2}

    0

    6

    Returns: 85424462

  20. {1,4,4,2,2,5,3,2,4,5,9}

    10

    7

    Returns: 980637931

  21. {1,1,1,1,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2}

    6

    3

    Returns: 708257516

  22. {1,2,3,1,2,1,1,1,1,2,1,1,1,1,2,1,2}

    1

    7

    Returns: 104938810

  23. {11,9}

    7

    1

    Returns: 623714550

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

    9

    7

    Returns: 146505796

  25. {3,6,3,5,3,3,8,5,3,3}

    8

    8

    Returns: 641146404

  26. {1,1,1,2,1,1,1}

    9

    2

    Returns: 711012050

  27. {30}

    1

    7

    Returns: 766

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

    0

    4

    Returns: 28394

  29. {14,19}

    7

    5

    Returns: 343636261

  30. {9,6}

    0

    7

    Returns: 19446

  31. {7,5}

    0

    6

    Returns: 3001

  32. {15}

    3

    1

    Returns: 4843

  33. {3,5,3,4,3,2,2,4,7,1,2,2}

    8

    4

    Returns: 533545918

  34. {1}

    5

    6

    Returns: 39

  35. {1,1,1,2,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,2,1,1,1,1}

    1

    6

    Returns: 213715583

  36. {3,1,1,1,1}

    4

    5

    Returns: 1329373

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

    5

    8

    Returns: 321440342

  38. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    4

    6

    Returns: 693702988

  39. {1,2,1,1,1,1,1,2,3,2,1,1,2,1,1,1,1}

    0

    7

    Returns: 884124802

  40. {1,1,1,1,1,1,2,1,4,3,1,1,2,1,2,1,1,1,1,1,1,3,1,2,2,4,1,2,2,2,1,1}

    8

    7

    Returns: 381101131

  41. {12,7,9,4,5,4,6}

    8

    8

    Returns: 815292690

  42. {1,1,1,1,1,1,1,3,1,1,1,1,2,1,1,1,1,1,1,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,1,1,1,1,1,1}

    9

    7

    Returns: 255805890

  43. {5,4,6,4,3,6,3,8,5,5}

    10

    8

    Returns: 86736258

  44. {1,2,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1}

    8

    6

    Returns: 48780676

  45. {2,3,2,2,2,2,2,2,1,3,2,1,2,1,1,1,4,3,2,2,2,3,1,3}

    8

    6

    Returns: 613817336

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

    9

    6

    Returns: 391085551

  47. {48}

    8

    8

    Returns: 74306940

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

    9

    7

    Returns: 873288870

  49. {5,5,3,4,6,5,4,5,3,7}

    8

    6

    Returns: 893462985

  50. {1,1,1,2,1,1,2,2,1,1,1,1,2,2,1,2,1,1,1,2,1,1,2,1,1,1,1,1,2,1,2,2,1,1,2,1,2}

    8

    8

    Returns: 116041219

  51. {9,2,5,7,3,7,5,4,5}

    8

    7

    Returns: 294257410

  52. {4,4,5,5,3,1,7,4,4,2,5,3}

    8

    6

    Returns: 536269216

  53. {1,1,1,1,1,1,1,2,1,1,1,2,1,1,2,1,1,1,1,1,1,1,1,1,2,1,1,1,1,2,1,1,1,2,1,2,1,2,1,1,1,1}

    10

    7

    Returns: 635889977

  54. {1,1,2,1,1,1,1,1,1,2,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,2,1,1}

    8

    7

    Returns: 666012396

  55. {1,2,2,2,1,2,3,2,1,4,1,2,3,2,3,2,4,1,2,3,2,1,2,2}

    8

    6

    Returns: 944297422

  56. {2,2,4,6,4,6,6,4,4,3,7}

    10

    7

    Returns: 90058018

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

    10

    8

    Returns: 730997197

  58. {1,1,1,1,1,2,1,1,1,1,3,2,1,1,2,1,1,2,2,1,2,2,3,1,2,2,1,2,1,2,2}

    8

    6

    Returns: 515614360

  59. {4,3,3,5,3,2,2,3,2,5,7,4,2,3}

    10

    6

    Returns: 285724132

  60. {19,15,13}

    9

    6

    Returns: 837858978

  61. {3,1,3,1,1,2,3,1,2,3,1,2,1,1,1,2,1,1,1,2,3,2,2,1,2,1,3}

    10

    6

    Returns: 91107239

  62. {2,1,2,2,1,3,3,2,2,1,2,2,2,3,1,1,3,3,2,2,1,3,2,1,2}

    8

    6

    Returns: 153001281

  63. {3,5,3,4,5,8,3,2,4,5,7}

    9

    8

    Returns: 543039460

  64. {2,2,2,1,1,2,1,1,1,1,2,2,1,1,2,2,2,1,2,1,1,2,3,1,1,2,3,1,2,2,1,1}

    10

    7

    Returns: 660743297

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

    10

    7

    Returns: 697332112

  66. {1,1,1,1,1,1,1,2,2,1,1,1,2,2,3,2,1,2,1,1,2,1,2,3,2,2,2,2,3,2,1}

    10

    6

    Returns: 928264524

  67. {1,1,2,1,1,1,1,1,1,1,1,1,1,2,2,2,1,1,1,1,2,1,1,2,1,1,2,2,1,1,1,1,1,1,3,1,1,1}

    8

    7

    Returns: 71101185

  68. {1,2,1,1,1,1,1,2,1,2,2,1,1,2,1,1,1,3,1,1,1,1,1,1,1,1,1,1,1,3,1,1,1,1,2,1,1,1}

    8

    8

    Returns: 544298185

  69. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    8

    6

    Returns: 612335076

  70. {13,15,20}

    10

    7

    Returns: 928928653

  71. {9,12,16,12}

    10

    6

    Returns: 434969858

  72. {49}

    9

    6

    Returns: 866142378

  73. {11,12,8,11,8}

    9

    6

    Returns: 723160955

  74. {23,24}

    10

    6

    Returns: 998444265

  75. {48}

    10

    8

    Returns: 54212496

  76. {47}

    10

    8

    Returns: 295134152

  77. {14,8,15,13}

    8

    7

    Returns: 947862298

  78. {17,30}

    9

    7

    Returns: 266773690

  79. {24,23}

    8

    7

    Returns: 402659957

  80. {22,27}

    8

    7

    Returns: 340209833

  81. {19,22,7}

    9

    6

    Returns: 889690034

  82. {12,17,13,6}

    8

    8

    Returns: 887875834

  83. {48}

    8

    8

    Returns: 74306940

  84. {25,23}

    9

    8

    Returns: 223700040

  85. {21,28}

    10

    7

    Returns: 323740073

  86. {9,12,11,17}

    10

    6

    Returns: 258095153

  87. {47}

    10

    8

    Returns: 295134152

  88. {47}

    8

    8

    Returns: 600710387

  89. {20,29}

    9

    6

    Returns: 629629601

  90. {10,11,8,13,8}

    8

    6

    Returns: 8860112

  91. {18,15,14}

    8

    6

    Returns: 740007065

  92. {5,16,11,9,6}

    10

    7

    Returns: 950427230

  93. {23,25}

    9

    7

    Returns: 223696456

  94. {8,7,8,14,12}

    8

    8

    Returns: 418822026

  95. {13,10,10,8,7}

    9

    6

    Returns: 263851329

  96. {49}

    10

    8

    Returns: 949155103

  97. {47}

    9

    8

    Returns: 651924767

  98. {23,24}

    8

    8

    Returns: 402660085

  99. {15,14,18}

    8

    7

    Returns: 266834995

  100. {1}

    2

    2

    Returns: 11

  101. {1}

    1

    1

    Returns: 4

  102. {10, 8, 10, 5, 3, 3, 1, 2, 3, 4 }

    10

    8

    Returns: 627459486

  103. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    10

    8

    Returns: 199658209

  104. {2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    10

    8

    Returns: 839270363

  105. {1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 1, 2 }

    10

    8

    Returns: 7792819

  106. {4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 }

    10

    8

    Returns: 901388560

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: