Re: [algogeeks] DP problems

Got it. Any idea on how to solve the problem 2(e) ? On 6 June 2014 00:52, Saurabh Paliwal wrote: > T[i][j] = 0 (i < 0 || j >=n || i >= j || s[i] != s[j]) > > T[i][j] = 1 + T[i-1][j+1] > > > > > On Fri, Jun 6, 2014 at 12:19 AM, kumar raja > wrote: > >> If i get u correctly, this is the recurren

Re: [algogeeks] DP problems

T[i][j] = 0 (i < 0 || j >=n || i >= j || s[i] != s[j]) T[i][j] = 1 + T[i-1][j+1] On Fri, Jun 6, 2014 at 12:19 AM, kumar raja wrote: > If i get u correctly, this is the recurrence relation ( i feel this makes > many people to understand the solution rather than looking at the code) > > > T[i.

Re: [algogeeks] DP problems

If i get u correctly, this is the recurrence relation ( i feel this makes many people to understand the solution rather than looking at the code) T[i..j] indicates the length of longest even length palin string ( not exactly palin but i think u know what i am saying) with i as begin and j as endi

Re: [algogeeks] DP problems

And now I get what you meant when you said "palindrome". You should have explained that if that was "not exact palindrome" So yes, your solution seems correct but that is the brute force approach. It runs in O(n*n*n) as there are n*n substrings and every check is linear. DP solution helps save tim

Re: [algogeeks] DP problems

Ok! So I guess now we are talkng my solution. What i do is maintain two pointers i and j, i is the end of the first string and j is the beginning of the second. If both the character match, I calculate the answer for pointers i-1,j+1 and add 1 to the answer for i,j. If they don't match, I simply ma

Re: [algogeeks] DP problems

U need not get an exact palindrome. u will start comparing from both the end points till they are equal and does not cross each other. So that should be possible in linear time right. I did not get ur code exactly and u have written O(n*n) so i have got the doubt. On 5 June 2014 23:22, Saurabh Pa

Re: [algogeeks] DP problems

Dude! That is what I just posted. Also your logic is wrong, Palindrome thing is just not working. Think for a while on this problem. On Thu, Jun 5, 2014 at 11:18 PM, kumar raja wrote: > Yes i agree that my recurrence relation is wrong. I have checked it some > inputs, it did not work. But i thi

Re: [algogeeks] DP problems

Yes i agree that my recurrence relation is wrong. I have checked it some inputs, it did not work. But i think the brute force solution is possible in O(n^3) solution. We have O(n^2) combination of end points. we can check for the maximum possible even length palin string in O(n). So that will give

Re: [algogeeks] DP problems

Hi all! Well, I agree with Shashwat in that Kumar is wrong with his solution. For example a string " kumarxyzramuk " will tell you why. I have a solution which runs in O(n*n) time. It is top-down dynamic programming approach. Let me know if you don't understand something or if there is some glitch

Re: [algogeeks] DP problems

Code ? On Thu, Jun 5, 2014 at 7:08 PM, kumar raja wrote: > U have two dimensions for the table ( has O(n^2) entries.) and to check > whether string is palindrome or not it will take O(n) . So it is O(n^3) > solution. > > I have checked it manually for some inputs, and it works. > > > On 5 June

Re: [algogeeks] DP problems

U have two dimensions for the table ( has O(n^2) entries.) and to check whether string is palindrome or not it will take O(n) . So it is O(n^3) solution. I have checked it manually for some inputs, and it works. On 5 June 2014 18:53, Shashwat Anand wrote: > I am not too sure about your O (N^3)

Re: [algogeeks] DP problems

I am not too sure about your O (N^3) solution even. Can you link the working code ? On Thu, Jun 5, 2014 at 6:48 PM, kumar raja wrote: > This is a very good collection of DP problems. > > I want the answers for problem 2(e) > and problem 14. > > for problem 14 the recurrence relation > that i h

[algogeeks] DP equation for interval problem

please help me with the following problem: http://www.spoj.com/problems/JUICE/ bit mask will require very large memory. If I sort the intervals in decreasing order of their start time.. I still cant make it to a dp If I sort the intervals in decreasing order of their finish times I am still not

[algogeeks] dp problem

how to solve these type of problems http://www.spoj.pl/problems/GNY07H/ means how to approach this problem by dp. -- *UTKARSH SRIVASTAV CSE-3 B-Tech 3rd Year @MNNIT ALLAHABAD* -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. T

Re: [algogeeks] DP problems in SPOJ

I think the first problem involves some mathematics... In this we fix the first bit and if the remaining no. of bits are odd then we calculate the no. as follows If we have 2^4=16 then total bits 5 so we do not include this. Total no. of bits in one less than the given no. (in this eg. 15) is 4.

[algogeeks] DP problems in SPOJ

Hi I have jus started to learn DP and I have coded the standard algorithms(LCS,etc). I have been trying these problems in SPOJ: http://www.spoj.pl/problems/NOVICE63/ http://www.spoj.pl/problems/NY10E/ I understand these may be solved elegantly using DP,but I dont get to code the same. Can any1 he

Re: [algogeeks] Dp solution for this problem?

thnx all On Mon, Oct 31, 2011 at 10:13 PM, Vandana Bachani wrote: > Hi Mohit, > Bellman-Ford algorithm is a dynamic programming algorithm but u need it > only if dijkstra's SP wont solve the problem... and Dijkstra's algo works > only for +ve weights. So if u r sure that there maybe negative weig

Re: [algogeeks] Dp solution for this problem?

Hi Mohit, Bellman-Ford algorithm is a dynamic programming algorithm but u need it only if dijkstra's SP wont solve the problem... and Dijkstra's algo works only for +ve weights. So if u r sure that there maybe negative weights then you will need to use bellmann ford which is a DP algo. On Mon, Oct

Re: [algogeeks] Dp solution for this problem?

I knew this could be done using Min Path finding algo. But what about DP for this problem , guys? On Mon, Oct 31, 2011 at 3:49 AM, SAMM wrote: > This can be done using the Dijkstra's algorithm , Start frm the source > frm the Destination (In this example from (2 2)) . You need to > consider the

Re: [algogeeks] Dp solution for this problem?

This can be done using the Dijkstra's algorithm , Start frm the source frm the Destination (In this example from (2 2)) . You need to consider the index of the array as the the vertices and the weigjht as the the value for the movement from the present vertex to it's connecting neighbour .. On 10/

Re: [algogeeks] Dp solution for this problem?

How about this one... 5 9 10 1 3 7 4 4 8 2 1 9 Check the immediate neighbors / 8 (or less) neighbors of your given cell.. Here for 5 the neighbors are 9,7,3 for 9 they are 5,3,7,4,10 for 7 they are 5,9,10,4,1,2,8,3 etc For every cell calculate the sum of it an its neighbors, find the minimu

Re: [algogeeks] Dp solution for this problem?

if all possible diagonal movements are allowed i guess we must check all the possibilities On Mon, Oct 31, 2011 at 12:52 AM, mohit verma wrote: > Given a matrix you have to find the shortest path from one point to > another within the matrix. The cost of path is all the matrix entries on > the w

Re: [algogeeks] Dp solution for this problem?

Consider each element of the matrix as a node of a graph. Connect the nodes to the adjacent nodes (up, down, left, right or diagonal) using directed edges having weight equal to the weight of the node it is incident on, eg. any edge coming into (0,0) with have weight 5. Given the starting point to

Re: [algogeeks] Dp solution for this problem?

Min Cost Path: http://www.geeksforgeeks.org/archives/14943 On Mon, Oct 31, 2011 at 12:52 AM, mohit verma wrote: > Given a matrix you have to find the shortest path from one point to > another within the matrix. The cost of path is all the matrix entries on > the way. You can move in any directio

[algogeeks] Dp solution for this problem?

Given a matrix you have to find the shortest path from one point to another within the matrix. The cost of path is all the matrix entries on the way. You can move in any direction (up, down, left, right, diagonally) e.g. 5 9 10 1 3 7 4 4 8 2 1 9 So shortest path from (0,0) to (2,2) is (0,0)--(1,

[algogeeks] DP Help...

any one give a good link to study Dynamic Programming concepts?? --Regards Vikram -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to

Re: [algogeeks] DP or DFS

nothing :P BFS :P On Wed, Jul 6, 2011 at 1:23 PM, KK wrote: > https://www.spoj.pl/problems/SHOP/ > Anybody plzz post a solution to the above problem... > i tried with dp but it failed... > How to implement with DFS or if possible with DP??? > > -- > You received this message because you are subsc

[algogeeks] DP or DFS

https://www.spoj.pl/problems/SHOP/ Anybody plzz post a solution to the above problem... i tried with dp but it failed... How to implement with DFS or if possible with DP??? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group

Re: [algogeeks] Dp problem

read topcoder tutorial binary search...u will get an idea On Mon, Apr 4, 2011 at 4:38 PM, rajat ahuja wrote: > then please share wid me yaar > thanks in advance > > On Mon, Apr 4, 2011 at 4:30 PM, Manmeet Singh wrote: >> >> Simple Dp >> >> On Mon, Apr 4, 2011 at 3:33 PM, Munish Goyal >> wrote:

Re: [algogeeks] Dp problem

then please share wid me yaar thanks in advance On Mon, Apr 4, 2011 at 4:30 PM, Manmeet Singh wrote: > Simple Dp > > > On Mon, Apr 4, 2011 at 3:33 PM, Munish Goyal wrote: > >> I think we can do it this way. >> >> Sum(all boards length) / K = A ( tentative avg. lenght to be painted by >> each pai

Re: [algogeeks] Dp problem

Simple Dp On Mon, Apr 4, 2011 at 3:33 PM, Munish Goyal wrote: > I think we can do it this way. > > Sum(all boards length) / K = A ( tentative avg. lenght to be painted by > each painter) > > Now start from B1, and keep going further till Bi, till Sum(B1-Bi) is less > than A. So this goes to pain

Re: [algogeeks] Dp problem

I think we can do it this way. Sum(all boards length) / K = A ( tentative avg. lenght to be painted by each painter) Now start from B1, and keep going further till Bi, till Sum(B1-Bi) is less than A. So this goes to painter P1. Same way for P2, start from i+1 till j. Condition: If i+1 itself i

Re: [algogeeks] Dp problem

like u hav boards of length of length 7 2 6 9 4 and u hav 3 painters who can work ||ly so now one way to distribute is (7 )(2 6 9) (4) so time in ths case is 17 suppose we do (7 2)(6)(9 4) time in ths case is 13 or i can do (7 2)(6 9 )(4) time in ths case is 15 i m takin 1 unit time to paint one

Re: [algogeeks] Dp problem

I didnt quite get this problem. Sample case? On 4/4/11, rajat ahuja wrote: > You have to paint N boards of length {B1, B2, B3… BN}. There are K painters > available and you are also given how much time a painter takes to paint 1 > unit of board. You have to get this job done as soon as possible u

Re: [algogeeks] Dp problem

i think this problem can be solved by binary search correct me if i m wrong On Mon, Apr 4, 2011 at 2:36 PM, rajat ahuja wrote: > You have to paint N boards of length {B1, B2, B3… BN}. There are K painters > available and you are also given how much time a painter takes to paint 1 > unit of board.

[algogeeks] Dp problem

You have to paint N boards of length {B1, B2, B3… BN}. There are K painters available and you are also given how much time a painter takes to paint 1 unit of board. You have to get this job done as soon as possible under the constraints that any painter will only paint continuous sections of board,

Re: [algogeeks] DP sorting

Hey Samba, Check this solution dp[i][j]= cost required to get the sorted sequence from index i to index j dp[i][j]= min(dp[i+1][j] + (i-j)*indexof(i) in the sequence ,dp[i][j-1] + (i-j) *indexof(j) insequence) Since the current state depends on only previous 2 states so you can optimize space to

[algogeeks] DP sorting

Hey guys help me solve the following DP problem: An N-element permutation is an N-element sequence of distinct numbers from the set {1, 2, ...,n}. For example the sequence 2,1,4,5,3 is a 5-element permutation. P is an N-element permutation. Your task is to sort P in ascending order. But because it

Re: [algogeeks] dp

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

Re: [algogeeks] dp

@Shubam: i ll do the else part rather.. :) and nice reply..;-);p -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubsc

Re: [algogeeks] dp

@ Shubham : Well Said :) :) On Fri, Feb 4, 2011 at 8:01 PM, shubham singh wrote: > if (u r calling dp of spoj as basic) > { > i would say u are a champ already ; > } > else > { > do practise more on spoj > > } > > -- > You received this message because you are subscribed to the Google Groups > "A

Re: [algogeeks] dp

if (u r calling dp of spoj as basic) { i would say u are a champ already ; } else { do practise more on spoj } -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe fro

[algogeeks] dp

hi all, can you all help to learn dp.. i hav done some basic dp in spoj... -- balaji ;-) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from th

[algogeeks] DP Problem: minimum Cost

You have different bundles of balls, which have different number of balls and different price tags. You have unlimited supplies of each of these bundles. Now if I want to get x number of balls, how should I choose bundles which cost me minimum. I am just looking for cost to be minimum, doesn't matt

Re: [algogeeks] DP problem

Hey Amir, Can u please throw some more light on this. I am not able to find a good solution for subset sum problem as well. Regards, Akash Agrawal http://tech-queries.blogspot.com/ On Fri, Dec 17, 2010 at 7:29 PM, Amir hossein Shahriari < amir.hossein.shahri...@gmail.com> wrote: > sort jewelri

Re: [algogeeks] DP problem

sort jewelries in decreasing order and then the problem can be solved in a way similar to subset sum problem On Mon, Dec 13, 2010 at 7:40 PM, Akash Agrawal wrote: > You have been given a list of jewelry items that must be split amongst two > people: Frank and Bob. Frank likes very expensive jewel

[algogeeks] DP problem

You have been given a list of jewelry items that must be split amongst two people: Frank and Bob. Frank likes very expensive jewelry. Bob doesn't care how expensive the jewelry is, as long as he gets a lot of jewelry. Based on these criteria you have devised the following policy: 1) Each piece of j

[algogeeks] DP problem

Counting Boolean Parenthesizations. You are given a boolean expression consisting of a string of the symbols 'true', 'false', 'and', 'or', and 'xor'. Count the number of ways to parenthesize the expression such that it will evaluate to true. For example,

Re: [algogeeks] DP

Only from either of the two ends. On Thu, Oct 7, 2010 at 6:05 PM, sharad kumar wrote: > is he allowed to pick only from end?? > > > > On Fri, Oct 8, 2010 at 5:44 AM, Anand wrote: > >> Given a row of notes (with specified values), two players play a game. At >> each turn, any player can pick a no

Re: [algogeeks] DP

is he allowed to pick only from end?? On Fri, Oct 8, 2010 at 5:44 AM, Anand wrote: > Given a row of notes (with specified values), two players play a game. At > each turn, any player can pick a note from any of the two ends. How will the > first player maximize his score? Both players will pla

[algogeeks] DP

Given a row of notes (with specified values), two players play a game. At each turn, any player can pick a note from any of the two ends. How will the first player maximize his score? Both players will play optimally. -- You received this message because you are subscribed to the Google Groups "

[algogeeks] DP problem

Algorithm for finding out the longest palindrome in a given string using dynamic programming --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@go