How to solve the question PLUSMUL from Snackdown Elimination round?

help
, , , ,
3

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 :smiley:
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
30 Likes