# Problem Link:

**Author** Roman Furko

**Tester** Balajiganpathi

**Editorialist** Utkarsh Lath

# Difficulty:

Simple

# Pre-requisites:

Dynamic Programming

# Problem:

Given a list of **N** integers, each **between -9 and 9**, you have to put one of the operators **‘+’, ‘-’, ‘*’** between consecutive elements of the list, so the resulting number is mimimum. The result is obtained by evaluating operators from left to right.

# Explanation:

## Subtask 1

We have no idea which operators should be filled in each of the blanks to get minimum result, so we can try all possible combinations. This can be done via recursion:

smallest-result = 10^18;

void calc( i, res-so-far) // first i-1 operators have been chosen, chose the remaining

if i ≥ N

smallest-result = min (smallest-result, res-so-far)

else

calc(i+1, res-so-far + A[i+1]) // the ith operator can be one out of ‘+’, ‘-’, ‘*’

calc(i+1, res-so-far - A[i+1])

calc(i+1, res-so-far * A[i+1])

calc(1, A[1])

print smallest-result

**NOTE:** You should use 64-bit integers for this problem, because the minimum value can be upto **- 9 ^{10} < -2^{31}**, which is out of range of 32 bit integers.

The next question is, how much time it would take ?

There are **3 ^{N-1}** ways of assigning the operators. Therefore, complexity of trying out all combinations is for all test cases

**O(T * 3**. For subtasks 1 and 2, these numbers are roughly

^{N-1})**2 * 10**and

^{5}**3 * 10**respectively, and these should be easily solvable. Therefore,

^{5}**subtasks 1 and 2**can be done by brute force. For other subtasks, the number of operations needed in worst case would be more than

**4 * 10**, and would possibly need more optimizations/better algorithms.

^{8}Now lets consider the subtask 3. In this subtask, there is a restriction on numbers, that they are all positive. Can we do anything better in this case ? This brings us back to the question

Can we really place all the operators (+, -, * ) at all the positions ?

Initially, when all numbers could be positive or negative, we could construct examples where all three operators (-, +, * ) are used. But in case of positive numbers, one can quickly realize that only ’ * ’ or ‘-’ will be used. This is because intuitively, ‘+’ will always increase the value, and any ‘+’ can be replaced by a ‘-’ to construct a strictly smaller value. Therefore, we will only need to check over all combinations of ‘-’ and ’ * ', thus giving rise to **O(2 ^{N-1})** possibilities. The number of steps needed for subtask # 3 would be

**5 * 10**, so it can be solved with our current observation.

^{7}It remains to see how to solve the subtask 4, 5 in given time limit. Let the operations applied be **op _{1}**,

**op**…

_{2}**op**, so the final expression becomes

_{N-1}**A**.

_{1}〈op_{1}〉 A_{2}〈op_{2}〉 A_{3}… A_{N-1}〈op_{N-1}〉 A_{N}Lets develop a shorthand by denoting **eval _{i} = A_{1} 〈op_{1}〉 A_{2} 〈op_{2}〉 A_{3} … A_{i-1} 〈op_{i-1}〉 A_{i}**, i.e. evaluation over first i numbers.

For each possibility of **op _{N-1}**, lets figure out what can we say about

**eval**.

_{N-1}- If
**op**. then it obviously makes best sense to choose the first_{N-1}= ‘+’**N-2**operators so that**eval**is minimum._{N-1} - If
**op**, then it again makes sense to choose the first_{N-1}= ‘-’**N-2**operators so that**eval**is minimum._{N-1} - If
**op**, then there are two cases:_{N-1}= ’ * '

i)**A**then we should choose the first_{N}≥ 0**N-2**operators so that**eval**is minimum._{N-1}

ii)**A**then we should choose the first_{N}≤ 0**N-2**operators so that**eval**is maximum, because we will flip its sign during last operation._{N-1}

Therefore, we only need to know the maximum and minimum possible values of **eval _{N-1}** to evaluate minimum possible of

**eval**. Similarly, if we want to maximize the value of

_{N}**eval**, we would again need to find only the maximum and minimum possible values of

_{N}**eval**.

_{N-1}To see why this really helps, consider a small test case as follows:

N = 4

A = 1 -2 4 -1

Now, we could put ‘+’ or ‘-’ or ‘*’ at the first place to obtain **eval _{2}** as ‘-1’, ‘3’ or ‘-2’. Now, to evaluate the smallest/largest possible value of

**eval**, only the values ‘-2’, and ‘3’ are relevant.

_{3}The smallest candidate value of

**eval**can be obtained by one of the possibilities

_{3}**-2+4, -2-4, -2x4**. The minimum being

**-8**. Similarly, the largest possible values of

**eval**can be one out of

_{3}**3+4, 3-4, 3x4**, best one being

**12**. Now in order to evaluate

**eval**, we only need to use

_{4}**eval**and

_{3}= -8**12**. Using same ideas candidates for smallest value of

**eval**are only

_{4}**-8 + -1, -8 - -1, 12 * -1**, which gives

**-12**as the final answer.

It is notable how a small observation has helped us eliminate so many possible assignments of operators. This approach is called *Dynamic Programming*.

We can summarize the ideas discussed above in the following code

best-eval[1] = A[1]

worst-eval[1] = A[1]

for i = 2 to N

if A* > 0

best-eval* = max(best-eval[i-1]+A*, best-eval[i-1]-A*, best-eval[i-1] * A*)

worst-eval* = min(worst-eval[i-1]+A*, worst-eval[i-1]-A*, worst-eval[i-1] * A*)

else

best-eval* = max(best-eval[i-1]+A*, best-eval[i-1]-A*, worst-eval[i-1] * A*)

worst-eval* = min(worst-eval[i-1]+A*, worst-eval[i-1]-A*, best-eval[i-1] * A*)

print worst-eval[N]

For * A > 0**,

*> best-eval*-A***, so we can apply some more optimizations based on these ideas, but they are not essential.*

*best-eval*+AThe time complexity is **O(N)** per test case, so it can pass all subtasks.