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.
Can someone please help me with the approach or mention someone who can help???
Thanks in Advance.
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!!!
can you guys please help me with the approach for the above problem Priyansh31dec , sharmaharisam , codemastercpp??
thanks in advance!!
Let us define a function f such that f(l, r) gives the answer for the subarray [l, r].
PS: Can you send the link to the problem?
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=8
a=[3,1,5,8,7,5,6,2]
expected output: 2196
code made from Your approach giving: 2286
can you please explain this testcase with your approach if I am going wrong.
Its not optimal as giving less answer: 2020
Nvm. Just realized I misunderstood something.
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
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<r<s<j. Basically to destroy the subarray [i+1,j-1] (before bursting ith or jth balloon), I destroy subarray [i+1,r-1] then subarray [r+1,s-1] followed by [s+1,j-1] and finally the rth and sth balloon.
So, dp(i)(j) = max over all r and s {dp(i)(r)+dp(r)(s)+dp(s)(j) +num(i)*num(r)*num(s)*num(j)}.
Answer to the problem is dp(0)(n+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!!
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!