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.
3 Likes
There are n-1 gaps and there are two choices to fill each of them ( + or *), hence there are 2^(n-1) 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…n-1). 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…k-1, so there are k terms before the term at index k, which implies there are k-1 gaps between the terms, hence 2^(k-1) 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 (k-1)th term. Hence we have two cases:
Addition of A[k] to each of the 2^(k-1) terms obtained till (k-1)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^(k-1) terms whose total sum is H[k-1] and A[k] is added to each of them, hence A[k] is added to H[k-1], 2^(k-1) times. Therefore,
H[k] = H[k-1] + 2^(k-1)*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[k-1]*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[k-2] 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 k-1 terms up to A[k-2], giving 2^(k-2) combinations whose total sum of values is H[k-2], so T is added to H[k-2] 2^(k-2) times. Therefore,
X= H[k-2] + 2^(k-2)*A[k-1]*A[k] + X1 ,
where X1 is the contribution made by multiplying T. We can follow the same approach repeatedly, to obtain:
X = H[k-2] + 2^(k-2)*A[k-1]*A[k] + H[k-3] + 2^(k-3)*A[k-2]*A[k-1]*A[k] + ……….+ A[0]A[1]…*A[k-2]*A[k-1]*A[k] -------------(2)
From (1) and (2), we get
H[k] = H[k-1] + 2^(k-1)*A[k] + H[k-2] + 2^(k-2)*A[k-1]*A[k] + H[k-3] + 2^(k-3)*A[k-2]*A[k-1]*A[k] + ……….+ A[0]A[1]…*A[k-2]*A[k-1]*A[k]
So, we get
H[k] = (i=0 to k-1) summation(H[i]) + G[k]-----(3)
Where G[k] = 2^(k-1)*A[k] + 2^(k-2)*A[k-1]*A[k] + 2^(k-3)*A[k-2]*A[k-1]*A[k] + A[0]A[1]…*A[k-1]*A[k]
= A[k]*(2^(k-1) + 2^(k-2)*A[k-1] + 2^(k-3)*A[k-2]*A[k-1] + …)
= A[k]*(2^(k-1) + G[k-1])
Hence,
G[k] = A[k]*(2^(k-1) + G[k-1]) ------(4)
Equation 3 can be used to find H[k] using H[k-1] 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[n-1];
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] = A[1](1 + H[0]) = 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 n-1, values of H[i], H_cumulative[i] and G[i+1] are computed using the already computed and stored values.
7 Likes
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.
Assume the input is an array a of N numbers, and let us define f(i) to be the answer for the subarray a]0..i]. The overall answer is of course f(N-1). The next thing to do is observe. Take a look at the image below. The sum of the expressions in the red box is f(3). Similarly the blue box corresponds to f(2), the green box to f(1), and the yellow box to f(0).
![alt text][2]
Clearly, we can define f(3) as
\begin{aligned}
f(3) &= \left[ f(2) + 2^2 × a_3 \right] + \left[ f(1) + 2^1 × a_3 × a_2 \right] \\
&+ \left[ f(0) + 2^0 × a_3 × a_2 × a_1 \right] + \left[ a_3 × a_2 × a_1 × a_0 \right]
\end{aligned}
Armed with this, we can put forward a definition of f(i).
\begin{aligned}
f(i) &= \Bigg[ f(i-1) + 2^{i-1} × a_i \Biggr]
+ \left[ f(i-2) + 2^{i-2} ×\prod_{k=i-1}^i a_k \right] \\
&+ \left[ f(i-3) + 2^{i-3} ×\prod_{k=i-2}^i a_k \right] +\;...\;
+ \left[ f(0) + 2^{0} ×\prod_{k=1}^i a_k \right] + \prod_{j=0}^i a_j \\
&= \sum_{j=0}^{i-1}f(j) + \Biggl[2^{i-1}a_i + \sum_{j=0}^{i-2}\left( 2^j × \prod_{k=j+1}^i a_k \right)+ \prod_{j=0}^i a_j \Biggr]
\end{aligned}
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{aligned}
g(i) &= \sum_{j=0}^{i}f(j) \\
h(i) &= 2^{i-1}a_i + \sum_{j=0}^{i-2}\left( 2^j × \prod_{k=j+1}^i a_k \right)+ \prod_{j=0}^i a_j
\end{aligned}
Now, observe that
\begin{aligned}
g(i) &= g(i-1) + f(i) \\
h(i) &= h(i-1)×a_i + 2^{i-1}a_i \\
f(i) &= g(i-1) + h(i)
\end{aligned}
For the base cases, we have f(0) = g(0) = h(0) = a_0.
Now we can compute all three functions in linear time and solve the problem 
Note that I have tried to explain everything using proper notation, but during the contest I usually find it easy to scribble a few small examples and try to find a pattern. So I encourage you to try that out with this problem and get the feel of it, especially for function h.
Here is my
[1] for reference. Hope this helps :)
[1]: https://www.codechef.com/viewsolution/14136944
[2]: https://discuss.codechef.com/upfiles/expr_plusmul.png
29 Likes
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.
1 Like
The process of finding the solution may be tough, but if you crack it the final form is quite simple 
What an awesome explanation, why not post this as UNOFFICIAL editorial
1 Like
Respect #Shakti_Billi
5 Likes
Thanks a lot for such a detailed explanation!
1 Like
Thanks a lot for such a detailed explanation!
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.
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/jquery-ui.js” was blocked due to MIME type mismatch (X-Content-Type-Options: nosniff).
Bizarre that jquery is being blocked but maybe admins know why.
click at the “thumbs up” thing to upvote. Award points doesnt work atm. It is supposed to be a future feature.
Haha thanks guys 
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…
@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.