TopCoder Statistics - Problem Statement

Problem Statement

You've invented a new programming language called Brainstuck. A Brainstuck program consists of a sequence of characters. The allowed characters are +, -, [, and ]. There is a single memory cell. This cell can hold a single integer of arbitrary size. Initially the cellâs value is 0. The Brainstuck interpreter processes each character in sequence using an instruction pointer. At the beginning of the execution of the program, the instruction pointer points to the first character of the program. After processing a character, the instruction pointer moves forward by one character. Each character corresponds to a command:

+ increases the value of the memory cell by 1.
- decreases the value of the memory cell by 1.
[ looks at the value of the memory cell. If it is zero, the instruction pointer moves to the matching ] command.
] looks at the value of the memory cell. If it is non-zero, the instruction pointer moves to the matching [ command.

The [ which matches a ] is decided according to the usual way of matching nested brackets. See the Notes for a formal definition. The program terminates when the instruction pointer moves past the last character.

A Brainstuck program is valid if and only if:

There are no unmatched [ or ] characters.
The execution of the program terminates after a finite number of steps.

Please count the number of valid Brainstuck programs that consist of exactly N characters and return this value modulo M.

Definition

Class:: Brainstuck
Method:: countPrograms
Parameters:: int, int
Returns:: int
Method signature:: int countPrograms(int N, int M)
(be sure your method is public)

Notes

The ] character which matches a [ character at index i in the string s is at the smallest index j such that j > i and s[i..j] contains an equal number of [ and ] characters.

Constraints

N will be between 1 and 100, inclusive.
M will be between 2 and 1,000,000,000, inclusive.

Examples

2

1000000000

Returns: 5

The valid programs are ++, -+, +-, --, []. Note that the execution of the program "[]" consists only of a single step: The instruction pointer points to the [ and the value of the memory cell is zero, so during the execution of this command the interpreter moves the instruction pointer to the matching ]. Then, after the command is executed, the interpreter increments the instruction pointer, which moves it past the last character of the program.
3

1000000000

Returns: 12

The valid programs are: +++ -++ +-+ --+ []+ ++- -+- +-- --- []- [+] [-]
5

1000000000

Returns: 92
16

1000000000

Returns: 55450070
13

163

Returns: 64
100

1000000000

Returns: 875563034
84

10007

Returns: 7588
74

424343

Returns: 130490
100

2

Returns: 0
100

49398543

Returns: 148084
1

2

Returns: 0
1

10

Returns: 2
2

5

Returns: 0
100

536870911

Returns: 117890459
99

536870911

Returns: 126659993
42

123123

Returns: 19512
96

29104293

Returns: 2103158
99

999999999

Returns: 209382398

Statistics

Problem Statement for "Brainstuck"

Problem Statement

Definition

Notes

Constraints

Examples