CHGIFT1 - Editorial

Problem Link:

Practice
Contest

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 - 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, op2opN-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[1] = A[1]
worst-eval[1] = A[1]
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.

Solutions:

Setter’s Solution
Tester’s Solution
Editorialist’s Solution

12 Likes

Why score of the contestants are still zero even in practice section.

can someone tell me whats wrong with my code it is just getting 30 points…

here is the link…

http://ideone.com/xnGCOr

Your program fails in the following test case

5

1 2 0 3 4 -5

Your output : -16

Correct output: -180

my answer is correct…it is showing -180 …

your input should rather be “6” instead of “5” as you are inputting 6 numbers…

Oops!!! My bad.

The problem lies in your minx and maxx function you are returning int instead of int64.

2 Likes

thnx bro…

lost 70 points just coz of it…;(…feels terrible.

can someone tell me whats wrong with my code i got all sample test cases passed
here is my link to the code

http://pastebin.com/GSyE6ZB6

You didn’t test your code properly, for sample test it prints -49

I took a look on your last submission and actually I’m not able to find counter example, but why you use in calc this:

    if(b==1)
            return ar[b-1];
    else if(ch=='+')
            return calc(ar,'*',b-1)+ar[b-1];
    else if(ch=='*')
            return calc(ar,'*',b-1)*ar[b-1];
    else if(ch=='-')
            return calc(ar,'-',b-1)-ar[b-1];

it seems incorrect to me…

here it is…

1
3
1 3 9

correct answer is -18, your code returns -11

Why isn’t my code working ?? Can someone check please
http://www.codechef.com/viewsolution/3447798

Can anyone tell me why some of my answers are wrong? Here is my code : http://www.codechef.com/viewsolution/3629457