can somebody post an easy tutorial/editorial for the snackdown elimination round 2k17 problem:plusmul
I found the editorials tough to understand.
I havn’t read the previous editorial, but i will try to explain my approach i think it’s an easy approach.
So let’s start, we have n elements in an array.
Now, let dp[i] be the required result as asked in the question for first i (just like for n) elements of the array.
Now we will add the next element ( a[i+1] ), and will see how the result will be affacted, so we have to calculate dp[i + 1].
Before this it should be clear that there will be 2 ^ (i - 1) total combinations taking i elements all together because we will have two options ( * and +) for each (i - 1) places.
That means dp[i] is the summation of all these 2 ^ (i - 1) combinations.
Now let’s calculate dp[i + 1],
we now included the next element a[i + 1] and for this either we can add ( ‘+’ ) or multiply ( ‘*’ ) as per rules given in question.
dp[i + 1] = dp[i] + a[i + 1] * (2 ^ (i - 1)) + dp[i] * a[i + 1]
This equation is not entirely correct because the last term we have multiplied the element a[i + 1] to dp[i].
For example:
lets the current elements of array be 2, 3, 5, 8, 9.
All 2 ^ 3 = 8 combinations from dp[4] (taking first 4 elements 2, 3, 5, 8) are given as :
2 + 3 + 5 + 8
2 + 3 + 5 * 8
2 + 3 * 5 + 8
2 + 3 * 5 * 8
2 * 3 + 5 + 8
2 * 3 + 5 * 8
2 * 3 * 5 + 8
2 * 3 * 5 * 8
So basically, dp[i] is the sum of all these values.
Now if we multiply a[i + 1] ie 9 to dp[i] then we will get summation of all these terms
(2 + 3 + 5 + 8) * 9
(2 + 3 + 5 * 8) * 9
(2 + 3 * 5 + 8) * 9
(2 + 3 * 5 * 8) * 9
(2 * 3 + 5 + 8) * 9
(2 * 3 + 5 * 8) * 9
(2 * 3 * 5 + 8) * 9
(2 * 3 * 5 * 8) * 9
But we only need these 8 combinations
2 + 3 + 5 + 8 * 9
2 + 3 + 5 * 8 * 9
2 + 3 * 5 + 8 * 9
2 + 3 * 5 * 8 * 9
2 * 3 + 5 + 8 * 9
2 * 3 + 5 * 8 * 9
2 * 3 * 5 + 8 * 9
2 * 3 * 5 * 8 * 9
So subtracting this from the above one, we will get the extra terms like
(2 + 3 + 5) * 8
(2 + 3) * 8
(2 + 3 * 5) * 8
(2) * 8
(2 * 3 + 5) * 8
(2 * 3) * 8
(2 * 3 * 5) * 8
which we have to subtract if u rearrange this u can get this:
2
2 + 3
2 * 3
2 + 3 + 5
2 + 3 * 5
2 * 3 + 5
2 * 3 * 5
all terms multiplied with 8 at end.
and then u can say that
- the first term is dp[1].
- the summation of 2nd and 3rd term is dp[2].
- the summation of last 4 terms is dp[3].
hence the overall summation is dp[1] + dp[2] + dp[3] multiplied with 8 (that is 9 - 1) at end.
So, we have to subtract the term sum_dp[3] * (9 - 1) where sum_dp[3] = dp[1] + dp[2] + dp[3].
In general we have to subtract the term sum_dp[i - 1] * (a[i + 1] - 1) that’s it.
where
sum_dp[i] = dp[1] + dp[2] + dp[3] + ... + dp[i].
hence the one line dp equation will be now,
dp[i + 1] = dp[i] + a[i + 1] * (2 ^ (i - 1)) + dp[i] * a[i + 1] - sum_dp[i - 1] * (a[i + 1] - 1)
That’s it.
Here u can see my solution based on this approach : link.
And sorry for bad English. 
4 Likes
how did u get extra terms?
I have updated it. Hope this helps.
1 Like
This is what I did:
I’ll explain with an example, n=4, arr[]={1,2,3,4}, the expressions corresponding to this example are:
1 + 2 + 3 + 4
1 + 2 + 3 * 4
1 + 2 * 3 + 4
1 + 2 * 3 * 4
1 * 2 + 3 + 4
1 * 2 + 3 * 4
1 * 2 * 3 + 4
1 * 2 * 3 * 4
We need to find the sum of all these expressions, one thing that you need to observe is that all of these expressions are made up of several multiplication terms (group of numbers with only ‘*’ in between them and ‘+’ at the beginning and the end of the group) that are added up. Eg. 3 * 4 appears in the 2nd and the 6th expression among the ones I mentioned above. Now, if we are able to count how many times each term appears in the expression, we can multiply the value of each term with the number of times it appears, and then summing this up for all possible terms will give us the answer. Notice that every possible term is a continuous sequence of numbers in the input array. So, there will be N*(N+1)/2 terms. This can be done in O(N^3) or O(N^2), and both these ways are not effecient.
But the idea itself can be used with a slight modification. First of all, lets see how to count the number of times some term appears in the expressions. I’ll explain this with an example:
Suppose that our input is {1,2,3,4,5,6}, and we need to count the number of times the term 2 * 3 appears. The expressions where 2 * 3 appears as a separate term will be of this form: 1 + 2 * 3 + 4 _ 5 _ 6 ( ‘_’ means that the position can be filled with any symbol). So, the number of times this term appears will be the number of ways in which all the positions with ‘_’ can be filled. In this case, its 2^2 because there are 2 positions and each position has 2 choices. The number of such positions for each term can be easily calculated. If the term is made up of ‘k’ numbers, then there will be (N-k-2) positions.
This is because there will be N-1 positions for symbols in an expression with N numbers. Since our term has ‘k’ numbers in it, the k-1 symbols between them will be fixed to * and two more symbols, the one before and after the term will be fixed to +. So the remaining positions will be = N-1 - (k-1+2) = N-k-2. Now, as I mentioned, calculating this for every term will be really slow, so we need to do something better.
Observe that the terms ending at position ‘i’ are obtained by multiplying the terms ending at position ‘i-1’ by the number at position ‘i’. I will explain this with an example :
N=5 Arr={1,2,3,4,5}, consider the terms ending at position 3 (1-based indexing) the terms will be:
3
3 * 2
3 * 2 * 1
Now, take a look at the terms ending at position 4:
4
4 * (3)
4 * (3 * 2)
4 * (3 * 2 * 1)
Observe that, except the first term, all the others are obtained by multiplying the terms at the previous position with 4. Lets also take a look at the counts of the number of times each of these terms appears:
Terms ending at position 3:
3 : 2^2
3 * 2 : 2^1
3 * 2 * 1 : 2^1 (Terms containing the first/last number will have N-K-1 symbols to fix because there is no symbol before/after those terms)
Similarly, terms ending at position 4:
4 : 2^2
4 * (3) : 2^1
4 * (3 * 2) : 2^0
4 * (3 * 2 * 1) : 2^0
Observe that every term ending at position 4 (except the first) is obtained by multiplying 4 to some term ending at position 3, and its count is same as the count of that term divided by 2. This is always true because the only difference between the terms ending at positions 3 and 4 is that an additional symbol is fixed to ‘*’.
Now, if we define ans[i] to be the sum of all the terms ending at position ‘i’, then ans[i] will be given by multiplying the previous answer with the number at this position, and then dividing by 2. You will have to consider the term containing the single number ending at this position separately because it does not depend on the terms ending at the previous position.
So, ans[i] = (ans[i-1]*arr[i])/2 + arr[i]*(2^(N-3)) (Becomes 2^(N-2) if i=1 or i=N)
The final answer will be sum of ans[i] for i from 1 to N.
4 Likes
yup thanks a lot…