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
Definition
- Class:
- RussianDolls
- Method:
- arrangements
- Parameters:
- int, int[], int
- Returns:
- long
- Method signature:
- long arrangements(int N, int[] visible, int hidden)
- (be sure your method is public)
Notes
- The constraints are constructed so the return value will be <= 263 - 1.
Constraints
- 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.
Examples
3
{}
2
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
3
{2}
1
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.
9
{9}
1
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.
20
{13,5,2,18}
3
Returns: 7163268480
25
{}
10
Returns: 1203163392175387500
largest return value
25
{1,3,5,7,9,11,13,15,17,19,21,23,25}
0
Returns: 479001600
2
{}
1
Returns: 1
2
{1}
1
Returns: 1
3
{3}
1
Returns: 3
15
{1,2,3,4,5,15}
0
Returns: 1
25
{}
25
Returns: 1
18
{15, 5, 1, 12}
5
Returns: 1310429376
11
{7}
4
Returns: 114276
5
{4, 2, 5}
1
Returns: 6
15
{10, 11}
4
Returns: 82173532
16
{5, 1, 13, 8, 16, 7}
6
Returns: 264460
4
{3}
2
Returns: 5
4
{}
1
Returns: 1
20
{10, 4, 7, 20, 11}
7
Returns: 13761566497
20
{9, 1, 18, 17}
8
Returns: 41240097360
12
{10, 12, 7, 4}
1
Returns: 33696
9
{9, 2}
1
Returns: 190
4
{4}
2
Returns: 6
4
{4, 3}
1
Returns: 5
20
{4, 11, 6, 1, 18, 17, 12, 9}
4
Returns: 347127552
11
{3, 11, 9}
4
Returns: 22296
14
{5, 14, 8}
4
Returns: 6320313
16
{11}
6
Returns: 1677387492
14
{10, 6, 14, 5, 12}
2
Returns: 1319961
4
{2}
2
Returns: 4
17
{17, 5, 4}
7
Returns: 366169320
21
{3, 6, 2, 18}
6
Returns: 231189168240
14
{3, 14, 2, 7}
1
Returns: 8608
13
{5, 11}
4
Returns: 1801776
25
{25, 13, 21, 4, 1}
6
Returns: 2543803089685632
4
{}
2
Returns: 7
25
{23, 18, 17, 24, 13, 11, 4, 3}
7
Returns: 25823856106170
2
{}
1
Returns: 1
15
{8, 1}
3
Returns: 1446368
15
{5, 15, 7, 13, 6}
3
Returns: 5156992
17
{1, 5, 17}
7
Returns: 285222663
17
{13, 12, 3, 1, 6, 14}
6
Returns: 2589772
10
{4, 8, 6}
3
Returns: 3672
25
{13, 3, 18, 15, 24, 10, 25, 1, 12}
3
Returns: 9888018742656
6
{3}
3
Returns: 38
2
{2}
0
Returns: 1
20
{20, 13, 9, 6, 3}
7
Returns: 13076248600
7
{6, 5, 7}
1
Returns: 175
8
{8, 7}
2
Returns: 1351
25
{6, 23, 14, 22, 11, 4}
8
Returns: 286724475758655
7
{5, 3, 6}
2
Returns: 52
18
{6, 14, 17, 10, 9}
8
Returns: 25998136
15
{14, 9, 2}
5
Returns: 22529832
10
{1, 10}
0
Returns: 1
17
{13}
7
Returns: 13066956188
21
{14, 19, 9}
5
Returns: 7962030735264
12
{1, 8, 3}
2
Returns: 2544
8
{8, 3}
2
Returns: 506
11
{5}
6
Returns: 35092
17
{17, 9, 10, 12}
4
Returns: 1524545144
12
{12, 10, 5}
2
Returns: 199176
25
{ }
12
Returns: 362262620784874680