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.
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) print smallest-result
NOTE: You should use 64-bit integers for this problem, because the minimum value can be upto - 910 < -231, which is out of range of 32 bit integers.
The next question is, how much time it would take ?
There are 3N-1 ways of assigning the operators. Therefore, complexity of trying out all combinations is for all test cases O(T * 3N-1). For subtasks 1 and 2, these numbers are roughly 2 * 105 and 3 * 105 respectively, and these should be easily solvable. Therefore, 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 * 108, and would possibly need more optimizations/better algorithms.
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 * 107, so it can be solved with our current observation.
It remains to see how to solve the subtask 4, 5 in given time limit. Let the operations applied be op1, op2 … opN-1, so the final expression becomes A1 〈op1〉 A2 〈op2〉 A3 … AN-1 〈opN-1〉 AN.
Lets develop a shorthand by denoting evali = A1 〈op1〉 A2 〈op2〉 A3 … Ai-1 〈opi-1〉 Ai, i.e. evaluation over first i numbers.
For each possibility of opN-1, lets figure out what can we say about evalN-1.
- If opN-1 = ‘+’. then it obviously makes best sense to choose the first N-2 operators so that evalN-1 is minimum.
- If opN-1 = ‘-’, then it again makes sense to choose the first N-2 operators so that evalN-1 is minimum.
- If opN-1 = ’ * ', then there are two cases:
i) AN ≥ 0 then we should choose the first N-2 operators so that evalN-1 is minimum.
ii) AN ≤ 0 then we should choose the first N-2 operators so that evalN-1 is maximum, because we will flip its sign during last operation.
Therefore, we only need to know the maximum and minimum possible values of evalN-1 to evaluate minimum possible of evalN. Similarly, if we want to maximize the value of evalN, we would again need to find only the maximum and minimum possible values of evalN-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 eval2 as ‘-1’, ‘3’ or ‘-2’. Now, to evaluate the smallest/largest possible value of eval3, only the values ‘-2’, and ‘3’ are relevant.
The smallest candidate value of eval3 can be obtained by one of the possibilities -2+4, -2-4, -2x4. The minimum being -8. Similarly, the largest possible values of eval3 can be one out of 3+4, 3-4, 3x4, best one being 12. Now in order to evaluate eval4, we only need to use eval3 = -8 and 12. Using same ideas candidates for smallest value of eval4 are only -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 = A worst-eval = A for i = 2 to N if A[i] > 0 best-eval[i] = max(best-eval[i-1]+A[i], best-eval[i-1]-A[i], best-eval[i-1] * A[i]) worst-eval[i] = min(worst-eval[i-1]+A[i], worst-eval[i-1]-A[i], worst-eval[i-1] * A[i]) else best-eval[i] = max(best-eval[i-1]+A[i], best-eval[i-1]-A[i], worst-eval[i-1] * A[i]) worst-eval[i] = min(worst-eval[i-1]+A[i], worst-eval[i-1]-A[i], best-eval[i-1] * A[i]) print worst-eval[N]
For A[i] > 0, best-eval[i]+A[i] > best-eval[i]-A[i], so we can apply some more optimizations based on these ideas, but they are not essential.
The time complexity is O(N) per test case, so it can pass all subtasks.