Statistics

Problem Statement for "CosmicBlocks"

Problem Statement

Josh and Sophie are playing with their new toy. This toy is called Cosmic Blocks. The toy consists of a number of blocks. Each block has the shape of a unit cube. The blocks come in N different colors. The colors are conveniently numbered 0 through N-1. There may be a different number of blocks of different colors.

Sophie likes to build structures. She always takes all the blocks and builds a structure according to the following steps: She places the blocks one at a time, in any order she likes. When placing a block, she may either put it on the floor, or directly on top of a single previously placed block. Hence the final structure can be viewed as a collection of towers, each consisting of one or more blocks placed atop each other. Note that Sophie's structure always contains all the available blocks.

Additionally, Sophie follows one more rule: She always places the blocks in such a way that for each color, all blocks of that color share the same height. Josh likes to take Sophie's structure apart. He also does that in steps. In each step, Josh removes all blocks of a particular color. However, he may only remove a block if no other block is currently placed on top of it.

Given one of Sophie's structures, a permutation of colors is called valid if it represents an order in which Josh can remove the blocks. Sometimes, some permutations of colors are not valid. For example, if Sophie placed a block of color 3 on top of a block of color 0, the permutations where 0 occurs before 3 are not valid.

Sophie and Josh now play the following game: First, Sophie builds a structure according to her rules. Next, Josh counts how many permutations of colors are valid for the structure she built.

Two structures built by Sophie are called fundamentally different if there are colors i and j such that in one structure there is at least one block of color i placed directly on top of a block of color j, and in the other structure there is no such pair of blocks.

You are given a int[] blockTypes, where the i-th element is the number of blocks of color i Josh and Sophie have. You are also given ints minWays and maxWays. Sophie wants to build a structure such that the result computed by Josh will be between minWays and maxWays, inclusive. Compute and return the number of fundamentally different structures she may build.

Definition

Class:
CosmicBlocks
Method:
getNumOrders
Parameters:
int[], int, int
Returns:
int
Method signature:
int getNumOrders(int[] blockTypes, int minWays, int maxWays)
(be sure your method is public)

Notes

  • Please read the definition of fundamentally different structures carefully. There may be pairs of structures that look different to you, but are not fundamentally different according to our definition.

Constraints

  • blockTypes will contain between 1 and 6 elements, inclusive.
  • Each element of blockTypes will be between 1 and 7,500, inclusive.
  • minWays will be between 1 and 720, inclusive.
  • maxWays will be between minWays and 720, inclusive.

Examples

  1. {2,2,2}

    1

    1

    Returns: 6

    Sophie wants to build a structure such that there is only one valid permutation of colors. To do so, she must put different colors into different heights. Each permutation of the colors produces a different structure, so there are 3! = 6 such structures.

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

    720

    720

    Returns: 1

    There is only one way to place the blocks such that they can be removed in any order.

  3. {2,2}

    1

    2

    Returns: 3

    Sophie has three ways how to build her structure: Place all the blocks on the floor. Place each block of color 0 on top of one block of color 1. Place each block of color 1 on top of one block of color 0.

  4. {1,2}

    1

    2

    Returns: 2

    In this case there is only one block of color 0 and two blocks of color 1, so it is impossible to put blocks of color 1 on top of blocks of color 0.

  5. {1}

    1

    1

    Returns: 1

  6. {1,2,4,8}

    5

    30

    Returns: 27

  7. {1,2,4,8,16,32}

    1

    720

    Returns: 4348

  8. {1500,1500,1500,1500,1500,7500}

    1

    720

    Returns: 11963

  9. {7500,7500,7500,7500,7500,7500}

    1

    720

    Returns: 14202

  10. {7500,3750,1875,937,468,200}

    1

    720

    Returns: 8110

  11. {1,2,1,2,3,9}

    1

    720

    Returns: 3180

  12. {1,1,8,8,27,27}

    1

    720

    Returns: 3198

  13. {2, 5132, 5981}

    624

    641

    Returns: 0

  14. {372, 2784, 790}

    138

    467

    Returns: 0

  15. {5472, 4987, 3903, 5033, 5762, 6908}

    282

    710

    Returns: 15

  16. {30,30,60,120,240,480}

    1

    720

    Returns: 8499

  17. {30,30,60,120,240,480}

    360

    360

    Returns: 16

  18. {30,30,60,120,240,480}

    180

    180

    Returns: 112

  19. {30,30,60,120,240,480}

    45

    45

    Returns: 54

  20. {653}

    1

    403

    Returns: 1

  21. {6049}

    1

    410

    Returns: 1

  22. {3594}

    1

    146

    Returns: 1

  23. {2768}

    1

    632

    Returns: 1

  24. {1190}

    1

    304

    Returns: 1

  25. {4400}

    1

    406

    Returns: 1

  26. {3840, 4758}

    1

    199

    Returns: 2

  27. {5563, 2440}

    1

    96

    Returns: 2

  28. {4179, 6315}

    1

    553

    Returns: 2

  29. {2684, 4685}

    1

    605

    Returns: 2

  30. {2847, 4315}

    1

    706

    Returns: 2

  31. {1791, 4451}

    1

    81

    Returns: 2

  32. {6558, 4968, 4052}

    1

    378

    Returns: 8

  33. {889, 2759, 5658}

    1

    69

    Returns: 8

  34. {64, 6978, 6970}

    1

    56

    Returns: 8

  35. {6211, 4589, 401}

    1

    661

    Returns: 8

  36. {2186, 4938, 758}

    1

    393

    Returns: 8

  37. {2448, 6574, 7103}

    1

    337

    Returns: 8

  38. {6010, 2692, 2469, 59}

    1

    110

    Returns: 52

  39. {1203, 3691, 4140, 2890}

    1

    39

    Returns: 49

  40. {4570, 442, 4421, 1796}

    1

    150

    Returns: 49

  41. {3132, 6982, 152, 4390}

    1

    328

    Returns: 50

  42. {535, 131, 5069, 3947}

    1

    71

    Returns: 52

  43. {3346, 6404, 4982, 2542}

    1

    249

    Returns: 49

  44. {7363, 1429, 6780, 3180, 2675}

    1

    402

    Returns: 498

  45. {2765, 2674, 2225, 7025, 6118}

    1

    688

    Returns: 501

  46. {6124, 5410, 2565, 4659, 1611}

    1

    508

    Returns: 501

  47. {1692, 6684, 3177, 1009, 1313}

    1

    484

    Returns: 538

  48. {4925, 1900, 3561, 7444, 1724}

    1

    147

    Returns: 516

  49. {2836, 5221, 3228, 2841, 6049}

    1

    376

    Returns: 520

  50. {7186, 2891, 1984, 3400, 5837, 6100}

    1

    646

    Returns: 7865

  51. {397, 1378, 6648, 5841, 5335, 3708}

    1

    660

    Returns: 7637

  52. {6451, 3210, 704, 1393, 3470, 5670}

    1

    318

    Returns: 7522

  53. {3908, 6514, 149, 2131, 2703, 2476}

    1

    558

    Returns: 7871

  54. {4134, 4114, 5897, 5591, 2230, 3414}

    1

    482

    Returns: 8135

  55. {1224, 4826, 1923, 3428, 3711, 6468}

    1

    279

    Returns: 7819

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

    1

    720

    Returns: 4445

  57. {7500,1000,7500,1000,7500}

    8

    88

    Returns: 448

  58. {7500,1000,7500,1000,7500,1000}

    1

    720

    Returns: 9242

  59. {300,400,699,1098,999,7500}

    1

    720

    Returns: 8585

  60. {8,88,888,888,88,8}

    1

    30

    Returns: 3227

  61. {9,18,26,35,44,53}

    1

    720

    Returns: 8146

  62. {7500, 7499, 7498, 7497, 7496, 7495 }

    1

    720

    Returns: 8195

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: