You are not logged in. Please login at www.codechef.com to post your questions!

×

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

abdullah768's gravatar image

6★abdullah768
2.1k218
accept rate: 16%


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
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 :)

link

answered 07 Jun '17, 20:19

meooow's gravatar image

6★meooow ♦
6.7k717
accept rate: 48%

edited 08 Jun '17, 22:07

1

What an awesome explanation, why not post this as UNOFFICIAL editorial :)

(07 Jun '17, 22:10) godslayer121★
5

Respect #Shakti_Billi

(07 Jun '17, 22:13) vijju123 ♦6★
1

Thanks a lot for such a detailed explanation!

(07 Jun '17, 22:34) abdullah7686★

Haha thanks guys :P

(08 Jun '17, 22:08) meooow ♦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) viralivora5★

@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) meooow ♦6★
showing 5 of 6 show all

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] = 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 n-1, values of H[i], H_cumulative[i] and G[i+1] are computed using the already computed and stored values.

link

answered 07 Jun '17, 19:26

aakanksha_21's gravatar image

3★aakanksha_21
711
accept rate: 0%

Thanks a lot for such a detailed explanation!

(07 Jun '17, 22:34) abdullah7686★

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.

link

answered 07 Jun '17, 20:31

coolrohan123's gravatar image

4★coolrohan123
562
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★

Here is the link to my solution ... I applied both 1d DP and 2d DP ..

link

answered 08 Jun '17, 08:11

shuklacoder55's gravatar image

3★shuklacoder55
142
accept rate: 0%

edited 08 Jun '17, 08:13

Here is my DP solution https://www.codechef.com/viewsolution/14032377 .... Hope it may help :-)

link

answered 08 Jun '17, 08:16

shuklacoder55's gravatar image

3★shuklacoder55
142
accept rate: 0%

edited 08 Jun '17, 08:17

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.

link

answered 08 Jun '17, 12:21

royappa's gravatar image

3★royappa
211
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) vijju123 ♦6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,535
×361
×200
×162
×5
×4

question asked: 07 Jun '17, 17:47

question was seen: 2,084 times

last updated: 24 Jun '17, 02:41