Re: [algogeeks] Re: dp problem
F[n] = number of ways to tile a 4-by-n grid G[n] = number of ways to tile a 4-by-n grid with top-right and bottom-right squares uncovered H[n] = number of ways to tile a 4-by-n grid with bottom-right 2 squares uncovered = number of ways to tile a 4-by-n grid with top-right 2 squares uncovered if n = 2, the right end of any tiling can be two vertical dominoes (F[n-1] ways) horz, horz vert (H[n-1] ways) horz, vert, horz (G[n-1] ways) vert, horz, horz (H[n-1] ways) 4 horizontal dominoes (F[n-2] ways) F[n] = F[n-1] + G[n-1] + 2*H[n-1] + F[n-2]; For G: the right end can be a vertical domino (F[n-1] ways) or two horizontal dominoes = top bottom are horz = G[n-2] G[n] = F[n-1] + G[n-2]; For H: the right end can be a vertical domino (F[n-1] ways) or two horizontal dominoes (H[n-1] ways) H[n] = F[n-1] + H[n-1]; F[0] = 1, F[1] = 1, G[0] = 0, G[1] = 1, H[0] = 0, H[1] = 1 Hope it helps !! -- 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] Re: dp problem
http://groups.google.com/group/algogeeks/browse_thread/thread/c678b320891bbaa1/1646f2fe7d2c6879?hl=enlnk=gstq=Spoj+Domino+Tiling+#1646f2fe7d2c6879 http://groups.google.com/group/algogeeks/browse_thread/thread/c678b320891bbaa1/1646f2fe7d2c6879?hl=enlnk=gstq=Spoj+Domino+Tiling+#1646f2fe7d2c6879 by traditional i mean, by dividing it into similar structure to make recurrence come into picture. @kunal any updates on the same ? On Fri, Apr 13, 2012 at 4:57 PM, UTKARSH SRIVASTAV usrivastav...@gmail.comwrote: anyone ? On Fri, Apr 13, 2012 at 12:09 PM, UTKARSH SRIVASTAV usrivastav...@gmail.com wrote: 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* -- *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. 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] Re: dp problem
that we all know we have to divide problem into smaller sub problems in dp ? but how u made those recurrences ? On Sat, Apr 14, 2012 at 8:51 PM, shady sinv...@gmail.com wrote: http://groups.google.com/group/algogeeks/browse_thread/thread/c678b320891bbaa1/1646f2fe7d2c6879?hl=enlnk=gstq=Spoj+Domino+Tiling+#1646f2fe7d2c6879 http://groups.google.com/group/algogeeks/browse_thread/thread/c678b320891bbaa1/1646f2fe7d2c6879?hl=enlnk=gstq=Spoj+Domino+Tiling+#1646f2fe7d2c6879 by traditional i mean, by dividing it into similar structure to make recurrence come into picture. @kunal any updates on the same ? On Fri, Apr 13, 2012 at 4:57 PM, UTKARSH SRIVASTAV usrivastav...@gmail.com wrote: anyone ? On Fri, Apr 13, 2012 at 12:09 PM, UTKARSH SRIVASTAV usrivastav...@gmail.com wrote: 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* -- *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. 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. -- *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. 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.
[algogeeks] Re: dp problem
anyone ? On Fri, Apr 13, 2012 at 12:09 PM, UTKARSH SRIVASTAV usrivastav...@gmail.com wrote: 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* -- *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. 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.
[algogeeks] Re: Dp problem
Here i proposed an algorithm. correct me if i am wrong !!
int main()
{
int N; //number of boards
int W; // number of workers
int smax = 0;
cin N W;
int *A = new int[N];
for(int i=0;iN;i++){
cin A[i];
smax += A[i];
}
int m = *max_element(A ,A+N);
for(int i=m;i=smax;i++){
int sum = 0;
int w = 1;
for(int j=0;jN;j++){
if(sum+A[j] = i){
sum += A[j];
}
else{
sum = A[j];
w++;
}
}
if(w=W){
cout i \n;
break;
}
}
return 0;
}
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 under the
constraints that any painter will only paint continuous sections of board,
say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.
--
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] Re: DP Problem: minimum Cost
Hi,
Can u please explain. I couldn't get what do u mean by after processing K
bundles?
I wrote following code (which is inefficient) which is goving correct result
for 140. But how to get the value 1400.
#includeiostream
using namespace std;
//#define MAX 0x7FFF
int main()
{
int weight[] = {8, 20, 70, 130};
int cost[] = {1025, 325, 475, 1050};
int ans[10];
for (int i=1; i 1; i++)
ans[i] = 21474836;
ans[0] = 0;
int i;
cout ans[1250] endl;
for (i=1; i10; i++)
{
for (int j=0; j4; j++)
{
if((i-weight[j]) = 0)
{
int cos = ans[i-weight[j]] + cost[j];
if (cos ans[i])
{
ans[i] = cos;
// cout ans[i]iendl;
}
}
}
if (i=140 ans[i] INT_MAX)
break;
}
cout ans[i] i endl;
return 0;
}
Regards,
Akash Agrawal
http://tech-queries.blogspot.com/
On Thu, Dec 30, 2010 at 6:03 PM, juver++ avpostni...@gmail.com wrote:
DP[K][N] - minimal cost choosing N balls and after processing K bundles.
--
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.comalgogeeks%2bunsubscr...@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] Re: DP Problem: minimum Cost
process bundles one by one, as for 0-1 knapsack problem. -- 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.
[algogeeks] Re: DP Problem: minimum Cost
DP[K][N] - minimal cost choosing N balls and after processing K bundles. -- 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.
[algogeeks] Re: DP problem
Refer to the original problem here: http://www.topcoder.com/stat?c=problem_statementpm=1166. And the tutorial: http://www.topcoder.com/tc?module=Staticd1=match_editorialsd2=tco03_online_rd_4 -- 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.
[algogeeks] Re: DP problem
What does arr[i+1][j-1] signify ? Can u give a pseudocode ? On Nov 28, 1:17 pm, Yingjie Xu [EMAIL PROTECTED] wrote: Using suffix tree, can be solved in O(n)... On 11/28/07, John [EMAIL PROTECTED] wrote: 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: DP problem
It means that the position arr[i][j] (read str.substr(i,j)) is a palindrome if the characters at positions i and j are equal (str.charAt(i) == str.charAt(j)) and the word without the last characters were a palindrome (arr[i-1][j-1]). This is a bottom-up approach. -- barata On Nov 28, 6:02 am, John [EMAIL PROTECTED] wrote: What does arr[i+1][j-1] signify ? Can u give a pseudocode ? On Nov 28, 1:17 pm, Yingjie Xu [EMAIL PROTECTED] wrote: Using suffix tree, can be solved in O(n)... On 11/28/07, John [EMAIL PROTECTED] wrote: 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: DP problem
suppose arr[i][j] says if string from i to j is a palindrome then arr[i][j] = (str[i]==str[j]) arr[i+1][j-1] then answer = max (abs(i-j) such that arr[i][j] =1) On Nov 28, 2007 12:49 AM, John [EMAIL PROTECTED] wrote: 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
