can somebody post an easy tutorial/editorial for the snackdown elimination round 2k17 problem:plusmul I found the editorials tough to understand. asked 23 Jun '17, 22:59

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.
This equation is not entirely correct because the last term we have multiplied the element a[i + 1] to dp[i]. For example:
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
But we only need these 8 combinations
So subtracting this from the above one, we will get the extra terms like
which we have to subtract if u rearrange this u can get this:
all terms multiplied with 8 at end. and then u can say that
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
hence the one line dp equation will be now,
That's it. Here u can see my solution based on this approach : link. And sorry for bad English. :) answered 24 Jun '17, 00:09
how did u get extra terms?
(24 Jun '17, 01:16)
I have updated it. Hope this helps.
(24 Jun '17, 03:20)
yup thanks a lot..
(24 Jun '17, 11:25)

This is what I did: 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. answered 24 Jun '17, 06:26
