MaxMinExpression | Topcoder Archive

Problem Statement

Fox Ciel has an expression that consists of some variables and some binary operators. The variables are represented by the first K lowercase letters. The only allowed operators are min and max. You are given a String[] expr. Concatenate all elements of expr to get the expression.

Formally, a valid expression is one of the following (quotes for clarity):

The string "X" where X is one of the first K lowercase letters.
The string "max(Y,Z)" where Y and Z are valid expressions.
The string "min(Y,Z)" where Y and Z are valid expressions.

Also, it is guaranteed that the expression contains each of the first K lowercase letters at least once.

For Ciel wants to assign integers between 1 and M, inclusive, to the variables. She is allowed to assign the same value to multiple variables. You are given the int K, the String[] expr, the int M, and an int target. Fox Ciel wants to assign the values to variables in such a way that the result of her expression will be equal to target. Return the number of ways in which she can do so, modulo 1,000,000,007.

Definition

Class:: MaxMinExpression
Method:: countAssignments
Parameters:: int, String[], int, int
Returns:: int
Method signature:: int countAssignments(int K, String[] expr, int M, int target)
(be sure your method is public)

Constraints

expr will contain between 1 and 14 elements, inclusive.
Each element of expr will contain between 1 and 50 characters, inclusive.
The concatenation of all elements of expr will satisfy the constraints in the statement.
The concatenation of all elements of expr will contain at most 694 characters.
K will be between 1 and 16, inclusive.
M will be between 1 and 1,000,000,000, inclusive.
target will be between 1 and M, inclusive.

Examples

```
1
```
```
{"a"}
```
```
10000
```
```
2012
```
```
Returns: 1
```
Ciel must assign 2012 to "a".
```
2
```
```
{"max(a,b)"}
```
```
1000000000
```
```
2012
```
```
Returns: 4023
```
There are 4023 ways to assign integers: ("a", "b") = (1, 2012), (2, 2012), ..., (2012, 2012), (2012, 1), (2012, 2), ..., (2012, 2011).
```
1
```
```
{"max(a,min(a,a))"}
```
```
20
```
```
12
```
```
Returns: 1
```
```
3
```
```
{"max(a,min(b,c))"}
```
```
20
```
```
12
```
```
Returns: 523
```

{"min(max(max(a,min(b,a)", "),min(f,d)),max(min(c,e),c))"}

1000000000

47584758

Returns: 886337049

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.