This Forum is in read only mode now.

You are not logged in. Please login at www.codechef.com to post your questions!

×

PROC18D - Editorial

2
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.

View Content

TIME COMPLEXITY

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

EDITORIALIST'S SOLUTION:

Editorialist's solution can be found here.

asked 20 Aug '18, 18:44

vjvjain0's gravatar image

4★vjvjain0
91211
accept rate: 6%

edited 18 Apr, 03:55


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

link

answered 20 Aug '18, 19:40

hemant_dhanuka's gravatar image

5★hemant_dhanuka
533112
accept rate: 3%

1

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

expected is 128 but your code output is 78

(20 Aug '18, 19:58) vjvjain04★

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

(20 Aug '18, 21:38) hemant_dhanuka5★
1

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

(21 Aug '18, 01:12) joffan5★

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.

link

answered 20 Aug '18, 23:59

joffan's gravatar image

5★joffan
9488
accept rate: 13%

edited 21 Aug '18, 02:33

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,877
×2,222
×1,025
×9

question asked: 20 Aug '18, 18:44

question was seen: 1,766 times

last updated: 18 Apr, 03:55