Re: [algogeeks] Dynamic programming problem
please run algo on rough , here is the basic idea : bcoz we are allowed to use same coin n number of times to form the given sum. so for eg example given coin is 1 rs and S=10; s[10] = 1 ,after 1st iteration , this mean that we can use 1 Rs coin to form Rs 10 ( adding 1 Rs *10 = 10) hence we found 1 way. llly for other coins others. On Fri, Dec 16, 2011 at 11:25 AM, sangeeta goyal wrote: > give explaination > > > > On Fri, Dec 16, 2011 at 11:14 AM, atul anand wrote: > >> use dynamic programming to solve this problem :- >> >> here is the algo:- >> >> result[S]; >> result[0]=1; >> index; >> for i=0 to len(coins[]) >> >> c=coins[i]; >> >> for k=c to S >>index=k-c; >>result[k]= result[k] + result[index]; >> >>end >> >> end >> >> print result[S]; >> >> >> On Fri, Dec 16, 2011 at 10:52 AM, Sangeeta wrote: >> >>> Given a list of N coins, their values (V1, V2, ... , VN), and the >>> total sum S. Find the minimum number of coins the sum of which is S >>> (we can use as many coins of one type as we want), or report that it's >>> not possible to select coins in such a way that they sum up to S. >>> >>> For a better understanding let's take this example: >>> Given coins with values 1, 3, and 5. >>> And the sum S is set to be 11. >>> >>> -- >>> 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 group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> -- >> 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 group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > 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 group at > http://groups.google.com/group/algogeeks?hl=en. > -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic programming problem
give explaination On Fri, Dec 16, 2011 at 11:14 AM, atul anand wrote: > use dynamic programming to solve this problem :- > > here is the algo:- > > result[S]; > result[0]=1; > index; > for i=0 to len(coins[]) > > c=coins[i]; > > for k=c to S >index=k-c; >result[k]= result[k] + result[index]; > >end > > end > > print result[S]; > > > On Fri, Dec 16, 2011 at 10:52 AM, Sangeeta wrote: > >> Given a list of N coins, their values (V1, V2, ... , VN), and the >> total sum S. Find the minimum number of coins the sum of which is S >> (we can use as many coins of one type as we want), or report that it's >> not possible to select coins in such a way that they sum up to S. >> >> For a better understanding let's take this example: >> Given coins with values 1, 3, and 5. >> And the sum S is set to be 11. >> >> -- >> 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 group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > 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 group at > http://groups.google.com/group/algogeeks?hl=en. > -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic programming problem
use dynamic programming to solve this problem :- here is the algo:- result[S]; result[0]=1; index; for i=0 to len(coins[]) c=coins[i]; for k=c to S index=k-c; result[k]= result[k] + result[index]; end end print result[S]; On Fri, Dec 16, 2011 at 10:52 AM, Sangeeta wrote: > Given a list of N coins, their values (V1, V2, ... , VN), and the > total sum S. Find the minimum number of coins the sum of which is S > (we can use as many coins of one type as we want), or report that it's > not possible to select coins in such a way that they sum up to S. > > For a better understanding let's take this example: > Given coins with values 1, 3, and 5. > And the sum S is set to be 11. > > -- > 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 group at > http://groups.google.com/group/algogeeks?hl=en. > > -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic programming question
i thnk it can be done using dynamic programming.. let the array b 25 3 25 1 10 2 5 now at at every point in the matrix..there can be two ways..to reach that point..either from left..or from right.. for example to reach at the center of the above matrix..we can come from 2->5->5 or 2->2->5..and can select the path that give max apples..similarly..we can calculate this..for every point in the 2D array the above matrix can be transformed into maximum apples at every point 2 7 10 4 12 13 14 1621 for top most row and left most column..we only add..the previous value..(because we dont have second direction) for arr(1,1) we calculate the max..that is from 7 and 4..and add it to the center value..to get 12 for arr(1,2) we calculate the max ..that if rom 12 and 10 and add it to arr(1,2) to get ..13.. this is how..we can do for..arr(2,1) and arr(2,2)... this is what we can do.. correct me if am wrong..i am naive solution provider On Tue, Dec 13, 2011 at 4:14 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 down or right. > Now if we can start any where in the matrix and have to reach anywhere > on the right(reach n column). We can either up, down, right(but not left). > We have to collect maximum apples from a given location. > I am trying to solve problem. solution for the first one is given at > http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg . > What data structure would be suitable for the second problem and will > dynamic programming work. > > > Thanks in advance. > Azhar. > > > -- > 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 group at > http://groups.google.com/group/algogeeks?hl=en. > -- *Dheeraj Sharma* -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming problem
This is a recently discussed problem in this group. Refer to subset sum problem. http://en.wikipedia.org/wiki/Subset_sum_problem On Sun, Jul 3, 2011 at 6:34 AM, Edmon wrote: > I need a help with this dynamic programming problem please. > It is from the entrance exam practice problem set: > > Given an integer sequence x_1 ... x_n is there a nonempty sub > sequences > which sums to zero? > > Describe - no code necessary - a dynamic programming solution based on > the predicate: > > "A nonempty sub sequence of x_1 ... x_n has sum s" > > I think that solution should be built on the > recursive backtracking function that selects a min > from these subsequences choices, but I think I am missing lots of > details > here. > > Any assistance is appreciated. Thank you in advance. > > -- > 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 group at > http://groups.google.com/group/algogeeks?hl=en. > > -- --Navneet -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming
dp[i] - profit from the opening restaurants up to the i-th position. dp[i] = max(dp[i - 1], p[i] + max[dp[j], j <= A and distance between i and j at least k]). Segment trees are helpful to find maximum profir for the positions to th elft of the current. So we use tree of maximums. To satisfy the second property (distance at least k), for the current position you should determine position A, where m[i] - m[A] >= k, this can be done using binary serach (lower_bound in C++). -- 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 at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming
Can you elaborate how to put segment tree into picture On Wed, Jan 5, 2011 at 2:57 PM, juver++ wrote: > Right. It can be solved simply in O(n^2). To optimize use segment trees. > > -- > 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 at > http://groups.google.com/group/algogeeks?hl=en. > -- 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 at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming
Right. It can be solved simply in O(n^2). To optimize use segment trees. -- 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 at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming
1-D simple dp with state current index you are at On Wed, Jan 5, 2011 at 7:41 AM, Akash Agrawal wrote: > didn't get the question correct... > Can u cite an example... > > Regards, > Akash Agrawal > http://tech-queries.blogspot.com/ > > > > On Wed, Jan 5, 2011 at 12:36 AM, Decipher wrote: > >> Yuckdonald's is considering opening a series of restaurants along >> Quaint Valley Highway (QVH).The n possible locations are along a >> straight line, and the distances of these locations from the start of >> QVH are, in miles and in increasing order,m1;m2; : : : ;mn. The >> constraints are as follows: >> 1)At each location,Yuckdonald's may open at most one restaurant.The >> expected profi t from opening a restaurant at location i is pi, where >> pi > 0 and i = 1; 2; : : : ; n. >> 2)Any two restaurants should be at least k miles apart, where k is a >> positive integer. >> Give an effi cient algorithm to compute the maximum expected total >> pro fit subject to the given >> constraints. >> >> -- >> 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 at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > 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 at > http://groups.google.com/group/algogeeks?hl=en. > -- 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 at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming
didn't get the question correct... Can u cite an example... Regards, Akash Agrawal http://tech-queries.blogspot.com/ On Wed, Jan 5, 2011 at 12:36 AM, Decipher wrote: > Yuckdonald's is considering opening a series of restaurants along > Quaint Valley Highway (QVH).The n possible locations are along a > straight line, and the distances of these locations from the start of > QVH are, in miles and in increasing order,m1;m2; : : : ;mn. The > constraints are as follows: > 1)At each location,Yuckdonald's may open at most one restaurant.The > expected profi t from opening a restaurant at location i is pi, where > pi > 0 and i = 1; 2; : : : ; n. > 2)Any two restaurants should be at least k miles apart, where k is a > positive integer. > Give an effi cient algorithm to compute the maximum expected total > pro fit subject to the given > constraints. > > -- > 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 at > http://groups.google.com/group/algogeeks?hl=en. > > -- 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 at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming Problem on Strings
@ankur: dp[i][j] number of (prefix) strings that have i As and j Bs is: dp[i-1][j] number of (prefix) strings that have i-1 As and j Bs appended by "A" + dp[i][j-1] number of (prefix) strings that have i As and j-1 Bs appended by "B" @ashish: wikipedia has some nice proofs for catalan number formula: en.wikipedia.org/wiki/Catalan_number -- 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 at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming Problem on Strings
Let the problem be represented as f(i,j) for i A's and jB's.
Amir represented it correctly as: f(i,j) = f(i,j-1) + f(j,i-1)
Lets try another representation:
Let t(i,j) is the number of strings of length i+j with iA's and jB's in any
order.
Hence, t(i, j) = (i+j)Ci
Now some valid strings for our problem would be:
"A""A""B...ntimes", where is a string counted as valid
by t(n-2,0)
Or "A""A""B...n-1times", is a string counted as valid
by t(n-2,1)
Hence,
*f(n,n) = t(n-2,0) + t(n-2,1) + t(n-2,2)+...+t(n-2,n-1)*
*
*
Adding these terms should give you the answer.
Hope this helps
Cheers
Nikhil Jindal
Delhi College of Engineering
On Thu, Aug 5, 2010 at 9:56 PM, Ashish Goel wrote:
> can u explain how is this number reached at?
>
> (2n)!/((n+1)!(n!))
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
> On Thu, Aug 5, 2010 at 12:53 PM, umesh kewat wrote:
>
>> Calculate the number of string can be formed by this formula in one
>> statement..
>>
>> for cross check the result is
>>
>> 2N!/((N+1)! * N!) where is number of A or B in string
>>
>>
>>
>>
>> On Thu, Aug 5, 2010 at 8:54 AM, Ashish Goel wrote:
>>
>>>
void dyckWords(int index, int open, int close)
{
static int dyck=0;
if (index == 2 *n)
{
printf("%s\n", out);
return ;
}
out[index] = '('; //or A
if ((open + 1) <= n && open >= close)
{
dyckWords(index + 1, open + 1, close);
}
out[index] = ')';//or B
if ((close + 1) <= n && open >= close)
{
dyckWords(index + 1, open, close + 1);
}
}
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Mon, Jul 19, 2010 at 1:25 AM, Amir hossein Shahriari <
amir.hossein.shahri...@gmail.com> wrote:
> @ashish: AAA is the prefix of the string and it is valid as a prefix
> and it's only used for strings with length >= 6 (where it is a valid
> prefix)
> actually only dp[i][j] where i==j counts the number of such strings and
> otherwise there is no string where i!=j and it that case dp[i][j] counts
> the
> number of valid prefixes for string
> dp[0][0]=1 does satisfy both properties because 0=0 so the number of As
> & Bs are the same
> the logic behind n/2 is that if the length of the string is n this
> means that it has n/2 As and n/2 Bs (n must be even)
> the dp for n=4 doesn't look like that! this is how it looks (i just
> compiled the code and checked values of dp):
> 1 0 0
> 1 1 0
> 1 2 2
> so dp[2][2]=2 which means the number of strings with 2 As and 2 Bs is 2
>
>
> --
> 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 at
> http://groups.google.com/group/algogeeks?hl=en.
>
>>> --
>>> 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 at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> Thanks & Regards
>>
>> Umesh kewat
>>
>>
>>
>> --
>> 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 at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> 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 at
> http://groups.google.com/group/algogeeks?hl=en.
>
Please access the attached hyperlink for an important electronic communications
disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
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 at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming Problem on Strings
@Amir: how you have found this relation dp[i][j]=dp[i-1][j]+dp[i][j-1] i am not able to understand it. Plz explain it. thanx On Tue, Jul 13, 2010 at 3:39 AM, Amir hossein Shahriari < amir.hossein.shahri...@gmail.com> wrote: > dp[i][j] is the number of strings that have i As and j Bs > > > dp[0][0]=1; // s="" > for (i=1;i<=n/2;i++) > > dp[i][0]=1; // s="AAA..." > > for (i=1;i<=n/2;i++) > > dp[0][i]=0; // the 2nd constraint > > for (i=1;i<=n/2;i++) > > for (j=1;j<=n/2;j++) > > if (j>i) > > dp[i][j]=0; // the 2nd constraint > > else > > dp[i][j]=dp[i-1][j]+dp[i][j-1]; > > > dp[n/2][n/2] would be the result > > -- > 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 at > http://groups.google.com/group/algogeeks?hl=en. > -- 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 at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming Problem on Strings
can u explain how is this number reached at?
(2n)!/((n+1)!(n!))
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Thu, Aug 5, 2010 at 12:53 PM, umesh kewat wrote:
> Calculate the number of string can be formed by this formula in one
> statement..
>
> for cross check the result is
>
> 2N!/((N+1)! * N!) where is number of A or B in string
>
>
>
>
> On Thu, Aug 5, 2010 at 8:54 AM, Ashish Goel wrote:
>
>>
>>>
>>> void dyckWords(int index, int open, int close)
>>> {
>>> static int dyck=0;
>>> if (index == 2 *n)
>>> {
>>> printf("%s\n", out);
>>> return ;
>>> }
>>>
>>> out[index] = '('; //or A
>>> if ((open + 1) <= n && open >= close)
>>>
>>>
>>>
>>>
>>>
>>> {
>>> dyckWords(index + 1, open + 1, close);
>>> }
>>> out[index] = ')';//or B
>>>
>>> if ((close + 1) <= n && open >= close)
>>> {
>>> dyckWords(index + 1, open, close + 1);
>>>
>>>
>>> }
>>> }
>>>
>>> Best Regards
>>> Ashish Goel
>>> "Think positive and find fuel in failure"
>>> +919985813081
>>> +919966006652
>>>
>>>
>>> On Mon, Jul 19, 2010 at 1:25 AM, Amir hossein Shahriari <
>>> amir.hossein.shahri...@gmail.com> wrote:
>>>
@ashish: AAA is the prefix of the string and it is valid as a prefix and
it's only used for strings with length >= 6 (where it is a valid prefix)
actually only dp[i][j] where i==j counts the number of such strings and
otherwise there is no string where i!=j and it that case dp[i][j] counts
the
number of valid prefixes for string
dp[0][0]=1 does satisfy both properties because 0=0 so the number of As
& Bs are the same
the logic behind n/2 is that if the length of the string is n this means
that it has n/2 As and n/2 Bs (n must be even)
the dp for n=4 doesn't look like that! this is how it looks (i just
compiled the code and checked values of dp):
1 0 0
1 1 0
1 2 2
so dp[2][2]=2 which means the number of strings with 2 As and 2 Bs is 2
--
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 at
http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>> --
>> 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 at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Thanks & Regards
>
> Umesh kewat
>
>
>
> --
> 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 at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
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 at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming Problem on Strings
Calculate the number of string can be formed by this formula in one
statement..
for cross check the result is
2N!/((N+1)! * N!) where is number of A or B in string
On Thu, Aug 5, 2010 at 8:54 AM, Ashish Goel wrote:
>
>>
>> void dyckWords(int index, int open, int close)
>> {
>> static int dyck=0;
>> if (index == 2 *n)
>> {
>> printf("%s\n", out);
>> return ;
>> }
>>
>> out[index] = '('; //or A
>> if ((open + 1) <= n && open >= close)
>>
>>
>>
>> {
>> dyckWords(index + 1, open + 1, close);
>> }
>> out[index] = ')';//or B
>>
>> if ((close + 1) <= n && open >= close)
>> {
>> dyckWords(index + 1, open, close + 1);
>> }
>> }
>>
>> Best Regards
>> Ashish Goel
>> "Think positive and find fuel in failure"
>> +919985813081
>> +919966006652
>>
>>
>> On Mon, Jul 19, 2010 at 1:25 AM, Amir hossein Shahriari <
>> amir.hossein.shahri...@gmail.com> wrote:
>>
>>> @ashish: AAA is the prefix of the string and it is valid as a prefix and
>>> it's only used for strings with length >= 6 (where it is a valid prefix)
>>> actually only dp[i][j] where i==j counts the number of such strings and
>>> otherwise there is no string where i!=j and it that case dp[i][j] counts the
>>> number of valid prefixes for string
>>> dp[0][0]=1 does satisfy both properties because 0=0 so the number of As &
>>> Bs are the same
>>> the logic behind n/2 is that if the length of the string is n this means
>>> that it has n/2 As and n/2 Bs (n must be even)
>>> the dp for n=4 doesn't look like that! this is how it looks (i just
>>> compiled the code and checked values of dp):
>>> 1 0 0
>>> 1 1 0
>>> 1 2 2
>>> so dp[2][2]=2 which means the number of strings with 2 As and 2 Bs is 2
>>>
>>>
>>> --
>>> 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 at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
> --
> 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 at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Thanks & Regards
Umesh kewat
--
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 at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming Problem on Strings
>
>
> void dyckWords(int index, int open, int close)
> {
> static int dyck=0;
> if (index == 2 *n)
> {
> printf("%s\n", out);
> return ;
> }
>
> out[index] = '('; //or A
> if ((open + 1) <= n && open >= close)
>
>
> {
> dyckWords(index + 1, open + 1, close);
> }
> out[index] = ')';//or B
> if ((close + 1) <= n && open >= close)
> {
> dyckWords(index + 1, open, close + 1);
> }
> }
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
> On Mon, Jul 19, 2010 at 1:25 AM, Amir hossein Shahriari <
> amir.hossein.shahri...@gmail.com> wrote:
>
>> @ashish: AAA is the prefix of the string and it is valid as a prefix and
>> it's only used for strings with length >= 6 (where it is a valid prefix)
>> actually only dp[i][j] where i==j counts the number of such strings and
>> otherwise there is no string where i!=j and it that case dp[i][j] counts the
>> number of valid prefixes for string
>> dp[0][0]=1 does satisfy both properties because 0=0 so the number of As &
>> Bs are the same
>> the logic behind n/2 is that if the length of the string is n this means
>> that it has n/2 As and n/2 Bs (n must be even)
>> the dp for n=4 doesn't look like that! this is how it looks (i just
>> compiled the code and checked values of dp):
>> 1 0 0
>> 1 1 0
>> 1 2 2
>> so dp[2][2]=2 which means the number of strings with 2 As and 2 Bs is 2
>>
>>
>> --
>> 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 at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
--
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 at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming Problem on Strings
void dyckWords(int index, int open, int close)
{
static int dyck=0;
if (index == 2 *n)
{
printf("%s\n", out);
return ;
}
out[index] = '('; //or A
if ((open + 1) <= n && open >= close)
{
dyckWords(index + 1, open + 1, close);
}
out[level] = ')';//or B
if ((close + 1) <= n && open >= close)
{
dyckWords(index + 1, open, close + 1);
}
}
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Mon, Jul 19, 2010 at 1:25 AM, Amir hossein Shahriari <
amir.hossein.shahri...@gmail.com> wrote:
> @ashish: AAA is the prefix of the string and it is valid as a prefix and
> it's only used for strings with length >= 6 (where it is a valid prefix)
> actually only dp[i][j] where i==j counts the number of such strings and
> otherwise there is no string where i!=j and it that case dp[i][j] counts the
> number of valid prefixes for string
> dp[0][0]=1 does satisfy both properties because 0=0 so the number of As &
> Bs are the same
> the logic behind n/2 is that if the length of the string is n this means
> that it has n/2 As and n/2 Bs (n must be even)
> the dp for n=4 doesn't look like that! this is how it looks (i just
> compiled the code and checked values of dp):
> 1 0 0
> 1 1 0
> 1 2 2
> so dp[2][2]=2 which means the number of strings with 2 As and 2 Bs is 2
>
>
> --
> 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 at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
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 at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming Problem on Strings
@ashish: AAA is the prefix of the string and it is valid as a prefix and it's only used for strings with length >= 6 (where it is a valid prefix) actually only dp[i][j] where i==j counts the number of such strings and otherwise there is no string where i!=j and it that case dp[i][j] counts the number of valid prefixes for string dp[0][0]=1 does satisfy both properties because 0=0 so the number of As & Bs are the same the logic behind n/2 is that if the length of the string is n this means that it has n/2 As and n/2 Bs (n must be even) the dp for n=4 doesn't look like that! this is how it looks (i just compiled the code and checked values of dp): 1 0 0 1 1 0 1 2 2 so dp[2][2]=2 which means the number of strings with 2 As and 2 Bs is 2 -- 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 at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming Problem on Strings
It can be solved with trie On Sun, Jul 18, 2010 at 10:28 AM, Ashish Goel wrote: > dp[i][0]=1 implies that there is 1 combination which will ensure that the > number of A's and B's is same in the string. > eg AAA is not a valid string > > dp[0][0]=1 doesnot satisfy property 1 either > > with this algo and tring length 4(possible strings AABB, ABAB) > > > a[i][j] will look like > > 1 1 1 > 0 1 0 > 0 1 1 > > > also, donot understand the logic why n/2 is chosen? > > > > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > > > > On Tue, Jul 13, 2010 at 3:39 AM, Amir hossein Shahriari < > amir.hossein.shahri...@gmail.com> wrote: > >> dp[i][j] is the number of strings that have i As and j Bs >> >> >> dp[0][0]=1; // s="" >> for (i=1;i<=n/2;i++) >> >> dp[i][0]=1; // s="AAA..." >> >> for (i=1;i<=n/2;i++) >> >> dp[0][i]=0; // the 2nd constraint >> >> for (i=1;i<=n/2;i++) >> >> for (j=1;j<=n/2;j++) >> >> if (j>i) >> >> dp[i][j]=0; // the 2nd constraint >> >> else >> >> dp[i][j]=dp[i-1][j]+dp[i][j-1]; >> >> >> dp[n/2][n/2] would be the result >> >> -- >> 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 at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > 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 at > http://groups.google.com/group/algogeeks?hl=en. > -- Rahul singhal RnD Engineer Tejas Networks Mobile- 09916969422 -- 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 at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming Problem on Strings
dp[i][0]=1 implies that there is 1 combination which will ensure that the number of A's and B's is same in the string. eg AAA is not a valid string dp[0][0]=1 doesnot satisfy property 1 either with this algo and tring length 4(possible strings AABB, ABAB) a[i][j] will look like 1 1 1 0 1 0 0 1 1 also, donot understand the logic why n/2 is chosen? Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Tue, Jul 13, 2010 at 3:39 AM, Amir hossein Shahriari < amir.hossein.shahri...@gmail.com> wrote: > dp[i][j] is the number of strings that have i As and j Bs > > > dp[0][0]=1; // s="" > for (i=1;i<=n/2;i++) > > dp[i][0]=1; // s="AAA..." > > for (i=1;i<=n/2;i++) > > dp[0][i]=0; // the 2nd constraint > > for (i=1;i<=n/2;i++) > > for (j=1;j<=n/2;j++) > > if (j>i) > > dp[i][j]=0; // the 2nd constraint > > else > > dp[i][j]=dp[i-1][j]+dp[i][j-1]; > > > dp[n/2][n/2] would be the result > > -- > 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 at > http://groups.google.com/group/algogeeks?hl=en. > -- 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 at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming Problem on Strings
that would be the Catlan number... Anil On Thu, Jul 15, 2010 at 11:41 PM, mohit ranjan wrote: > @Ajeet > * > Google "Dyck words*" > > > Mohit > > > > On Mon, Jul 12, 2010 at 1:43 PM, aejeet wrote: > >> A string can contain only the characters A and B. >> >> The string formation must follow the following rules >> 1. The number of occurrences of A and that of B must be equal in the >> string >> 2. For any prefix of string, the number occurrences of A must be >> greater than or equal to the number of occurrences of B. >> >> Now given an integer of length N, find the number of possible string >> formations adhering the rules above. >> >> -- >> 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 at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > 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 at > http://groups.google.com/group/algogeeks?hl=en. > -- 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 at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming Problem on Strings
@Ajeet * Google "Dyck words*" Mohit On Mon, Jul 12, 2010 at 1:43 PM, aejeet wrote: > A string can contain only the characters A and B. > > The string formation must follow the following rules > 1. The number of occurrences of A and that of B must be equal in the > string > 2. For any prefix of string, the number occurrences of A must be > greater than or equal to the number of occurrences of B. > > Now given an integer of length N, find the number of possible string > formations adhering the rules above. > > -- > 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 at > http://groups.google.com/group/algogeeks?hl=en. > > -- 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 at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming Problem on Strings
dp[i][j] is the number of strings that have i As and j Bs dp[0][0]=1; // s="" for (i=1;i<=n/2;i++) dp[i][0]=1; // s="AAA..." for (i=1;i<=n/2;i++) dp[0][i]=0; // the 2nd constraint for (i=1;i<=n/2;i++) for (j=1;j<=n/2;j++) if (j>i) dp[i][j]=0; // the 2nd constraint else dp[i][j]=dp[i-1][j]+dp[i][j-1]; dp[n/2][n/2] would be the result -- 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 at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming
Hi Sharad, Yeah its some what similar to the coin exchange problem. Thanks. On Mon, Dec 7, 2009 at 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. >> >> Let fi(x) = i*(1+log x). Describe a dynamic programming algorithm to >> input 2 integers x and m and determine how to break x into m integers >> x1, x2, ..., xm such that f1(x1)+f2(x2)+...+fm(xm) is the largest >> among all possible ways of breaking x into m integers. Note that x≥m >> and xi≥1 for all 1≤i≤m >> >> 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 at >> http://groups.google.com/group/algogeeks?hl=en. >> >> >> > -- > 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 at > http://groups.google.com/group/algogeeks?hl=en. > -- 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 at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming
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. > > Let fi(x) = i*(1+log x). Describe a dynamic programming algorithm to > input 2 integers x and m and determine how to break x into m integers > x1, x2, ..., xm such that f1(x1)+f2(x2)+...+fm(xm) is the largest > among all possible ways of breaking x into m integers. Note that x≥m > and xi≥1 for all 1≤i≤m > > 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 at > http://groups.google.com/group/algogeeks?hl=en. > > > -- 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 at http://groups.google.com/group/algogeeks?hl=en.
