PROC18D - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Editorialist: Vaibhav Jain

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Greedy, DP

PROBLEM:

You are given an expression of n numbers and n-1 operators$(+ or -)$ and you need to maximize expression’s value by adding valid parenthesis.

QUICK EXPLANATION:

When we encounter '+' sign our maximum value will be maximum of left and right expressions and when we encounter '-' sign our maximum value will be maximum of left expression and minimum of right expression and vice-versa for minimum values.

EXPLANATION:

The basic intuition for this solution is based on the thing that whenever we get '-' sign the left expression should be maximum as possible and right expression should be minimum as possible. And when we get '+' sign both expressions should be maximum as possible.

To do above thing we need to memoize. For this we will maintain two 2-D DP matrices as dpMax and dpMin. While dpMax will store the maximum and dpMin will store the minimum in the range. [i][j] will tell us that the range is from i to j.

For implementing we need to have one loop for iterating from second to last element of numbers and we will have a nested loop inside our first loop so that it can calculate all possible ranges from first index till current index of our main loop. And inside our nested loop we will have one loop which will be necessary to get the optimal value for different ranges. The latter loop will iterate over the operators to get us the optimal value.

If you are having difficulty in understanding the above part you can see hidden part for example.

Click to view

For input : 10 - 7 + 50 - 20 + 20 - 100

End range is 1
Start range is 0
[3 0 1]

End range is 2
Start range is 1
[57 1 2]
Start range is 0
[-47 0 2] [53 0 2]

End range is 3
Start range is 2
[30 2 3]
Start range is 1
[37 1 3] [37 1 3]
Start range is 0
[-27 0 3] [33 0 3] [33 0 3]

End range is 4
Start range is 3
[40 3 4]
Start range is 2
[10 2 4] [50 2 4]
Start range is 1
[57 1 4] [57 1 4] [57 1 4]
Start range is 0
[-7 0 4] [53 0 4] [53 0 4] [53 0 4]

End range is 5
Start range is 4
[-80 4 5]
Start range is 3
[-60 3 5] [-60 3 5]
Start range is 2
[110 2 5] [110 2 5] [110 2 5]
Start range is 1
[117 1 5] [117 1 5] [117 1 5] [117 1 5]
Start range is 0
[93 0 5] [113 0 5] [113 0 5] [113 0 5] [113 0 5]

Ans 113

TIME COMPLEXITY

The time complexity will be O(n^{3}).

EDITORIALIST’S SOLUTION:

Editorialist’s solution can be found here.

2 Likes
2

Bro, can u help me to figure out any test case where mycode is failing… i am using top down dp approach similar to urs

my solution link in java

1 Like
3

1
6
10 - 7 + 25 - 20 + 30 - 100

expected is 128 but your code output is 78

1 Like
4

thanks for replying, can u apply bracket over that to get sum 128

5

I spent too long analyzing this during the timed competition (resulting in no score). But the essence of my analysis was this:

  • An expression e with no minus sign has only one value, the sum of its terms s(e).
  • An expression e with only one minus sign has a clear maximum value, \max(e) = s(e) - 2k_1 where k_1 is the term following the minus sign (the factor 2 is just there to switch from +k_1 to -k_1)
  • An expression with two or more minus signs has a maximum value \max(e) which is one of the two following values:
    • s(e) - 2s(k_m), where k_m are the terms between the two minus signs
    • if there are two or more terms between the minus signs, s(1:k_1-1) - k_1+ \max(k_1+1:n), breaking at the first intervening plus sign.

This is because two successive minus signs allow the brackets to be placed so as to add all terms succeeding the second minus sign. So in the first of those two cases we force successive minus signs by amalgamating all the intervening terms. In the second case we take the smallest initial negative hit and maximize the rest.

My solution

With a little more work this could probably be coded up as O$(n)$, maintaining a couple of least subtraction options in a single traversal of the terms.

1 Like
6

10 - ((7+25) - (20+30) - 100) = 10 - (32 - 150 ) = 10 - (-118) = 128

1 Like