Re: [algogeeks] Re: a google question
@Gene I think there is some mistake in this programe. when the input is : a[ ] = {30,25,19,16} b[ ] = {20,18,14,10} the right result should be 30+20, 30+18, 25+20,30+14 but the output of your programe is 30+20,30+18,25+20,25+18 Best Regards! 2010/5/4 Gene gene.ress...@gmail.com I propose this solution (it's C89): #include stdio.h //int a[] = { 8, 7, 4, 3, 2, 1, 1, 1, 1, 1 }; //int b[] = { 34, 23, 21, 19, 15, 13, 11, 8, 4, 2 }; int a[] = { 6, 5, 4, 3, 2, 1 }; int b[] = { 9, 8, 6, 5, 3, 2 }; void find_pairs(int *a, int *b, int n) { int iamax[100], ibmax[100], i, ia, ib; for (i = 0; i n; i++) iamax[i] = ibmax[i] = -1; ia = ib = 0; for (i = 0; i n; i++) { printf((%d,%d)\n, a[ia], b[ib]); if (a[ia + 1] + b[ibmax[ia + 1] + 1] b[ib + 1] + a[iamax[ib + 1] + 1]) ib = ++ibmax[++ia]; else ia = ++iamax[++ib]; } } int main(void) { find_pairs(a, b, sizeof a / sizeof a[0]); return 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.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] a google question
i think ,you can use the idea of merg (merg sort) --- On Mon, 7/19/10, manish bhatia mb_mani...@yahoo.com wrote: From: manish bhatia mb_mani...@yahoo.com Subject: Re: [algogeeks] a google question To: algogeeks@googlegroups.com Date: Monday, July 19, 2010, 5:03 PM Given two sorted postive integer arrays A(n) and B(n) (W.L.O.G, let's say they are decreasingly sorted), we define a set S = {(a,b) | a \in A and b \in B}. Obviously there are n^2 elements in S. The value of such a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs from S with largest values. The tricky part is that we need an O(n) algorithm. manish... From: Ashish Goel ashg...@gmail.com To: algogeeks@googlegroups.com Sent: Sun, 18 July, 2010 6:31:08 PM Subject: Re: [algogeeks] a google question question please... Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Fri, Jul 16, 2010 at 4:43 PM, manish bhatia mb_mani...@yahoo.com wrote: It doesn't work A = 92 87 81 72 70 61 53 22 18 17 B = 79 78 74 68 64 62 57 34 29 24 C (GOLD) = 171 170 166 166 165 161 160 160 159 156 D (TEST) = 171 170 166 166 165 159 155 155 146 145 Result: FAILED! manish... From: Jitendra Kushwaha jitendra.th...@gmail.com To: algogeeks@googlegroups.com Sent: Sun, 2 May, 2010 9:13:14 PM Subject: Re: [algogeeks] a google question Here is a solution of O(n) , taking 4 pointers 2 for each array #include cstdio #includeiostream using namespace std; #define N 10 int main(void) { int arr1[N] = {8,7,4,3,2,1,1,1,1,1}; int arr2[N] = {34,23,21,19,15,13,11,8,4,2}; int *p11,*p12,*p21,*p22; p11 = p12 = arr1; p21 = p22 = arr2; int f1; f1 = 0; for(int i=0;iN;i++) { int ans=0; int a,b,c,d; a = *p11 + *p21; b = *p11 + *p22; c = *p21 + *p12; d = *(p11+1) + *(p21+1); //printf(a=%d b=%d c=%d d=%d\n,a,b,c,d); //debug if(f1==0) ans = a , p12++ , p22++ , f1=1; else if(b = c b = d ) ans = b , p22++ ; else if(c = b c = d ) ans = c , p12++ ; else ans = d , p11++ , p21++ ,printf(4 ); printf(%d\n,ans); } } Regards Jitendra Kushwaha Undergradute Student Computer Science Eng. 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 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. -- 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.
[algogeeks] Re: Adobe Puzzle
Nice way to put it erappy, here is another way. A block of length L can be place at the corner of the outer square such that it makes a triangle so that two sides of the triangle is the corner sides of the square and the base of the triangle is the block. Now, on this block another block can be placed to reach the corner of the inner square. On Jul 19, 10:08 am, erappy era...@gmail.com wrote: Use the block of size L, use the diagonal of the block (diagonal would be definitely L ) to fit in between two square islands. Thanks, On Sun, Jul 18, 2010 at 11:38 PM, amit amitjaspal...@gmail.com wrote: Puzzle, A square Island surrounded by bigger square, and in between there is infinite depth water. The distance between them is L. The wooden blocks of L are given. The L length block can't be placed in between to cross it, as it will fall in water (just fitting). How would you cross using these L length blocks. -- 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] Boxes!!!
step : 1. Sorting LBH in decreasing order first on L than on B and than on H . 2. Now find longest decreasing sub-sequence of array of structures(LBH) . correct me if I m wrong !!! On Sun, Jul 18, 2010 at 11:44 PM, amit amitjaspal...@gmail.com wrote: Given a lot of cuboid boxes with different length, breadth and height. We need to find the maximum subset which can fit into each other. For example: If Box 1 has LBH as 7 8 9 If Box 2 has LBH as 5 6 8 If Box 3 has LBH as 5 8 7 If Box 4 has LBH as 4 4 4 then answer is 1,2,4 A box can fit into another only and only if all dimensions of that is less than the bigger box.Rotation of boxes is not possible. -- 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. -- siddharth shankar -- 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: Road crossing algorithm
Can you write some pseudo-code for your algorithm? I think it has a problem with how-much-time-to-wait-in-one-lane. For example, there are two lanes and cars are coming as: lane1 10 5 4 3 2 1 lane2 9 6 3 So, the times when the car is not there will be: lane1 9 8 7 6 lane2 10 8 7 5 4 2 1 So, jumping to a lane is possible only when staying in that lane is allowed till the next jump. When that is put in, the algorithm essentially becomes the same as the recursive algo given above. On Jul 16, 6:04 pm, Ashish Goel ashg...@gmail.com wrote: it does have, have been thinking on this since y'day and it will still work with a little modification in case there is a path, it indeed covers move back possibilities with two adjacent lane timings2 alternatively, if frog moves back ,based on current time, only possible entries after the current time need to be looked at in the current lane Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Jul 15, 2010 at 11:47 PM, Tech Id tech.login@gmail.com wrote: Hi Ashish, Your algo does not have a chance for jump_back. This may be required for certain cases, especially when multiple cars are running on one lane. My solution was for one car on one lane, hence car_times[i] gives the car in i-th lane will take to hit the path frog is trying to cross. It should not be too difficult to put multiple cars on single lane in my algo. Actually, from a game perspective, the problem can have many parts like: speed of cars vary, frog can move sideways too instead of vertically on the road. frog can make upto m jumps etc etc. Regards Techie -- 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.
[algogeeks] Strings
Given two text strings A of length n and B of length m, you want to transform A into B with a minimum number of operations of the following types: delete a character from A, insert a character into A, or change some character in A into a new character. The minimal number of such operations required to transform A into B is called the edit distance between A and B. Solution: ci = Insertion cost cd= deletion cost cr=replacement cost. T[i][j] = Min cost to transform A[1..i] to B[1...j] http://codepad.org/y1oUtioX Is there any better solution available? -- 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: Strings
http://codepad.org/QSaNaQlH On Mon, Jul 19, 2010 at 10:29 PM, Anand anandut2...@gmail.com wrote: Given two text strings A of length n and B of length m, you want to transform A into B with a minimum number of operations of the following types: delete a character from A, insert a character into A, or change some character in A into a new character. The minimal number of such operations required to transform A into B is called the edit distance between A and B. Solution: ci = Insertion cost cd= deletion cost cr=replacement cost. T[i][j] = Min cost to transform A[1..i] to B[1...j] http://codepad.org/y1oUtioX Is there any better solution available? -- 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.