anamolous's blog

Need help for the below problem....
By anamolous, history, 3 years ago, In English

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!!!

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can you guys please help me with the approach for the above problem Priyansh31dec , sharmaharisam , codemastercpp??

thanks in advance!!

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

Let us define a function f such that f(l, r) gives the answer for the subarray [l, r].

  1. The base case is that if r <= l then f(l, r) = 0.
  2. 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.
  3. Final answer for whole array is just f(0, n-1).

PS: Can you send the link to the problem?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    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.

    your approach if I am not wrong
    If mentioned this approach

    Its not optimal as giving less answer: 2020

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Nvm. Just realized I misunderstood something.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
»
3 years ago, # |
← Rev. 7   Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    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!!

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      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!

      → Reply