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

×

CHGIFT1 - Editorial

16
3

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, 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[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

This question is marked "community wiki".

asked 29 Sep '13, 14:48

admin's gravatar image

0★admin ♦♦
18.4k348492529
accept rate: 36%

edited 30 Sep '13, 00:04

Debanjan's gravatar image

2★Debanjan
34659


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

link

answered 29 Sep '13, 15:18

sobhagya's gravatar image

3★sobhagya
2.7k132747
accept rate: 12%

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

here is the link..

http://ideone.com/xnGCOr

link

answered 29 Sep '13, 15:21

subway's gravatar image

5★subway
1396811
accept rate: 0%

Your program fails in the following test case

5

1 2 0 3 4 -5

Your output : -16

Correct output: -180

(29 Sep '13, 15:47) sobhagya3★

my answer is correct..it is showing -180 ..

your input should rather be "6" instead of "5" as you are inputting 6 numbers..

(29 Sep '13, 16:56) subway5★
2

Oops!!! My bad.

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

(29 Sep '13, 17:49) sobhagya3★

thnx bro..

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

(29 Sep '13, 19:48) subway5★

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

link

answered 30 Sep '13, 16:01

sanjeevmsk's gravatar image

1★sanjeevmsk
1
accept rate: 0%

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

http://ideone.com/edYUjX

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

(30 Sep '13, 16:04) betlista ♦♦3★

here it is...

1
3
1 3 9

correct answer is -18, your code returns -11

(30 Sep '13, 16:41) betlista ♦♦3★

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

link

answered 20 Feb '14, 22:17

surf666's gravatar image

2★surf666
112
accept rate: 0%

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

link

answered 22 Mar '14, 20:25

amitab_57th's gravatar image

0★amitab_57th
1
accept rate: 0%

toggle preview
Preview

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:

×13,920
×3,035
×1,612
×9
×6

question asked: 29 Sep '13, 14:48

question was seen: 3,866 times

last updated: 22 Mar '14, 20:25