### anamolous's blog

By anamolous, history, 4 months ago,

I have come across a problem but wasn't able to solve... Can someone help me with below problem.

You are given n balloons(n is even), indexed from 0 to n — 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the two adjacent(let be i,i+1) balloon, you will get nums[i — 1] * nums[i] * nums[i + 1]*nums[i + 2] coins. If i — 1 or i + 2 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.After bursting i and i+1 ,i-1 and i+2 would become adjacent.

Return the maximum coins you can collect by bursting the balloons wisely.

Constraints:

1<n<=200

1<=nums[i]<=1000

TestCase:

n=4

nums=[3,1,5,8]

Explaination remove element at index 1,2 i.e(1,5) will get score= 3 x 1 x 5 x 8 =120

array would become [3,8] removing this two would get us score= 1 x 3 x 8 x 1=24

ans=144

Similar Problem:

similar problem but with one ballon burst instead of two

I have solved the similar problem but not getting approach for the main problem.

UPD: We have got the optimal (N^4/8) (thanks ShivanshJ ) approach would pass the limit thankyou man if got some optimisation even please comment below!!!

• +4

 » 4 months ago, # |   0 can you guys please help me with the approach for the above problem Priyansh31dec , sharmaharisam , codemastercpp??thanks in advance!!
 » 4 months ago, # | ← Rev. 3 →   +3 Let us define a function f such that f(l, r) gives the answer for the subarray [l, r]. The base case is that if r <= l then f(l, r) = 0. Else there is some pivot index i such that f(l, r) = f(l, i-1) + f(i+1, r-1) + nums[i-1]*nums[i]*nums[r]*nums[r+1]. We can iterate through all indices i in the range to find the optimal pivot. Final answer for whole array is just f(0, n-1). PS: Can you send the link to the problem?
•  » » 4 months ago, # ^ | ← Rev. 3 →   +3 sorry I don't have link for the problem as came across this problem in some hiring test.BTW, which elements you are removing in your approach as in my opinion your solution would have some extra answer than the expected.I have written the brute force to make case n=8a=[3,1,5,8,7,5,6,2]expected output: 2196code made from Your approach giving: 2286 can you please explain this testcase with your approach if I am going wrong. your approach if I am not wrongdef ans(l,r): if r<=l:return 0 tot=0 for i in range(l,r): tot=max(ans(l,i-1)+ans(i+1,r-1)+a[i-1]*a[i]*a[r]*a[r+1],tot) return tot  If mentioned this approachdef ans(l,r): if r<=l:return 0 tot=0 for i in range(l+1,r): tot=max(ans(l,i-1)+ans(i+1,r-1)+a[i-1]*a[i]*a[r]*a[r+1],tot) return tot Its not optimal as giving less answer: 2020
•  » » » 4 months ago, # ^ |   +3 Nvm. Just realized I misunderstood something.
•  » » » » 4 months ago, # ^ |   0 yeah you may refer to the link to similar problem but change in main problem is we are required to remove two element instead of one which lead me not getting any optimal substructure as got for similar 1 burst balloon problem
 » 4 months ago, # | ← Rev. 7 →   +3 I have an O(n^4) solution. Can someone tell how to optimize it? Reindex the array from [1,n], attach fake balloons having value = 1 at index 0 and n+1. dp(i)(j) means the max. no. of coins we can get if I burst the entire subarray [i+1,j-1] before bursting ith or jth balloon. (Length of subarray is even). In my last operation of destroying subarray [i+1,j-1] two last balloons having index r and s will be left which will give: num(i)*num(r)*num(s)*num(j) coins. Note that i
•  » » 4 months ago, # ^ | ← Rev. 3 →   +1 Yeah your substructures making much sense to me and independent and the approach is accurate just now we need is the optimisation part from N^4 to N^3(or N^3log(N))UPD: we have n<=200 not n<=500 hence can't we just reduce second loop of J to (N/2) third loop of r as well to (N/2) and s as well to (N/2) hence it would be something like (N^4/8)=2*10^8 hence should pass the limit ThankYou very much man!!
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +3 You're welcome! :) Yeah you're right by reducing the length of loops to half as avoid odd length subarrays. It was a nice problem!