CosmicBlocks
SRM 549 · 2012-06-05 · by tehqin
Problem Statement
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
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.
{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.
{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.
{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.
{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.
{1}
1
1
Returns: 1
Submissions are judged against all 62 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CosmicBlocks with a public method int getNumOrders(vector<int> blockTypes, int minWays, int maxWays) · 62 test cases · 2 s / 256 MB per case