CODEWITHSUNDEEP
algorithmlanguage-agnostic
Naman
Naman

Reputation: 2669

Maximize evaluation of expression with one parenthesis insertion

I encountered this problem in a programming contest:

Given expression x1 op x2 op x3 op . . . op xn, where op is either addition '+' or multiplication '*' and xi are digits between 1 to 9. The goal is to insert just one set of parenthesis within the expression such that it maximizes the result of the expression.
The n is maximum 2500.

Eg.: Input: 3+5*7+8*4

Output: 303

Explanation: 3+5*(7+8)*4

There was another constraint given in the problem that at max only 15 '*' sign will be present. This simplified the problem. As we will have just 17 options of brackets insertion and brute force would work in O(17*n).

I have been thinking if this constraint was not present, then can I theoretically solve the problem in O(n^2)? It seemed to me a DP problem. I am saying theoretically because the answers will be quite big (9^2500 possible). So if I ignore the time complexity of working with big numbers then is O(n^2) possible?

Upvotes: 2

Views: 186

Answers (1)

Ralph M. Rickenbach
Ralph M. Rickenbach

Reputation: 13203

If there is no multiplication, you are finished.

If there is no addition, you are finished.

The leading and trailing operation of subterms that have to be evaluated always are additions, because parenthesis around a multiplication does not alter the outcome.

If you have subterms with only additions, you do not need to evaluate subparts of them. Multiplication of the full subterm will always be bigger. (Since we only have positiv numbers/digits.)

Travers the term once, trying to place the opening parenthesis after (worst case) each * that is succeeded with a +, and within that loop a second time, trying to place the closing parenthesis before (worst case) each succeeding * that immediately follows an +.

You can solve the problem in O(ma/2), with m: number of multiplications and a: number of additions. This is smaller than n^2.

Possible places for parenthesis shown with ^:

1*2*^3+4+5^*6*^7+8^

Upvotes: 1

Related Questions