[algogeeks] Re: Dynamic Programming - Series

what is square have -ve value then your solution gonna fail. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.

[algogeeks] Re: Dynamic Programming Problem SPOJ-AMR11A

If you need hint: I used DP (Dynamic Programming) to solve this and get AC (Accepted). I stored the matrix as 2-D array and then started with array[R][C]. From there I can go upward and left. In each element of array put the minimum possible value to get the array[R][C]. In case, if we get the v

Re: [algogeeks] Re: Dynamic programming question

The first problem I mentioned is a similar problem. but the second one seems to be little difficult. where additional path we could go is up. - Azhar. On Thu, Dec 15, 2011 at 10:17 PM, Dheeraj Jain wrote: > http://www.geeksforgeeks.org/archives/14943 is a very similar problem. > > > On Thu, Dec

[algogeeks] Re: Dynamic programming problem

Take an array of size Min[N+1][S+1] where, N is the total no. of unique denominations and S is the total sum Let the value array be V[N]; // let it be 1- based indexed for ease of explanation in the below given code snippet. Initialize the following: a) for (i =0; i <= N; ++i) Min[i][0]

Re: [algogeeks] Re: Dynamic programming question

http://www.geeksforgeeks.org/archives/14943 is a very similar problem. On Thu, Dec 15, 2011 at 1:12 PM, WgpShashank wrote: > @Azhar , also for 1st question u r trying Array DS will suffices. Its > Standard Coin Change Problem , u need to solve subproblem 1st , store it in > extra array to avoid r

[algogeeks] Re: Dynamic programming question

@Azhar , also for 1st question u r trying Array DS will suffices. Its Standard Coin Change Problem , u need to solve subproblem 1st , store it in extra array to avoid recalculation , if u are able to produce the sum less given sum then u can use same approach to reach desired sum . it uses the

[algogeeks] Re: Dynamic programming question

@Azhar , 1st Try to formulate the recursive relation , then draw recursive tree , then u willl know why it need DP to solve efficiently , then u can memozation to solve the same . Hope it help. Thanks Shashank Mani CSE ,BIT Mesra http://shashank7s.blogspot.com/ -- You received this message

[algogeeks] Re: Dynamic programming question

Maybe you'll need to tighten up the problem to make it interesting. By your description you could just go all the way up and all the way down in each column and pick up all the apples and then make a move to the right and do the same thing in that column and so on until you get to the destination c

[algogeeks] Re: Dynamic programming question

>From (a,b) to (c,n) => What about traversing all columns n >= j >= a as we can move up-down-right anytime we want. On Dec 14, 5:57 pm, Azhar Hussain wrote: > We need not necessarily pick the apple. We need to suggest a way that could > have maximum apples and path need not be longest. Another pe

Re: [algogeeks] Re: Dynamic programming question

We need not necessarily pick the apple. We need to suggest a way that could have maximum apples and path need not be longest. Another person will follow our path and pick the apples. we can start from specified (i,j) and have to reach specified (i, n) traversing either top, right, down(not left).

[algogeeks] Re: Dynamic programming question

Longest path won't work so well because it will return infinity if a path contains a positive cycle, which doesn't apply here because once you pick up an apple, it's gone. On Dec 13, 7:17 am, vikas wrote: > Graph > take up, right  and bottom as nodes connected to current and do find > max path. >

[algogeeks] Re: Dynamic programming question

Graph take up, right and bottom as nodes connected to current and do find max path. On Dec 13, 3:44 pm, Azhar Hussain wrote: >   We have apples arranged in a mxn matrix. We start from the upper left > corner and have to reach bottom right corner with maximum apples. We can > only move either dow

Re: [algogeeks] Re: Dynamic Programming Cormen

Because here we can not reOrder words, Greedy seems to work fine to me too, i am not able to come up with an contradictory example..will post if will get one... or post if any one can. but here is the DP solution to the

Re: [algogeeks] Re: Dynamic Programming Cormen

Reply for what? On Sat, Jul 16, 2011 at 1:07 PM, Nitish Garg wrote: > Someone please reply. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/vBP5Z

[algogeeks] Re: Dynamic Programming Cormen

Someone please reply. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/vBP5ZdFV9HEJ. To post to this group, send email to algogeeks@googlegroups.com. To unsu

[algogeeks] Re: Dynamic Programming Cormen

I just read that had the cost of a line be defined as just the number of extra spaces and not as the cube of the number of extra spaces, then the greedy approach I mentioned in the above post, can anybody explain why not in the first case? -- You received this message because you are subscribe

[algogeeks] Re: Dynamic Programming Problem

Use complete search, add memoization and you have a top-down dynamic programming solution ready. - lets say we have division positions in an array cuts[] - start and end will identify the position of current cut (taken from cuts[] array) - initialize memo[][] array to INT_MAX, this is the place wh

[algogeeks] Re: Dynamic Programming

Correct. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this grou

[algogeeks] Re: Dynamic Programming

Note the value of j is never decreasing On Jan 7, 8:56 pm, sourabh jakhar wrote: > it is a o(n2) complexity > > > > On Fri, Jan 7, 2011 at 6:13 PM, emacs ray wrote: > > Here is an O(n) approach without any advanced data structures. > > > dp[i] = max{dp[j] : m[i]-m[j] >= n} + a[i] > > > With the

Re: [algogeeks] Re: Dynamic Programming

it is a o(n2) complexity On Fri, Jan 7, 2011 at 6:13 PM, emacs ray wrote: > Here is an O(n) approach without any advanced data structures. > > dp[i] = max{dp[j] : m[i]-m[j] >= n} + a[i] > > With the increasing of i, the optimal value in the brace will > not be descending. We can keep the optimal

[algogeeks] Re: Dynamic Programming

Here is an O(n) approach without any advanced data structures. dp[i] = max{dp[j] : m[i]-m[j] >= n} + a[i] With the increasing of i, the optimal value in the brace will not be descending. We can keep the optimal value so far and check if there is a larger one. #include using namespace std; int

[algogeeks] Re: Dynamic Programming

Thanks -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group

[algogeeks] Re: Dynamic Programming

You may check the exact solution found here: http://users.eecs.northwestern.edu/~dda902/336/hw6-sol.pdf -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this

[algogeeks] Re: Dynamic Programming

I meant any test cases you think I haven't covered in my solution. Although I have run this solution and checked answer manually . -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com

[algogeeks] Re: Dynamic Programming

About? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group

[algogeeks] Re: Dynamic Programming

#include #include using namespace std; int profit(int m[],int p[],int n) { int i,j,dp[7] = {0},k,mx; dp[0] = p[0]; //dp[i] = profit for opening restaurant till i_th index which is dp[i] = max(max(dp[j]) +p[i]),p[i]) , where j=n for(i=1;i<7;i++) { mx = 0;

[algogeeks] Re: Dynamic Programming

Thanks everyone for suggestions and follow my Dynamic Programming - Series for more questions on DP . -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this gr

[algogeeks] Re: Dynamic Programming - Series

Complexity of above solution is O(n) On Jan 5, 10:50 pm, suhash wrote: > In any column, we can place atmost 2 pebbles. > > (a) Considering an isolated column, we can place 1 or 2 pebbles. > Solutions: {1},{2},{3},{4},{1,3},{1,4},{2,4} > (b) Have an array dp[n][5][5]. Let dp[i][j][k] store the max

[algogeeks] Re: Dynamic Programming - Series

In any column, we can place atmost 2 pebbles. (a) Considering an isolated column, we can place 1 or 2 pebbles. Solutions: {1},{2},{3},{4},{1,3},{1,4},{2,4} (b) Have an array dp[n][5][5]. Let dp[i][j][k] store the maximum sum that can be achieved starting from column 'i' to column 'n-1' (columns ar

Re: [algogeeks] Re: Dynamic Programming

yes u correct on this d = val[id] is correct initialization. On Wed, Jan 5, 2011 at 11:02 PM, juver++ wrote: > However, initial value of d should be profit of position id. > There is a case when there is an optimal way not to take any > restaurants to the right of id position, only current is en

Re: [algogeeks] Re: Dynamic Programming

However, initial value of d should be profit of position id. There is a case when there is an optimal way not to take any restaurants to the right of id position, only current is enough. Consider, the following case: m = {1, 2} p = {1, 4}; k = 10; right answer is 4, not 1 :). Also optimal solution

Re: [algogeeks] Re: Dynamic Programming

In main just pass answerIs = max(val[0], solve(0)); On Wed, Jan 5, 2011 at 10:49 PM, juver++ wrote: > Sorry, disregard my first proposition about index i. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send

Re: [algogeeks] Re: Dynamic Programming

Sorry, disregard my first proposition about index i. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googleg

Re: [algogeeks] Re: Dynamic Programming

Minor fixes: i loop should be from 0 to id - 1, if you are moving from left to right. initial value of d should be the val[id] not 0. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.

Re: [algogeeks] Re: Dynamic Programming

ok :):) On Wed, Jan 5, 2011 at 10:43 PM, juver++ wrote: > I was replying to the @Decipher post. Not yours. :) > Your algorithm seems to be ok. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algo

Re: [algogeeks] Re: Dynamic Programming

I was replying to the @Decipher post. Not yours. :) Your algorithm seems to be ok. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to

Re: [algogeeks] Re: Dynamic Programming

I am telling the DP O(n^2) solution, whts wrong in it?? On Wed, Jan 5, 2011 at 10:36 PM, juver++ wrote: > Unfortunately, you are wrong. > We need one loop for i and that is all. All other things for searching max > p[j] is solved by segment tree in O(log n). > > -- > You received this message be

[algogeeks] Re: Dynamic Programming

Unfortunately, you are wrong. We need one loop for i and that is all. All other things for searching max p[j] is solved by segment tree in O(log n). -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge.

Re: [algogeeks] Re: Dynamic Programming

int solve(int id) { if(id==n) return 0; int &d = dp[id]; if(~d) return d; d = 0; for(int i=id+1;i=k) { d >?= val[id] + solve(i); } } return d; } Its O(n^2), and Juver++, is very correct. On Wed, Jan 5, 2011 at 10:22

[algogeeks] Re: Dynamic Programming

I think your solution will take O(n3) time , as it will require three loops . 1st for index i , 2nd for first max and 3rd for second max . Instead we should take : dp[i] = max(dp[j]) + p[i] , where j k . Pls correct me if something is wrong . -- You received this message because you are subscribe

[algogeeks] Re: Dynamic Programming Problem on Strings

what about printing these strings onto terminal. can printing of the string is also similar. I tried to develop the algo but got messed up.can some one help? On Aug 8, 2:53 am, Amir hossein Shahriari wrote: > @ankur: dp[i][j] number of (prefix) strings that have i As and j Bs is: > dp[i-1][j] num

[algogeeks] Re: Dynamic Programming

Yes its some what similar..!! On Dec 7, 4:57 am, sharad kumar wrote: > is this similar to coin exchange problem? > > > > On Mon, Dec 7, 2009 at 5:42 PM, Hitesh wrote: > > hi there, > > Need help on this..any way or suggestion how to solve this problem.. > > any help would be appreciated. > > > L

[algogeeks] Re: Dynamic Programming Algorithm for "swim relay team"

Hi, There are five segments in c:- 1.Data Segment 2.Code Segment 3.Stack Segment 4.Bss segment 5.Heap segment Can any one explain what things are stored in which segment when a c program actually runs? I have read that uninitialized and initialized global variables are stored in bss and stack segme

[algogeeks] Re: Dynamic Programming Algorithm for "swim relay team"

Hi I have a simmilar Problem , and was wondering if you can elaborate on the funktion , sorry I am a starter and I need a bit more explainations ... f(P1,P2, P3,...Pn) ,,, How can I implement it in Java ,... Thank you Samuel On 6 Jan., 08:10, Satish <[EMAIL PROTECTED]> wrote: > We can used

[algogeeks] Re: Dynamic Programming Algorithm for "swim relay team"

Well, actually that only solves for when the # of players and events are same, what if there're more players than events? The recursion you describe has exponential growth rate. f(c) for some set of P's can't really be cached, because the number of possible c's is just are huge as exponential.

[algogeeks] Re: Dynamic Programming Algorithm for "swim relay team"

We can use dynamic programming here to find out the team configuration with minimum time. Define a function f(P1,P2, P3,...Pn) that returns the players sequence (given n players for n rounds, which swimmer swims at which position) that would return the total minimum time. Then f() can be defined

[algogeeks] Re: Dynamic Programming Algorithm for "swim relay team"

At risk of stating the incredibly obvious, or giving away answer to a fun interview question. The naive but correct algorithm that gives the solution will have tried every combination M of K swimmers in M events. which will give you K!/(K-M)! arrangements, and the algorithm would then compare the

[algogeeks] Re: Dynamic programming?

let pr[i] be answer to sub-problem 1..i and there is restaurant built at i. (maximum expected total profit) How do we calculate pr[i]? Expected profit from location i + max. pr[j], where location of j is at least k apart from location i. pr[i] = p[i] + max(pr[j]), where j is between 1..i-1 and m[

[algogeeks] Re: dynamic programming ..

Hi, Greedy solution will work only when the denomination of coins are such that they are multiples of the smallest number present (it should be greater than 1) In dynamic programming we check all possible combination. and improve the runtime by storing results in tables/arrays we can save a lot o

[algogeeks] Re: dynamic programming ..

Hi mukesh, Let M(S),S>=0 be true if its possible to make money S with the given coins v1,v2,...vk. Then, M(S)=M(S-v1) || M(S-v2) || ...|| M(S-vk). Base Case: M(vi)=true for 1<=i<=k. M(0)=true Let vl be the smallest of all vi's where 1<=i<=k. Then M(1...vl-1)=false. On 3/3/07, mukesh tiwari <[EMAI

[algogeeks] Re: dynamic programming

I have the same question. It seems the S-G function doesn't work when there is a draw... ? "Rajiv Mathews 写道： " > Is there a way to leverage this solution to handle more than one pile > of matches? > > Say there were k piles each containing n_1, n_2, ..., n_k matches, > with the same rules, that

[algogeeks] Re: dynamic programming

k...ThanxI have cleared my doubt I would like to ask here one more question similar to this question. Suppose a game is played between A and B, consider a number n = 100, at each time each player adds a divisor of n < 100 to n. Find which player won the game when total = 1953, when the

[algogeeks] Re: dynamic programming

Yes , it will always fill with 3 . the best result both player can get for n > 4 is always draw. You can check it for some values on paper . if you want to have a winner you must change the basic conditions of the problem. On 11/28/06, ravi <[EMAIL PROTECTED]> wrote: > > > We Define an array Win[]

[algogeeks] Re: dynamic programming

We Define an array Win[] which its i'th element shows the best result player one can get if every one plays his/her best games. the base case is : Win[1] = Win[3] = Win[4] = 1; Win[2] = 3 (draw) for filling the element Win[n] we consider elements Win[n-1] , Win[n-3] , Win[n-4] . if any of them i

[algogeeks] Re: dynamic programming in tree

hi, could you explain the part -- Since these introduce strict inequalities, so you need rewrite rules for these too. But it all falls out by case analysis. thanks

[algogeeks] Re: dynamic programming in tree

Yes. You can cast the program as a DP, but the memo table may well have size exponential in the number of weights due to the NP hardness. I.e. in general the "DP" degenerates into an exhaustive search. Trees with internal isomorphisms (including A(j) values) improve efficiency. The DP is of the

[algogeeks] Re: dynamic programming in tree

it is NP, but I am have this feeling that there is a dynamic programming to solve it.

[algogeeks] Re: dynamic programming in tree

[a,b] is user input. weights should be inside the interval. if outside, it will be a violation and we would like to minimize it.

[algogeeks] Re: dynamic programming in tree

I fear this problem is NP hard.

[algogeeks] Re: dynamic programming in tree

a question: Dose [a,b] have any thing to do with the problem? [EMAIL PROTECTED] wrote: > I have a binary tree. So there is a unique path from root > to each leaf of the tree. > > > Each leaf L also has a number associated with it, A(L). In addition > user inputs an interval [a,b]. > > > Now, I