×

# Ball Elimination - DP problem

 3 Can someone please explain the approach for this problem. The approach in the editorial is not clear. Thanks!! :-) asked 12 Mar '17, 12:33 206●5 accept rate: 11% 3 That Q is definitely not "Very Very Easy" lol. (12 Mar '17, 13:27)

 6 My approach is slightly different from what is described in the editorial, but I hope it will be easy to understand. If $a$ is our array of $n$ balls, let $f(i, j)$ be the cost of eliminating all the balls in $a[i..j]$. Our required solution is then $f(0, n-1)$ (assuming 0-based indexing). How do we calculate the value of $f(i, j)$? If $a[i]=a[j]$, let us eliminate all balls between $i$ and $j$, then we can remove ball $i$ and $j$ with no cost. Hence in this case, $f(i, j)=f(i+1, j-1)$. If $a[i] \ne a[j]$, let us split our given range into two pieces to be solved recursively. We cannot immediately say where is the best index for splitting hence we have to try all indices between $i$ and $j$. In this case, $f(i, j) = min\{f(i, k) + f(k+1, j) : i \le k \lt j\}$ What about our base cases? If $i=j+1$, then our range is empty, and $f(i,j)=0$. If $i=j$, then we have one ball in our range which requires cost $1$ to remove. So here $f(i,j)=1$. Our final definition of $f$ is as follows $$f(i,j) = \begin{cases} 0 & \text{if } i=j+1, \\ 1 & \text{if } i=j, \\ f(i+1,j-1) & \text{if } a[i]=a[j], \\ min\{f(i, k) + f(k+1, j) : i \le k \lt j\} & \text{otherwise}. \end{cases}$$ The dynamic programming solution will require $\mathcal{O}(n^2)$ space and $\mathcal{O}(n^3)$ time. For this problem the top-down approach is easier to implement. Here is the link to my solution. As a challenge you can also try to implement a bottom-up approach :) Hope this helps! answered 13 Mar '17, 02:54 6★meooow ♦ 6.7k●7●17 accept rate: 48% Nice explanation. Can you please present your views in regards of table filling DP? I mean how the approach given in editorial working? (13 Mar '17, 08:23) Thanks for the solution and it would be good if you can provide a table filling DP solution! (13 Mar '17, 10:44) 1 In the editorial $f(i,j)$ is said to be for the range $i$ to $j$ inclusive, but the solution described is for $f(i,j)$ with $i$ inclusive and $j$ exclusive. There is another mistake in the editorial where "f(i-1,k+1) + f(k+1, j)" should be "f(i+1,k) + f(k+1, j)". With these corrections I hope the explanation makes sense. (13 Mar '17, 17:02) meooow ♦6★ I can easily interpret the mistake by looking through the solution. But i wanna know about how table is filling there? (13 Mar '17, 19:10) 2 @bansal1232 by the editorial's approach it is clear that the cases must be filled in increasing order of $j-i$, in other words the indices with $i$ close to $j$ must be filled first. Hence the solution fills in increasing order of the variable len. The base case for $i=j$ is $0$. The actual table filling would look something like this.. (13 Mar '17, 23:17) meooow ♦6★ O..M..G!! Seriously meooow that's AWESOME!!! (14 Mar '17, 11:38) showing 5 of 6 show all
 1 We have got 2 conditions - eliminate single ball and pay 1 pound. eliminate 2 neighboring balls of same colors for no cost. So we wil try to form a recursive solution which we will later memoize. We will have two pointers(index for given array) in our recursive function solve(). solve(int i,int j) { } 2.we take a temp variable to store the ith color in array. temp=ar[i]; 3.Take a variable ans= some large value because we want the minimum answer. 4.Now we need a loop to generate different index between i and j. for(int k=i;k<=j;k++) { } 5.Now let's see different conditions in the loop. a. we check if(temp==ar[k]). b. if(k==i) i.e it is the first element (i.e ith element) so we call the function-  ans=min(ans,1+solve(k+1,j)); since we have used ith ball which is only single ball so we add 1 and call the function from k+1 to j.  c. if(k==j) i.e the last element - ans=min(ans,solve(i+1,k-1));  since temp(which is 1 element was equal to ar[k] which means the first ball color(ith) is equal to last ball (jth) color ,so we don't have to pay for it and we just called the function from i+1 to k-1. d. if both above case are not true this means k is in between i and j so it is simple to see that ans=min(ans,solve(i+1,k-1)+solve(k+1,j)); leaving the first (ith) ball and kth ball we call the function. 6.Now we are left with the base cases- We have 2 base cases because in last there are 2 conditions - a. 1 ball left i.e i==j. so we return 1 as only single ball left. if(i==j) { return 1; }  b. otherwise if(i>j) { return 0; } -The memoization is simple which you can do by declaring a 2D array. First try it yourself and for reference you can see my code http://pastebin.com/hzk4CFK5 answered 13 Mar '17, 00:16 11●1 accept rate: 0% I appreciate your effort but try to explain in more simple and precise language, if u can. (13 Mar '17, 00:22) I agree with @bansal1232 . (13 Mar '17, 01:03)
 1 All right let me give a shot trying to explain you the solution. Let me first define a state. I am taking (i,j) as a state which means the given array from index i to j inclusively. Now, when I say answer for a state(i,j) that means the minimum moves required when i have an array from index i to j(inclusively). n : size of array ( 0-based array ) Aim : we need to find the solution for the state (0,n-1) -> whole array. How to accomplish it: we are going to collect answer for the desired state by taking the optimal combination of sub-states. Okay, once again get back to state (0,n-1). Lets see the first element at index 0 i.e arr[0]. For first element we have two options either we will eliminate it individually (this will cost 1 move) or We will club it with some other index having same element as of arr[0]. lets say[ 0 , 1 , 2 , k1 , 4 , 5 , k2 , . . . , n-1 ] are the indices of the array. and element at index 0 matches with element at index k1 and element at index k2 means arr[0] == arr[k1] == arr[k2]. Now once again get back to our answer for state concept. Let's assume we have answer for all possible states (i,j) except state(0,n-1), which is the desired one. So,we can say ans(0,n-1) = 1 + ans(1,n-1) // means we are eliminating arr[0] individually Here, we have eliminated arr[0] individually so we add 1 to answer + we need to add answer for rest of array so we add the answer for the state (1,n-1). or 0 1 2 k1 4 5 k2 .... n-1 ------- ---------------------- ans(0,n-1) = ans(1,k1-1) + ans(k1+1,n-1) This means we are clubbing idx 0 and k1 ( this counts 0 move ) ,but to do this we need to delete elements in between 0 and k1 , but as assumed we already the answer for that state(1,k1-1) + we also need to add the answer for array after k1 index because they are not eliminated so we will add answer for that state too i.e ans(k1+1,n-1) or 0 1 2 k1 4 5 k2 .... n-1 ------------------- ---------- ans(0,n-1) = ans(1,k2-1) + ans(k2+1,n-1) Same above explaination. So, ans(0,n-1) will be the minimum from above three conditions and hence, the question.  We will just put the above relation for states in recursion by initializing the base states. Base States : ans(i,j) = 1 for all i == j ans(i,j) = 0 for all i > j  My Solution : here . answered 14 Mar '17, 06:11 42●1 accept rate: 0%
 0 It's very easy DP. But it need a little bit perfection on this. Give me some time, i will upload the full editorial of this question answered 12 Mar '17, 13:43 2.8k●3●17 accept rate: 16% Thanks! Your response is much awaited!! (12 Mar '17, 22:56) Sorry for that. I still could not able to figure out the right way to explain you. It's all about DP. There is getting a problem of manipulating the recursion formula given in the editorial (12 Mar '17, 23:29) ok. But any simple explanation would be appreciated!! Thanks!! (12 Mar '17, 23:54) Ok. So please give me more time. I am just little bit busy in our HINDU Methodology Holy festival. (13 Mar '17, 00:22)
 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:

×1,878
×365

question asked: 12 Mar '17, 12:33

question was seen: 1,919 times

last updated: 14 Mar '17, 11:38