TopCoder Statistics - Problem Statement

Problem Statement

A codeset is a set of n binary strings (the codes) that could be used to encode messages based on an alphabet of size n. In order to be able to decode the result, a codeset must have the property that no code is a prefix of any other code. A codeset is "maximal" if it is not possible to add any additional code to the codeset without violating the prefix requirement.

We are interested in how many different codesets of size n exist. For example, when n=4 there are 5 different maximal codesets:


         {"000","001","01","1"}, {"010","011","00","1"}, {"111","110","10","0"},
         {"101","100","11","0"}, {"00","11","01","10"}

Oh yes, we have a favorite code and we are only interested in codesets that include that code. You are given n, the size of each codeset, and a binary String favorite. Return the number of maximal codesets of size n that contain favorite. If there are more than 1,000,000,000, return -1 instead.

Definition

Class:: CodeSet
Method:: numSets
Parameters:: int, String
Returns:: int
Method signature:: int numSets(int n, String favorite)
(be sure your method is public)

Constraints

n will be between 2 and 20, inclusive.
favorite will contain between 1 and 20 characters, inclusive.
Each character in favorite will be '0' or '1' (zero or one).

Examples

4

"01"

Returns: 2

This is the example shown above. Only the first and last codeset listed contain "01".
4

"0110"

Returns: 0

None of the possible codesets contains "0110".
2

"0"

Returns: 1

The only maximal codeset of size 2 is {0,1}.
20

"011001"

Returns: 65132550
15

"100001"

Returns: 87210
19

"1111111"

Returns: 8351070
5

"111"

Returns: 3
17

"110100100001"

Returns: 2907
20

"110101111001010010"

Returns: 18
20

"011101000001"

Returns: 303600
14

"0110000010001"

Returns: 1
3

"0111100000111101"

Returns: 0
20

"000110000010100111"

Returns: 18
4

"01011000011000"

Returns: 0
10

"010011101001110"

Returns: 0
6

"010011011100101"

Returns: 0
3

"10011111100000111110"

Returns: 0
15

"110000100"

Returns: 5508
14

"01111110"

Returns: 3808
16

"001100100110"

Returns: 544
5

"0001101110"

Returns: 0
14

"0010011100000100011"

Returns: 0
20

"11"

Returns: 477638700
18

"01101"

Returns: 8947575
6

"1100110100110000111"

Returns: 0
20

"100111101000010000"

Returns: 18
3

"010010111"

Returns: 0
18

"1010100001001100"

Returns: 16
20

"1101100010101110111"

Returns: 1
13

"000011001110"

Returns: 1
12

"101101"

Returns: 1638
16

"00110010"

Returns: 62016
12

"010111000000"

Returns: 0
16

"1000101111"

Returns: 7752
8

"01001010"

Returns: 0
13

"010111101111001"

Returns: 0
15

"11010000"

Returns: 15504
6

"1"

Returns: 14
4

"11000110000011"

Returns: 0
7

"101100001000001001"

Returns: 0
17

"010010101100010"

Returns: 15
3

"101"

Returns: 0
2

"0011100010"

Returns: 0

Statistics

Problem Statement for "CodeSet"

Problem Statement

Definition

Constraints

Examples