I've been waiting for the editorials since a while now. Can someone please share their logic for the problem PLUSMUL in SNACKDOWN ELIMINATION round? That was the only question that I thought aboutfor 3 hours but could not figure anything out. asked 07 Jun '17, 17:47

PLUSMUL is a very nice problem to be solved using dynamic programming. I am assuming you are familiar with the concept and moving forward with the explanation. Armed with this, we can put forward a definition of $f(i)$. The current form of the equation works, but it has complexity $\mathcal{O}(n^2)$, which is too slow for this problem. We need to improve our method. Let us define two additional functions $g(i)$ and $h(i)$ which we get from our definition of $f(i)$. $$ \begin{align} g(i) &= \sum_{j=0}^{i}f(j) \\ h(i) &= 2^{i1}a_i + \sum_{j=0}^{i2}\left( 2^j × \prod_{k=j+1}^i a_k \right)+ \prod_{j=0}^i a_j \end{align} $$ Now, observe that $$ \begin{align} g(i) &= g(i1) + f(i) \\ h(i) &= h(i1)×a_i + 2^{i1}a_i \\ f(i) &= g(i1) + h(i) \end{align} $$ For the base cases, we have $f(0) = g(0) = h(0) = a_0$. Here is my code for reference. Hope this helps :) answered 07 Jun '17, 20:19
1
What an awesome explanation, why not post this as UNOFFICIAL editorial :)
(07 Jun '17, 22:10)
5
Respect #Shakti_Billi
(07 Jun '17, 22:13)
1
Thanks a lot for such a detailed explanation!
(07 Jun '17, 22:34)
Haha thanks guys :P
(08 Jun '17, 22:08)
hey @meooow ,your explaination is showing math processing error where mathematical terms are present..it would be very helpful if u could write a blog so that others can benefit..
(23 Jun '17, 13:05)
@viralivora the math is working okay for me. It is likely an issue with your network or browser. You can try doing a "hard refresh" as mentioned here.
(24 Jun '17, 02:41)
showing 5 of 6
show all

There are n1 gaps and there are two choices to fill each of them ( + or *), hence there are 2^(n1) possible combinations. Since this number can be huge, listing out and computing the value of each combination can take too much time. Let A be the input array, and i be the index used of addressing (i=0,1...n1). Let H[k] be the answer for the kth term (i.e sum of values of all combinations up to A[k]). i=0,1,2...k1, so there are k terms before the term at index k, which implies there are k1 gaps between the terms, hence 2^(k1) combinations. For obtaining all combinations up to the kth term, A[k] could have been either added or multiplied to each of the combinations obtained up to the (k1)th term. Hence we have two cases: Addition of A[k] to each of the 2^(k1) terms obtained till (k1)th term. Multiplication of A[k] to each of those terms. Let us consider the first case. Since we are only interested in finding the final sum of values of all possible combinations and not in finding individual combinations themselves, let us find out how much contribution adding of A[k] makes to H[k]. We have 2^(k1) terms whose total sum is H[k1] and A[k] is added to each of them, hence A[k] is added to H[k1], 2^(k1) times. Therefore, H[k] = H[k1] + 2^(k1)*A[k] + X (1) where X is the contribution made by case 2. Let us now look at case 2. In this case, each term ends with T = A[k1]*A[k]. We can further divide this case into two more cases, first in which T is added to each of the combinations up to A[k2] and the next in which it is multiplied to them. The case in which T is added can be dealt with, the same way as case 1. There are k1 terms up to A[k2], giving 2^(k2) combinations whose total sum of values is H[k2], so T is added to H[k2] 2^(k2) times. Therefore, X= H[k2] + 2^(k2)A[k1]A[k] + X1 , where X1 is the contribution made by multiplying T. We can follow the same approach repeatedly, to obtain: X = H[k2] + 2^(k2)A[k1]A[k] + H[k3] + 2^(k3)A[k2]A[k1]A[k] + ……….+ A[0]A[1]..A[k2]A[k1]A[k] (2) From (1) and (2), we get H[k] = H[k1] + 2^(k1)A[k] + H[k2] + 2^(k2)A[k1]A[k] + H[k3] + 2^(k3)A[k2]A[k1]A[k] + ……….+ A[0]A[1]..A[k2]A[k1]*A[k] So, we get H[k] = (i=0 to k1) summation(H[i]) + G[k](3) Where G[k] = 2^(k1)A[k] + 2^(k2)A[k1]A[k] + 2^(k3)A[k2]A[k1]A[k] + A[0]A[1]..A[k1]A[k] = A[k](2^(k1) + 2^(k2)A[k1] + 2^(k3)A[k2]A[k1] + …) = A[k]*(2^(k1) + G[k1]) Hence, G[k] = A[k]*(2^(k1) + G[k1]) (4) Equation 3 can be used to find H[k] using H[k1] and G[k] (which can be found using eqn 4). Hence, the recurrence equations (3) and (4) can be used repeatedly to find the final answer i.e H[n1]; The base cases for H and G are: H[0] = A[0] (since only one combination is possible, the sum is the element itself) G[1] = A1 = A[1] + A[1]*A[0] CPP implementation: Since, we are dealing with two recurrence equations, we can use a dynamic programming approach. For this, we need to initialise three arrays, H ( which stores the answer up to each element), G (which stores the value of G for each element starting from the one at position ‘1’) and H_cumulative ( stores the cumulative sum of answers(H) up to each element). H[0] = A[0] G[1] = A[1](1 + H[0]) = A[1] + A[1]A[0] In each iteration from i=1 to n1, values of H[i], H_cumulative[i] and G[i+1] are computed using the already computed and stored values. answered 07 Jun '17, 19:26

I was finding a formula during the contest , but could not able to do that. But looking at @aakansha's logic, looks like it was a tough one. answered 07 Jun '17, 20:31
The process of finding the solution may be tough, but if you crack it the final form is quite simple :)
(07 Jun '17, 20:44)

Here is my DP solution https://www.codechef.com/viewsolution/14032377 .... Hope it may help :) answered 08 Jun '17, 08:16

I appreciate everybody's answers, really. But the answer from "meooow" is truly BEAUTIFUL. Wow. Also, it explains the key idea of reducing the time from O(n^2) which I just couldn't figure out. Getting to O(n^2) was hard enough for me  and I was proud of that  but then reducing beyond that was too tough!! Now I know. Huge thanks. answered 08 Jun '17, 12:21
By the way I tried to use the "award points" option on meooow's answer but I get an error https://gyazo.com/36da04f6b5c9c976ffaa6b66b68111db In browser Console there is this JS error: The resource from “https://ajax.googleapis.com/ajax/libs/jqueryui/1.10.1/jqueryui.js” was blocked due to MIME type mismatch (XContentTypeOptions: nosniff). Bizarre that jquery is being blocked but maybe admins know why.
(08 Jun '17, 12:28)
click at the "thumbs up" thing to upvote. Award points doesnt work atm. It is supposed to be a future feature.
(08 Jun '17, 15:43)
