×

# How to solve the question PLUSMUL from Snackdown Elimination round?

 3 1 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 2.4k●4●20 accept rate: 17%

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)$.

Clearly, we can define $f(3)$ as
\begin{align} 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{align}

Armed with this, we can put forward a definition of $f(i)$.
\begin{align} 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{align}

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^{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{align}

Now, observe that \begin{align} 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{align}

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 :D
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 code for reference. Hope this helps :)

6★meooow ♦
7.0k717
accept rate: 48%

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) 6★

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) 6★
showing 5 of 6 show all
 1 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 56●2 accept rate: 9% 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) meooow ♦6★
 0 Here is my DP solution https://www.codechef.com/viewsolution/14032377 .... Hope it may help :-) answered 08 Jun '17, 08:16 14●2 accept rate: 0%
 0 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 3★royappa 21●1 accept rate: 0% 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. (08 Jun '17, 12:28) royappa3★ 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)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,647
×476
×210
×170
×6
×4

question asked: 07 Jun '17, 17:47

question was seen: 2,302 times

last updated: 24 Jun '17, 02:41