Brackets on a calculator
The screen of an old calculator shows an expression of one-digit numbers and the signs +, − and ×. There are no brackets, and the calculator computes as it should: 7 − 3 × 2 − 4 × 5 = −19. You may place brackets however you like; the order of the numbers and signs does not change, and minus still only subtracts. What is the largest value you can get?
For this expression the answer is 65: (7 − 3 × (2 − 4)) × 5. Look at the middle: for the result to be largest, the piece 3 × (2 − 4) has to be as small as possible.
Input
One line without spaces: digits from 0 to 9, with one sign +, - or * between neighbouring digits. From 1 to 15 digits.
Output
One integer: the largest value of the expression with some placement of brackets.
Examples
Example 1
7-3*2-4*5
65
Example 2
1-9*9-9
1
Limits
- Time · Python
- 2000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 13 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The last operation, under some placement of brackets, divides the expression into a left and a right piece, each computed with its own brackets. Which pieces come up, and how many are there in all?
2Hint 2
To get the largest A − B, the right piece B must be as small as possible. And the product of two very negative numbers is very positive. What should be kept for each piece, then?
3The idea
For each piece of digits from i to j keep two numbers: the smallest and the largest value it can take under some placement of brackets. The last operation divides the piece at some sign k, and its result is a op b, where a is the value of the left part and b of the right. For +, − and × the extremum of a op b is always reached when a and b are themselves extreme, so it is enough to try four combinations, “smallest or largest on the left and on the right”.
4Walkthrough
Why four combinations are enough: with the sign fixed, the expression a + b, a − b or a · b is monotone in each argument with the other fixed, addition and subtraction always, multiplication depending on the sign of the other factor. So the largest and smallest values are reached at the ends of the ranges [lo, hi] of both parts.
Compute the pieces in increasing order of length: this is interval DP. In the first example the largest value 65 = (7 − 3 × (2 − 4)) × 5 comes out like this: the piece “3 × 2 − 4” needs its minimum, −6, which is subtracted from 7 to give 13, and then multiplied by 5. A solution that keeps only maxima takes this piece’s maximum, 2, and loses.
4+Solution
5Complexity
O(n³) for n digits: O(n²) pieces, each with O(n) choices of the last operation. The numbers fit in 64 bits: in absolute value a result is at most the product of (di + 1) over all the digits, which is less than 1015.
6Common mistakes
- Only the maximum of a piece. Fails the first example: subtraction and multiplying negatives want the minimum of a part.
- Greedy brackets. “All the pluses first” or “all the multiplications first” is not always best: in the second example the answer comes from the bracket (9 − 9), which zeroes a product.
- Trying all placements. Their number is a Catalan number: for 15 digits 2,674,440 options, each with its own evaluation tree; without a table of pieces this is too slow.