TopCoder problem "RussianDolls" used in TCCC '04 Wildcard (Division I Level Two)

Problem Statement


Note to plugin users: there are html elements in this statement that will not appear correct in plugins. Please use the statement to view them.

Russian Nesting Dolls are a set of dolls which nest inside each other. The dolls are constructed in such a way that each doll will fit comfortably inside any larger doll, and no two dolls are the same size. There are a finite number of ways to nest dolls inside one another so that a specific subset of the dolls is visible. For example, with 3 dolls, there is only one way that they could be nested such that only the largest doll is visible, but there are 2 ways to nest the dolls if the largest and medium doll are visible (depending on which of the two larger dolls the smallest doll is inside). In addition, if you are just given how many dolls are visible, there may be even more ways that the dolls could be nested. For example, if you know there are 2 dolls visible in a 3-doll set, there are 3 ways they could be nested (see example 0).

Your clever friend has used an entire set of N nesting dolls in an arrangement on a table. He assures you that all the nesting dolls are on the table, but you can only see a subset of the dolls. In addition, he has placed a piece of cardboard in front of some of the dolls so that you cannot see which ones they are, and he tells you how many are behind the board. He asks you how many possible ways he could have arranged the dolls such that the current configuration is on the table.

Each doll has a number painted on it from 1 to N, which identifies the size of the doll. You can fit a doll labeled i inside a doll labeled j as long as i < j. Your program will be given an int N, identifying how many dolls there are in the set, a int[] visible, identifying which dolls you can see on the table, and an int hidden, identifying how many more dolls would be visible if the board was removed. Two arrangements are different if any doll is nested immediately inside a different doll, or is nested in one arrangement but not in the other.



Parameters:int, int[], int
Method signature:long arrangements(int N, int[] visible, int hidden)
(be sure your method is public)


-The constraints are constructed so the return value will be <= 263 - 1.


-N will be between 2 and 25, inclusive.
-hidden will be between 0 and N, inclusive.
-visible will have between 0 and N-hidden elements, inclusive.
-Each element of visible will be between 1 and N, inclusive.
-There will be no repeated elements in visible.
-There will be at least one configuration which is possible given the arguments.


Returns: 3
There are three dolls, two of which are behind the board. Since no dolls are showing, the third doll must be nested inside one of the other two. There are three possibilities:

1 and 3 are behind the board, 2 is nested inside 3

2 and 3 are behind the board, 1 is nested inside 2

2 and 3 are behind the board, 1 is nested inside 3
Returns: 2
In this case, doll 2 is showing. Since there is only one doll behind the board, it must be doll 3. The only unknown is doll 1. It could either be nested in doll 3 or doll 2.
Returns: 255
Dolls 1-8 could either be behind the board or inside doll 9. However, the case where 1-8 are all inside of 9 is not possible, because then there wouldn't be a doll behind the board. So the answer is 28 - 1.
Returns: 7163268480

Problem url:

Problem stats url:




lbackstrom , brett1479 , vorthys

Problem categories:

Advanced Math