Problem Link:Author Roman Furko Difficulty:Simple Prerequisites: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 1We 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: The next question is, how much time it would take ? There are 3^{N1} ways of assigning the operators. Therefore, complexity of trying out all combinations is for all test cases O(T * 3^{N1}). For subtasks 1 and 2, these numbers are roughly 2 * 10^{5} and 3 * 10^{5} 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 * 10^{8}, 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
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 ^{N1}) possibilities. The number of steps needed for subtask # 3 would be 5 * 10^{7}, 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 op_{1}, op_{2} ... op_{N1}, so the final expression becomes A_{1} ⟨op_{1}⟩ A_{2} ⟨op_{2}⟩ A_{3} ... A_{N1} ⟨op_{N1}⟩ A_{N}. Lets develop a shorthand by denoting eval_{i} = A_{1} ⟨op_{1}⟩ A_{2} ⟨op_{2}⟩ A_{3} ... A_{i1} ⟨op_{i1}⟩ A_{i}, i.e. evaluation over first i numbers. For each possibility of op_{N1}, lets figure out what can we say about eval_{N1}. Therefore, we only need to know the maximum and minimum possible values of eval_{N1} to evaluate minimum possible of eval_{N}. Similarly, if we want to maximize the value of eval_{N}, we would again need to find only the maximum and minimum possible values of eval_{N1}. To see why this really helps, consider a small test case as follows: 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_{3}, only the values '2', and '3' are relevant. The smallest candidate value of eval_{3} can be obtained by one of the possibilities 2+4, 24, 2x4. The minimum being 8. Similarly, the largest possible values of eval_{3} can be one out of 3+4, 34, 3x4, best one being 12. Now in order to evaluate eval_{4}, we only need to use eval_{3} = 8 and 12. Using same ideas candidates for smallest value of eval_{4} 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 For A[i] > 0, besteval[i]+A[i] > besteval[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. Solutions:
This question is marked "community wiki".
asked 29 Sep '13, 14:48

Why score of the contestants are still zero even in practice section. answered 29 Sep '13, 15:18

Why isn't my code working ?? Can someone check please http://www.codechef.com/viewsolution/3447798 answered 20 Feb '14, 22:17

Can anyone tell me why some of my answers are wrong? Here is my code : http://www.codechef.com/viewsolution/3629457 answered 22 Mar '14, 20:25
