[algogeeks] Re: problem
what are the constraints or limits for a,b and n?? On Jun 10, 3:07 pm, payel roy smithpa...@gmail.com wrote: Find the number of fractions a/b such that- 1. *gcd(a, b) = 1* 2. *0 a/b 1* 3. *a * b = (n!) ^ (n!)* Where *n!* denotes the factorial of n and ^ denotes power, *i.e. (2!) ^ (2!) = 4*. -- 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: problem
No constraints as such! On 10 June 2012 17:19, Nachammai Lakshmanan nnlna...@gmail.com wrote: what are the constraints or limits for a,b and n?? On Jun 10, 3:07 pm, payel roy smithpa...@gmail.com wrote: Find the number of fractions a/b such that- 1. *gcd(a, b) = 1* 2. *0 a/b 1* 3. *a * b = (n!) ^ (n!)* Where *n!* denotes the factorial of n and ^ denotes power, *i.e. (2!) ^ (2!) = 4*. -- 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.
[algogeeks] Re: problem
This problem is of ACM-ICPC kanpur online round 2012. you can find the solution herehttp://www.codechef.com/ACMKAN11/problems/ARTHMNCY . On Sunday, 10 June 2012 16:37:33 UTC+5:30, payel roy wrote: Find the number of fractions a/b such that- 1. *gcd(a, b) = 1* 2. *0 a/b 1* 3. *a * b = (n!) ^ (n!)* Where *n!* denotes the factorial of n and ^ denotes power, *i.e. (2!) ^ (2!) = 4*. On Sunday, 10 June 2012 16:37:33 UTC+5:30, payel roy wrote: Find the number of fractions a/b such that- 1. *gcd(a, b) = 1* 2. *0 a/b 1* 3. *a * b = (n!) ^ (n!)* Where *n!* denotes the factorial of n and ^ denotes power, *i.e. (2!) ^ (2!) = 4*. -- 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/-/0tnSKnC7YRYJ. 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: problem
Can you please simplify the algorithm? Solution is not clear from the posted submissions !!! On 10 June 2012 20:32, KK kunalkapadi...@gmail.com wrote: This problem is of ACM-ICPC kanpur online round 2012. you can find the solution herehttp://www.codechef.com/ACMKAN11/problems/ARTHMNCY . On Sunday, 10 June 2012 16:37:33 UTC+5:30, payel roy wrote: Find the number of fractions a/b such that- 1. *gcd(a, b) = 1* 2. *0 a/b 1* 3. *a * b = (n!) ^ (n!)* Where *n!* denotes the factorial of n and ^ denotes power, *i.e. (2!) ^ (2!) = 4*. On Sunday, 10 June 2012 16:37:33 UTC+5:30, payel roy wrote: Find the number of fractions a/b such that- 1. *gcd(a, b) = 1* 2. *0 a/b 1* 3. *a * b = (n!) ^ (n!)* Where *n!* denotes the factorial of n and ^ denotes power, *i.e. (2!) ^ (2!) = 4*. -- 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/-/0tnSKnC7YRYJ. 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: problem
A correction, it is *(2^p) - 1 *, and the answer (*2^(number of primes less than n)) - 1* .(It is simply taking any subset of the primes,leaving the one in which do not take any prime) On Sun, Jun 10, 2012 at 10:03 PM, Piyush Kapoor pkjee2...@gmail.com wrote: The problem simply asks you to calculate the number of ways to express a number( = *N!^N!*) as product of two co prime numbers. For a general *N* , it is simply equal to *2^(p-1)* , where *p * is the number of distinct prime factors of *N*. For *N!* , *p* will be number of primes less than *N* , and for *N!^N!* it is same as *N!* , So the answer is *2^((number of primes less than N) - 1)* . On Sun, Jun 10, 2012 at 9:53 PM, payel roy smithpa...@gmail.com wrote: Can you please simplify the algorithm? Solution is not clear from the posted submissions !!! On 10 June 2012 20:32, KK kunalkapadi...@gmail.com wrote: This problem is of ACM-ICPC kanpur online round 2012. you can find the solution here. On Sunday, 10 June 2012 16:37:33 UTC+5:30, payel roy wrote: Find the number of fractions a/b such that- 1. gcd(a, b) = 1 2. 0 a/b 1 3. a * b = (n!) ^ (n!) Where n! denotes the factorial of n and ^ denotes power, i.e. (2!) ^ (2!) = 4. On Sunday, 10 June 2012 16:37:33 UTC+5:30, payel roy wrote: Find the number of fractions a/b such that- 1. gcd(a, b) = 1 2. 0 a/b 1 3. a * b = (n!) ^ (n!) Where n! denotes the factorial of n and ^ denotes power, i.e. (2!) ^ (2!) = 4. -- 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/-/0tnSKnC7YRYJ. 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. -- Regards, Piyush Kapoor, 2nd year,CSE IT-BHU -- *Regards,* *Piyush Kapoor,* *2nd year,CSE IT-BHU* -- 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: problem with increment operator
It's output will be compiler dependent. So on Turbo C, compiler will perform all pre-increment operation first then will start adding. like in your problem all ++a operation will go first. then addition will happen. so 6+6+6=18. on gcc, first two variables will it take, performs pre-increment operation and then adding and then third variable will come.as it continues. As in this case in gcc it will be performed like, (++a + ++a) + (a++)=(6+6)+6=18 post-increment will be unaffected during entire expression. Feel free to ask if you didn't got what i explained. On Monday, May 28, 2012 11:02:03 AM UTC+5:30, ashish wrote: #includestdio.h int main() { int a=4; printf(%d\n,++a + ++a + a++); return 0; } according to me output should be 17, but it is coming out to be 18. plz explain it?? -- 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/-/eBcLatQS34kJ. 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: problem with increment operator
The order of evaluation of sub-expressions is not defined since there is no sequence point in the sub-expression. So, the behavior is not defined, and one cannot rely on a specific compiler implementation - gcc, MSVC, or any other. As a general rule of thumb, you should avoid this type of complex expressions where the same object is modified within the sub-expressions. Regards, Ashot Madatyan From: algogeeks@googlegroups.com [mailto:algogeeks@googlegroups.com] On Behalf Of holmes Sent: Wednesday, May 30, 2012 3:21 PM To: algogeeks@googlegroups.com Subject: [algogeeks] Re: problem with increment operator It's output will be compiler dependent. So on Turbo C, compiler will perform all pre-increment operation first then will start adding. like in your problem all ++a operation will go first. then addition will happen. so 6+6+6=18. on gcc, first two variables will it take, performs pre-increment operation and then adding and then third variable will come.as it continues. As in this case in gcc it will be performed like, (++a + ++a) + (a++)=(6+6)+6=18 post-increment will be unaffected during entire expression. Feel free to ask if you didn't got what i explained. On Monday, May 28, 2012 11:02:03 AM UTC+5:30, ashish wrote: #includestdio.h int main() { int a=4; printf(%d\n,++a + ++a + a++); return 0; } according to me output should be 17, but it is coming out to be 18. plz explain it?? -- 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/-/eBcLatQS34kJ. 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.
[algogeeks] Re: Problem
aim : minimize the sum of elements of a sorted set of size k. mehdi's solution is correct, 1. sort the whole array, 2. and then as you add new element to the set a. delete the oldest element added along with its difference b. add the difference of the newly added element. O(nlogn) On Nov 19, 11:36 am, Zyro vivkum...@gmail.com wrote: sorry...minimize sum of the difference between the elements of the subset.. On Nov 19, 10:03 am, shady sinv...@gmail.com wrote: what do you mean by difference among them ? do we need to select the elements to minimize the sum between consecutive elements ? or only the first and last element ? On Nov 18, 6:30 pm, Zyro vivkum...@gmail.com wrote: Q: Select the K elements in an array of size N which are having the minimum difference among them? For Example : If you have an array like arr[]={9,5,2,6,3,11} and value of K is 3. Then ans would be {2,3,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: Problem
agree with mehdi's solution.minimizing sum of differences will be equivalent to minimizing the difference between the largest and smallest number in the setO(logn) solution.. -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://youtube.com/amolsharma99 On Sat, Nov 19, 2011 at 1:50 PM, shady sinv...@gmail.com wrote: aim : minimize the sum of elements of a sorted set of size k. mehdi's solution is correct, 1. sort the whole array, 2. and then as you add new element to the set a. delete the oldest element added along with its difference b. add the difference of the newly added element. O(nlogn) On Nov 19, 11:36 am, Zyro vivkum...@gmail.com wrote: sorry...minimize sum of the difference between the elements of the subset.. On Nov 19, 10:03 am, shady sinv...@gmail.com wrote: what do you mean by difference among them ? do we need to select the elements to minimize the sum between consecutive elements ? or only the first and last element ? On Nov 18, 6:30 pm, Zyro vivkum...@gmail.com wrote: Q: Select the K elements in an array of size N which are having the minimum difference among them? For Example : If you have an array like arr[]={9,5,2,6,3,11} and value of K is 3. Then ans would be {2,3,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. -- 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: Problem
@amol how ? we are not minimizing the difference between the greatest and smallest element in the set, but the difference of the sum of the consecutive elements in the sorted selected array of size k... and complexity O(logn) ? On Nov 19, 1:25 pm, Amol Sharma amolsharm...@gmail.com wrote: agree with mehdi's solution.minimizing sum of differences will be equivalent to minimizing the difference between the largest and smallest number in the setO(logn) solution.. -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://youtube.com/amolsharma99 On Sat, Nov 19, 2011 at 1:50 PM, shady sinv...@gmail.com wrote: aim : minimize the sum of elements of a sorted set of size k. mehdi's solution is correct, 1. sort the whole array, 2. and then as you add new element to the set a. delete the oldest element added along with its difference b. add the difference of the newly added element. O(nlogn) On Nov 19, 11:36 am, Zyro vivkum...@gmail.com wrote: sorry...minimize sum of the difference between the elements of the subset.. On Nov 19, 10:03 am, shady sinv...@gmail.com wrote: what do you mean by difference among them ? do we need to select the elements to minimize the sum between consecutive elements ? or only the first and last element ? On Nov 18, 6:30 pm, Zyro vivkum...@gmail.com wrote: Q: Select the K elements in an array of size N which are having the minimum difference among them? For Example : If you have an array like arr[]={9,5,2,6,3,11} and value of K is 3. Then ans would be {2,3,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. -- 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: Problem
sorry, we don't need to do so much computation minimizing the difference of the maximum and minimum array in the selected array is the solution. difference will always be = largest element - smallest element On Nov 19, 1:20 pm, shady sinv...@gmail.com wrote: aim : minimize the sum of elements of a sorted set of size k. mehdi's solution is correct, 1. sort the whole array, 2. and then as you add new element to the set a. delete the oldest element added along with its difference b. add the difference of the newly added element. O(nlogn) On Nov 19, 11:36 am, Zyro vivkum...@gmail.com wrote: sorry...minimize sum of the difference between the elements of the subset.. On Nov 19, 10:03 am, shady sinv...@gmail.com wrote: what do you mean by difference among them ? do we need to select the elements to minimize the sum between consecutive elements ? or only the first and last element ? On Nov 18, 6:30 pm, Zyro vivkum...@gmail.com wrote: Q: Select the K elements in an array of size N which are having the minimum difference among them? For Example : If you have an array like arr[]={9,5,2,6,3,11} and value of K is 3. Then ans would be {2,3,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: Problem
that's what i was saying :) -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://youtube.com/amolsharma99 On Sat, Nov 19, 2011 at 2:10 PM, shady sinv...@gmail.com wrote: sorry, we don't need to do so much computation minimizing the difference of the maximum and minimum array in the selected array is the solution. difference will always be = largest element - smallest element On Nov 19, 1:20 pm, shady sinv...@gmail.com wrote: aim : minimize the sum of elements of a sorted set of size k. mehdi's solution is correct, 1. sort the whole array, 2. and then as you add new element to the set a. delete the oldest element added along with its difference b. add the difference of the newly added element. O(nlogn) On Nov 19, 11:36 am, Zyro vivkum...@gmail.com wrote: sorry...minimize sum of the difference between the elements of the subset.. On Nov 19, 10:03 am, shady sinv...@gmail.com wrote: what do you mean by difference among them ? do we need to select the elements to minimize the sum between consecutive elements ? or only the first and last element ? On Nov 18, 6:30 pm, Zyro vivkum...@gmail.com wrote: Q: Select the K elements in an array of size N which are having the minimum difference among them? For Example : If you have an array like arr[]={9,5,2,6,3,11} and value of K is 3. Then ans would be {2,3,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. -- 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: Problem
@all : Thanks :) On Nov 19, 3:55 pm, Amol Sharma amolsharm...@gmail.com wrote: that's what i was saying :) -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://youtube.com/amolsharma99 On Sat, Nov 19, 2011 at 2:10 PM, shady sinv...@gmail.com wrote: sorry, we don't need to do so much computation minimizing the difference of the maximum and minimum array in the selected array is the solution. difference will always be = largest element - smallest element On Nov 19, 1:20 pm, shady sinv...@gmail.com wrote: aim : minimize the sum of elements of a sorted set of size k. mehdi's solution is correct, 1. sort the whole array, 2. and then as you add new element to the set a. delete the oldest element added along with its difference b. add the difference of the newly added element. O(nlogn) On Nov 19, 11:36 am, Zyro vivkum...@gmail.com wrote: sorry...minimize sum of the difference between the elements of the subset.. On Nov 19, 10:03 am, shady sinv...@gmail.com wrote: what do you mean by difference among them ? do we need to select the elements to minimize the sum between consecutive elements ? or only the first and last element ? On Nov 18, 6:30 pm, Zyro vivkum...@gmail.com wrote: Q: Select the K elements in an array of size N which are having the minimum difference among them? For Example : If you have an array like arr[]={9,5,2,6,3,11} and value of K is 3. Then ans would be {2,3,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. -- 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: Problem
what do you mean by difference among them ? do we need to select the elements to minimize the sum between consecutive elements ? or only the first and last element ? On Nov 18, 6:30 pm, Zyro vivkum...@gmail.com wrote: Q: Select the K elements in an array of size N which are having the minimum difference among them? For Example : If you have an array like arr[]={9,5,2,6,3,11} and value of K is 3. Then ans would be {2,3,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.
[algogeeks] Re: Problem
sorry...minimize sum of the difference between the elements of the subset.. On Nov 19, 10:03 am, shady sinv...@gmail.com wrote: what do you mean by difference among them ? do we need to select the elements to minimize the sum between consecutive elements ? or only the first and last element ? On Nov 18, 6:30 pm, Zyro vivkum...@gmail.com wrote: Q: Select the K elements in an array of size N which are having the minimum difference among them? For Example : If you have an array like arr[]={9,5,2,6,3,11} and value of K is 3. Then ans would be {2,3,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.
[algogeeks] Re: Problem
The Sum of the difference in the Subset containing the K elements must be minimum... As in above example {9,5,2,6,3,11} where K=3 In case of {2,3,5} 3-2=1 5-3=2 sum of the difference is 3...In all other subsets we cant have sum of the difference less than 3...so {2,3,5} is the required answer. On Nov 19, 10:03 am, shady sinv...@gmail.com wrote: what do you mean by difference among them ? do we need to select the elements to minimize the sum between consecutive elements ? or only the first and last element ? On Nov 18, 6:30 pm, Zyro vivkum...@gmail.com wrote: Q: Select the K elements in an array of size N which are having the minimum difference among them? For Example : If you have an array like arr[]={9,5,2,6,3,11} and value of K is 3. Then ans would be {2,3,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.
[algogeeks] Re: Problem of calculating large binomial coefficients which large base so lucas theorem cant be applied
@Pankajsingh: See the recent thread Modular arithmetic + Combinatorics in this newsgroup. Dave On Nov 6, 12:49 am, pankajsingh psingh...@gmail.com wrote: i want to calculate values like (100 C 1) %17,what would be better algorithm for it,i think lucas theorem cant be used in this case.want some efficent algorithm,actually i want to calculate mC1,mC2mC1000 %17,such that may is about 10^6 -- 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: Problem of calculating large binomial coefficients which large base so lucas theorem cant be applied
Thanks Dave, but i want some more efficient in my case, something like O(k) to calculate all mC1 mC2...mCk, i already had a worst time O(k^2), i.e for (long long int i1=1;i1=k;i1++) { while((result*(m-i1+1))%i1) { result=result+17; } result=(result*( m-i1+1)); result /= i1; result=result%17; m1[i1]=result;//mCi } this works well upto calculating 10^7 C 10^5, but i want some more efficient... does your is O(k)??,doesnt seems so,please suggest if you get any better Really thanks for the effort.. -- 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: Problem
Topology Sort :- Just want to share something to u all . The field's where Topology sort is used :- • Email loops. • Compilation units. • Class inheritance. • Course prerequisites. • Deadlocking detection. • Precedence scheduling. • Temporal dependencies. • Pipeline of computing jobs. • Check for symbolic link loop. • Evaluate formula in spreadsheet. -- 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: Problem on overflow
If both number are negative shouldn't be b min_int - a On Aug 28, 11:49 pm, Avinash LetsUncomplicate.. avin. 2...@gmail.com wrote: @Saurabh being ready to run your code for unsatisfactory input doesn't seem more logical than trying to find out if you can do something about it. i would have loved a kind reply from you. -- 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: Problem on overflow
@dave i was saying if user input a .. he can enter aintmax then how to detect overflow? -- 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: Problem on overflow
@Avinash: Give an example. Dave On Aug 28, 7:00 am, Avinash LetsUncomplicate.. avin.2...@gmail.com wrote: @dave i was saying if user input a .. he can enter aintmax then how to detect overflow? -- 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: Problem on overflow
@avinash in that case the number will become negative,It wont remain a satisfactory input.Try to think logically and believe me once you get the logic you will relent why there is no option to delete previous mails..., On Sun, Aug 28, 2011 at 6:32 PM, Dave dave_and_da...@juno.com wrote: @Avinash: Give an example. Dave On Aug 28, 7:00 am, Avinash LetsUncomplicate.. avin.2...@gmail.com wrote: @dave i was saying if user input a .. he can enter aintmax then how to detect overflow? -- 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. -- Saurabh Singh B.Tech (Computer Science) 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.
Re: [algogeeks] Re: Problem on overflow
if( unsigned int (a) + unsigned int (b) 0) return overflow else return ok; On Sun, Aug 28, 2011 at 7:23 PM, saurabh singh saurab...@gmail.com wrote: @avinash in that case the number will become negative,It wont remain a satisfactory input.Try to think logically and believe me once you get the logic you will relent why there is no option to delete previous mails..., On Sun, Aug 28, 2011 at 6:32 PM, Dave dave_and_da...@juno.com wrote: @Avinash: Give an example. Dave On Aug 28, 7:00 am, Avinash LetsUncomplicate.. avin.2...@gmail.com wrote: @dave i was saying if user input a .. he can enter aintmax then how to detect overflow? -- 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. -- Saurabh Singh B.Tech (Computer Science) 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. -- *MOHIT VERMA* -- 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: Problem on overflow
@Saurabh being ready to run your code for unsatisfactory input doesn't seem more logical than trying to find out if you can do something about it. i would have loved a kind reply from you. -- 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: Problem on overflow
@Prags: Pseudocode: If either number is zero, the sum will not overflow. If the numbers have different signs, the sum will not overflow. If both numbers are positive, overflow will occur if maxint - a = b. If both numbers are negative, overflow will occur if maxint + a = -b. Dave On Aug 27, 8:58 am, Prags onlypr...@gmail.com wrote: Two numbers are given as input check if their sum will be overflow or not ?? Give a successfull running code for it. -- 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: Problem on overflow
@dave if number a is entered exceeding limit(already overflowed) then a goes negative(if a was entred just more than limit ) /a goes positive (if a was entred sufficiently more than limit ) maxint -a=b concept fails Avinash Katiyar NIT 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: Problem on overflow
@Avinash: What do you mean by exceeding limit(already overflowed)? The number maxint is the limit. Every positive number is = maxint. Dave On Aug 27, 10:31 am, Avinash LetsUncomplicate.. avin. 2...@gmail.com wrote: @dave if number a is entered exceeding limit(already overflowed) then a goes negative(if a was entred just more than limit ) /a goes positive (if a was entred sufficiently more than limit ) maxint -a=b concept fails Avinash Katiyar NIT 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.
Re: [algogeeks] Re: Problem on overflow
@Dave: +1 for nice solution... :) On Sat, Aug 27, 2011 at 10:12 PM, Dave dave_and_da...@juno.com wrote: @Avinash: What do you mean by exceeding limit(already overflowed)? The number maxint is the limit. Every positive number is = maxint. Dave On Aug 27, 10:31 am, Avinash LetsUncomplicate.. avin. 2...@gmail.com wrote: @dave if number a is entered exceeding limit(already overflowed) then a goes negative(if a was entred just more than limit ) /a goes positive (if a was entred sufficiently more than limit ) maxint -a=b concept fails Avinash Katiyar NIT 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: Problem on overflow
@Dave: i didn't understand, suppose a=3, b=31000 and MaxInt=32000; you are saying if (MaxInt-a)=b; then overflow will occur. but here condition is not satisfying. plz explain. -- 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/-/fE3AeoR_djAJ. 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: Problem on overflow
@Abishek: I was brain-dead in my earlier posting. Let me try again: If either number is zero, the sum will not overflow. If the numbers have different signs, the sum will not overflow. If both numbers are positive, overflow will occur if b maxint - a. If both numbers are negative, overflow will occur if b -maxint - a - 1. Dave On Aug 27, 12:18 pm, Abhishek mailatabhishekgu...@gmail.com wrote: @Dave: i didn't understand, suppose a=3, b=31000 and MaxInt=32000; you are saying if (MaxInt-a)=b; then overflow will occur. but here condition is not satisfying. plz explain. -- 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: Problem on overflow
I think you just need to reverse the comparison operators in Dave's earlier post On Sat, Aug 27, 2011 at 10:59 PM, Dave dave_and_da...@juno.com wrote: @Abishek: I was brain-dead in my earlier posting. Let me try again: If either number is zero, the sum will not overflow. If the numbers have different signs, the sum will not overflow. If both numbers are positive, overflow will occur if b maxint - a. If both numbers are negative, overflow will occur if b -maxint - a - 1. Dave On Aug 27, 12:18 pm, Abhishek mailatabhishekgu...@gmail.com wrote: @Dave: i didn't understand, suppose a=3, b=31000 and MaxInt=32000; you are saying if (MaxInt-a)=b; then overflow will occur. but here condition is not satisfying. plz explain. -- 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. -- Dipit Grover B.Tech in CSE IIT Roorkee -- 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: Problem on overflow
Oops, I just saw that Dave had already corrected it. Net problem, sorry guys! On Sat, Aug 27, 2011 at 11:02 PM, dipit grover digo.d.b...@gmail.comwrote: I think you just need to reverse the comparison operators in Dave's earlier post On Sat, Aug 27, 2011 at 10:59 PM, Dave dave_and_da...@juno.com wrote: @Abishek: I was brain-dead in my earlier posting. Let me try again: If either number is zero, the sum will not overflow. If the numbers have different signs, the sum will not overflow. If both numbers are positive, overflow will occur if b maxint - a. If both numbers are negative, overflow will occur if b -maxint - a - 1. Dave On Aug 27, 12:18 pm, Abhishek mailatabhishekgu...@gmail.com wrote: @Dave: i didn't understand, suppose a=3, b=31000 and MaxInt=32000; you are saying if (MaxInt-a)=b; then overflow will occur. but here condition is not satisfying. plz explain. -- 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. -- Dipit Grover B.Tech in CSE IIT Roorkee -- Dipit Grover B.Tech in CSE IIT Roorkee -- 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: Problem on overflow
@Dave: Still your approach to solve the problem remains correct. (subtracting a number from max possible value then comparing this difference with another number). So, no need to think that you were brain dead (If you were, you would have posted a movie story here)..[?] Mathematically it is wrong, not in terms of approach..[?] On Sat, Aug 27, 2011 at 11:02 PM, dipit grover digo.d.b...@gmail.comwrote: I think you just need to reverse the comparison operators in Dave's earlier post On Sat, Aug 27, 2011 at 10:59 PM, Dave dave_and_da...@juno.com wrote: @Abishek: I was brain-dead in my earlier posting. Let me try again: If either number is zero, the sum will not overflow. If the numbers have different signs, the sum will not overflow. If both numbers are positive, overflow will occur if b maxint - a. If both numbers are negative, overflow will occur if b -maxint - a - 1. Dave On Aug 27, 12:18 pm, Abhishek mailatabhishekgu...@gmail.com wrote: @Dave: i didn't understand, suppose a=3, b=31000 and MaxInt=32000; you are saying if (MaxInt-a)=b; then overflow will occur. but here condition is not satisfying. plz explain. -- 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. -- Dipit Grover B.Tech in CSE IIT Roorkee -- 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. 361.gif360.gif
[algogeeks] Re: Problem on overflow
@Kunal: You are very kind. Dave On Aug 27, 12:58 pm, Kunal Patil kp101...@gmail.com wrote: @Dave: Still your approach to solve the problem remains correct. (subtracting a number from max possible value then comparing this difference with another number). So, no need to think that you were brain dead (If you were, you would have posted a movie story here)..[?] Mathematically it is wrong, not in terms of approach..[?] On Sat, Aug 27, 2011 at 11:02 PM, dipit grover digo.d.b...@gmail.comwrote: I think you just need to reverse the comparison operators in Dave's earlier post On Sat, Aug 27, 2011 at 10:59 PM, Dave dave_and_da...@juno.com wrote: @Abishek: I was brain-dead in my earlier posting. Let me try again: If either number is zero, the sum will not overflow. If the numbers have different signs, the sum will not overflow. If both numbers are positive, overflow will occur if b maxint - a. If both numbers are negative, overflow will occur if b -maxint - a - 1. Dave On Aug 27, 12:18 pm, Abhishek mailatabhishekgu...@gmail.com wrote: @Dave: i didn't understand, suppose a=3, b=31000 and MaxInt=32000; you are saying if (MaxInt-a)=b; then overflow will occur. but here condition is not satisfying. plz explain. -- 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. -- Dipit Grover B.Tech in CSE IIT Roorkee -- 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. 361.gif 1KViewDownload 360.gif 1KViewDownload- Hide quoted text - - Show quoted text - -- 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: Problem on overflow
@Avinash: maxint is the largest possible integer. There aren't any integers greater than it. Thus, a can't be greater than maxint. For example, if an int is 32 bits, maxint = 2^31 - 1. Dave On Aug 27, 10:41 pm, Avinash LetsUncomplicate.. avin. 2...@gmail.com wrote: @dave i was saying if user enter a+b in which aintmax .. A goes negative(if a sligtly intmax) a+b =no overflow which we know shouldnt be an answer.. On 8/28/11, Dave dave_and_da...@juno.com wrote: @Kunal: You are very kind. Dave On Aug 27, 12:58 pm, Kunal Patil kp101...@gmail.com wrote: @Dave: Still your approach to solve the problem remains correct. (subtracting a number from max possible value then comparing this difference with another number). So, no need to think that you were brain dead (If you were, you would have posted a movie story here)..[?] Mathematically it is wrong, not in terms of approach..[?] On Sat, Aug 27, 2011 at 11:02 PM, dipit grover digo.d.b...@gmail.comwrote: I think you just need to reverse the comparison operators in Dave's earlier post On Sat, Aug 27, 2011 at 10:59 PM, Dave dave_and_da...@juno.com wrote: @Abishek: I was brain-dead in my earlier posting. Let me try again: If either number is zero, the sum will not overflow. If the numbers have different signs, the sum will not overflow. If both numbers are positive, overflow will occur if b maxint - a. If both numbers are negative, overflow will occur if b -maxint - a - 1. Dave On Aug 27, 12:18 pm, Abhishek mailatabhishekgu...@gmail.com wrote: @Dave: i didn't understand, suppose a=3, b=31000 and MaxInt=32000; you are saying if (MaxInt-a)=b; then overflow will occur. but here condition is not satisfying. plz explain. -- 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. -- Dipit Grover B.Tech in CSE IIT Roorkee -- 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. 361.gif 1KViewDownload 360.gif 1KViewDownload- Hide quoted text - - Show quoted text - -- 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. -- Sent from my mobile device- Hide quoted text - - Show quoted text - -- 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: problem regarding output??
++ on a void* will increase the address by 1 byte. ++ on a type* will increase the address by sizeof(type) bytes. As if the initial pointer were an array of type On Aug 9, 2:49 pm, Rajesh Kumar testalgori...@gmail.com wrote: why j and k point different location? #includestdio.h main() { int a=10,*j; void *k; j=k=a; k=(int *)k; k++; j++; printf(%u %u\n,j,k); } -- Regards Rajesh Kumar -- 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: problem regarding output??
C++ will not allow void pointer to increment. But in C we can perform it where void will be treated as char* http://stackoverflow.com/questions/3523145/pointer-arithmetic-for-void-pointer-in-c On Aug 9, 6:39 pm, UMarius mar...@aseara.ro wrote: ++ on a void* will increase the address by 1 byte. ++ on a type* will increase the address by sizeof(type) bytes. As if the initial pointer were an array of type On Aug 9, 2:49 pm, Rajesh Kumar testalgori...@gmail.com wrote: why j and k point different location? #includestdio.h main() { int a=10,*j; void *k; j=k=a; k=(int *)k; k++; j++; printf(%u %u\n,j,k); } -- Regards Rajesh Kumar -- 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: problem regarding output??
(int *) it is derefrencing of any void pointer into integer. -- 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: problem tree minimum sum in binary
Guys this problem generated lot of discussion in computer science as ist Euler Problem as it involves maths stuff rather then considering tree (it wont work check below link for detail ) or applying computer science . Also problem is already famous (Euler problem ) as we have to find the maximum sum in triangle we have given a big triangle which has many small triangle only thing u need to know a triangle has 3 vertexes so that you can approach :) and a detailed description,explaination solution you can find here using bottom up iterative approach :) http://shashank7s.blogspot.com/2011/04/project-euler-problem-67-finding.html let me know if i missed something or any other approach to solve it Shashank Mani Computer Science Birla Institute of Technlogy,Mesra -- 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/-/WSaKBwAWiW4J. 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: Problem: Longest Increasing Seq code
p[i] maintains previous index from which b[i] has reached longest sequence till i. to get the actual list of non-decrease sequence, p has to be traversed through back indices for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v; surender On Sat, Jul 16, 2011 at 9:06 AM, Neeraj Gupta neeraj.gupta...@gmail.comwrote: Hi Can anyone help me in understanding the following code http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence.cpp I am not able to understand what is the exact purpose of vector p in the above mentioned code. A little detail explanation will be helpful. I have already read this the basic idea of the algorithm * Let Ai,j be the smallest possible tail out of all increasing subsequences of length j using elements a1, a2, ... , ai. Observe that, for any particular i, Ai,1, Ai,2, ... , Ai,j. This suggests that if we want the longest subsequence that ends with ai + 1, we only need to look for a j such that Ai,j ai + 1 = Ai,j + 1 and the length will be j + 1. Notice that in this case, Ai + 1,j + 1 will be equal to ai + 1, and all Ai + 1,k will be equal to Ai,k for k!=j+1. Furthermore, there is at most one difference between the set Ai and the set Ai + 1, which is caused by this search. Since A is always ordered in increasing order, and the operation does not change this ordering, we can do a binary search for every single a 1, a2, ... , an. * ~Neeraj Hi, -- 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.
[algogeeks] Re: Problem: Longest Increasing Seq code
Hi Can anyone help me in understanding the following code http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence.cpp I am not able to understand what is the exact purpose of vector p in the above mentioned code. A little detail explanation will be helpful. I have already read this the basic idea of the algorithm * Let Ai,j be the smallest possible tail out of all increasing subsequences of length j using elements a1, a2, ... , ai. Observe that, for any particular i, Ai,1, Ai,2, ... , Ai,j. This suggests that if we want the longest subsequence that ends with ai + 1, we only need to look for a j such that Ai,j ai + 1 = Ai,j + 1 and the length will be j + 1. Notice that in this case, Ai + 1,j + 1 will be equal to ai + 1, and all Ai + 1,k will be equal to Ai,k for k!=j+1. Furthermore, there is at most one difference between the set Ai and the set Ai + 1, which is caused by this search. Since A is always ordered in increasing order, and the operation does not change this ordering, we can do a binary search for every single a1, a2, ... , an. * ~Neeraj Hi, -- 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: Problem
For small numbers, trial division would work. Be sure to only divide by prime numbers. When you find one which divides your target, increment your counter and divide the target by that number as many times as it works. Then go on to the next prime. When the prime squared is larger than the target, you are done. The number of divisors is 2 times the product of the number of times each prime divided the target. For large numbers you need to look into methods for factoring large numbers. You would want to start with a test to determine that the number is composite. If not, it has 2 divisors. Then try to divide the number by small primes. Then use one of the factoring algorithms such as the General Number Field Sieve to find factors. Don On May 11, 8:55 am, Harshit Gangal harshit.gan...@gmail.com wrote: How can we calculate the number of divisors a number have in minimum time or having minimum Time Complexity. -- Harshit Gangal Fourth Year Undergraduate Student Dept. of Computer Science JIIT, Noida , India -- 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: Problem regarding MySql server Installation
i forget to say that every tool has its own site for documentation help check it it out http://dev.mysql.com/doc/refman/5.5/en/default-privileges.html Thanks Shashank -- 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: Problem regarding MySql server Installation
As i remeber you can do this on command prompt type i am assuming u have installed configured mysql mysql -u username -p password i think u shoud have google it Thanks Regards Shashank Mani The Best Way to escape Fromm problem is Solve It CSE,BIT Mesra -- 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: Problem regarding MySql server Installation
Sorry, but this isn't a mysql group. all discussions need to be algorithm related. On Apr 28, 3:04 pm, Aniket aniket...@gmail.com wrote: I was trying to install mysql 5.5. in Windows XP.After installation during configuration phase when there was to apply security settings I m always getting an error Error No 1045 Access Denied for user 'root'@localhost(using password: NO). I have tried all possibilities in Firewall but it dint work.Hope anybody here will help me out of this problem.I am totally screwed up!!! -- 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: Problem; print the largest subset of negative number in array of integers
How about the following way.. where you can save some space. but before that.. you meant, your application will need O(n) space for the recursion only right? in that case, instead of the recursion, try this approach. set start, length = 0, tempStart, tempLenght =0 set tempStart = i_value increase tempLenght for every negative number until you find a positive number, when positive, check tempLength lenght and assign the set the length, start accordingly. and set tempStart,tempLength to 0 and go until the end. returning the value. sizeOfArray*start + length u can extract these two in main and print. return the following things, -- 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: Problem from ACM ICPC 2010
There are 4 kids). So 1, 2, 3 are connected into a circle. There is no place for the remaining 4-th) -- 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: Problem from ACM ICPC 2010_2
Run dfs/bfs from the root (node 0). Store distance from the root to each node at the node's data. Then the final path's weight between i and j is: dist[i] + dist[j] - dist[lca(i, j)]. -- 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: Problem from ACM ICPC 2010_2
Thanks, i finished it. :) it wasdist[i] + dist[j] - 2*dist[lca(i, j)] this problem is difficult :( http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4809 I dont have idea how to solve it. -- 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: Problem from ACM ICPC 2010
Just got AC for this problem. Here is simple solution: 1. Calculate degree for each vertex. If there is a degree 2, then answer is No. You may use hash_map or map here. 2. So at this step we don't have any verticies with 3 and more edges, only = 2 are allowed. Though, we should check if there is circle (cycle). If such exists and it doesn't have ALL vertices (it size is equal to n, so all children are connected next to each other), then answer is No, otherwise Yes. Used bfs for this. Good luck. -- 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: Problem from ACM ICPC 2010
Hi.. thanks for your response. The number of kids: 3 = K = 10^9 I cant declare an array: long long A[10]; and how does dfs or bfs finds the components of the graph? because i have to verify if there is a cycle in all the components. -- 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: Problem from ACM ICPC 2010
Use mapint, vectorint whichs maps vertex and all its neighbors. You should use bfs only to find if there is cycle (with a shape of circle). setint is useful to keep track of visited vertices. -- 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: Problem from ACM ICPC 2010
Also, you may use hash_set and hash_map if such exists in your language. -- 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: Problem from ACM ICPC 2010
In the 3rd test case, how come the answer is Yes. 1,2 and 3 are forming a cycle. On Jan 8, 1:19 pm, juver++ avpostni...@gmail.com wrote: Also, you may use hash_set and hash_map if such exists in your language. -- 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: Problem from ACM ICPC 2010
I wondered that too...seems kid 3 gets too many wishes On Jan 8, 8:21 pm, bhawana goel bhawan...@gmail.com wrote: In the 3rd test case, how come the answer is Yes. 1,2 and 3 are forming a cycle. On Jan 8, 1:19 pm, juver++ avpostni...@gmail.com wrote: Also, you may use hash_set and hash_map if such exists in your language. -- 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: Problem with Virtual Function
Guys Lets keep discussions in t his group limited to Algos and problems neutral to any language. @akshay: Request you to post these C++ language specific questions to those language specific groups. This will not only help this group remain confined to its core purpose but will help you get better insights to ur problem by language specific geeks there. For C++ I would recommend you to try the group http://groups.google.co.in/group/comp.lang.c++.moderated/topics?hl=en. Regards, Sourav On Jun 13, 5:08 pm, BALARUKESH SIVARAMAN sbalarukesh1...@gmail.com wrote: In the first post the problem was that m_speed is not public also u should access m_speed using Scope resolution operator as m_speed is not a member of B. class A { public: virtual int speed()=0; int m_speed;}; class B:public A { public: int speed() { return A::m_speed;} }; For ur second question... int main() { A *aptr=new B; coutaptr-speed(); return 0; } I hope ur not clear with the concept of virtual functions... This example will help you. If not post back ur questions... -- 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: Problem in code
Can we just not post the code here for debugging? This group more related to algorithms than implementations. If your code is not working, use debugger. On Sat, Feb 23, 2008 at 6:22 AM, monty 1987 [EMAIL PROTECTED] wrote: Find out why this program is not working which converts list representation of graph in adjacency matrix #includeiostream using namespace std; struct node { node* point; node* next; int info; }; node * getnode(int i); void adja(int count,node **p); int main() { int count,wt,j,i; node *r1,*r2; char c='y'; coutEnter the no. of nodes; cincount; node * root[50]; for(i=0;icount;++i) { root[i]=getnode(i); if(i!=0) root[i-1]-next=root[i]; } for(i=0;icount;++i) { c='y'; r2=root[i]; while(c=='y') { coutEnter the node connected to i+1 th node :; cinj; coutEnter the weight; cinwt; if(r2==root[i]) { r2-point=getnode(wt); r2=r2-point; r2-point=root[j-1]; r2-info=wt; } else { r2-next=getnode(wt); r2=r2-next; r2-point=root[j-1]; r2-info=wt; } coutEnter y for more node else n :-; cinc; } } adja(count,root[0]); } node * getnode(int i) { node * s=new node; s-info=i; s-next=NULL; s-point=NULL; return s; } void adja(int count,node **p) { node *k; int adj[50][50],i,flag,j; couter; for(i=0;icount;++i) for(j=0;jcount;j++) adj[i][j]=0; for(i=0;icount;++i) { coutrr; k=*(p+i); while(k!=NULL) { flag=0; if(flag==0) { k=k-point; adj[i][k-info]=k-info; flag=1; } else { k=k-next; adj[i][k-info]=k-info; } } } for(i=0;icount;++i) { for(j=0;jcount;j++) coutadj[i][j]\t; cout\n; } } --~--~-~--~~~---~--~~ 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: Problem with conditional statement
It says If there is more than one solution print the pair with smaller X value. Also I believe for a value of X only one of the 2 Y values might work, not sure though. -Dhyanesh On 6/18/07, mukesh tiwari [EMAIL PROTECTED] wrote: Hi everybody i am trying to solve problem http://acm.uva.es/p/v105/10512.html. my solution is (x+y)y=P(1) (x-y)x=Q (2) (1+(y/x))xy=P (1)//taking x outside (1-(y/x))x^2=Q (2) dividing 1 and 2 and let (y/x)=k (1+k)k/(1-k)=P/Q; solving for k k=-(P+Q) +-sqrt((P+Q)^2+4PQ)/2Q; since x=y so we can not take -ve sign as it will make |k|1 which is not possible so i take only +ve sign ; solution is possible only when (P+Q)^2+4PQ is perfect square . after determining k we can find out x and y so my values are x=+-sqrt(Q/(1-k)); and y=+-sqrt(Pk/(1+k)); now my problem is based on for each value of x we have two values of y so we have 4 pair of values .So which value to output . thnkx 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: problem with string class in c++
hi :) and welcome to C++ there's some problems in your code... 1. the string temp has the length 0 and you cannot use subscript operator to access for example temp[3] or temp[2] or . first in the declaration of temp you can initialize it by x (just to adjust the size to the appropriate) string temp = x; then modify the characters using your loop or ... 2.when you wanna output it via cout... it fails because it contain characters which are not in the defined range... (the characters does not have a symbol to show...) so you must either use the loop (for) you used with %d or add '0' to all of them and use couttemp; (I advise not to change the characters to 0,1,2,... use '0' and '1' it's not hard to work with them...! you can simply ++ them or anything (but not %2 /2 ... - just put an if...)) 3.you use the variable len in your code... but be aware of the last loop!! if you prepend a 1 in the beginning of your string then you must perform the loop for len+1 times for printing...! so just use couttempendl; and some other things that makes your code a better c++ code! : use coutendl; instead of cout\n; simply use x = 1 + temp omit x=temp and q=1 ... good luck. On Friday 09 February 2007 02:43, mukesh tiwari wrote: hi everybody I have to add one in a binary string . I m using string class but i m not getting the correct result . i hve just started the programing in c++. here is my code and i will explaining it... in plusOne funtion i store the length of string in len variable . i took two string temp and q and initialize q with 1. now i coping the content string x into sring temp by subtracting the ascii value of char 0 temp[i]=x[i]-'0';//is this assignment is wrong or right then after i am doing simlple arithmetic .but problem is that when i m printing the temp and x string using printf function it gives the correct result but at the same time cout is giving a blank line... now my algorithm do is if a carry is generated in last operation(when i=0) then append 1 before temp ..(for example if input is 111 then adding 1 will give 1000 ...) now my confusion is that for multiple precison arithmetic can we use string class in c++ like char array in c or not plz explain me ... here is some input 101010//this input will give correct output 111//wrong out ...i cant understand why .. plz somebody expert in c++ explain .i hve just started coding in c++.. #includeiostream #includestring #includecstdio using namespace std; class BinaryString { public: string plusOne(string x) { int len=x.length(),i,carry=1;//initially carry will be 1 becoz we have to add 1 in string x. string temp,q; q=1;//intialization of string for(i=0;ilen;i++) temp[i]=x[i]-'0'; for(i=len-1;i=0;i--) { temp[i]=temp[i]+carry; carry=temp[i]/2; temp[i]=temp[i]%2; } for(i=0;ilen;i++) printf(%d,temp[i]); cout\n; //couttemp\n; x=temp; if(carry==1)//append 1 at starting of string temp; x=q+temp; for(i=0;ilen;i++) printf(%d,x[i]); cout\n; coutx\n; return(x); } }; int main() { string x; BinaryString B; while(cinx) B.plusOne(x); //coutx\n; --~--~-~--~~~---~--~~ 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-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: problem regarding lexicographic path
well mukesh , I solved the problem iteratively from right to left and filling up an arry. Here is my code. I think Lago Haryanto was right. you have to select and find out the lexicographically shortest path greedily. Minhaz code: /* @JUDGE_ID: 55890 116 C++*/ #includestdio.h void min3(int,int); void dp(void); void print(void); struct datum{ long long cur_val; long long cur_sum; int nextro; }; struct datum data[11][101]; int cur_ro,cur_col; void main(){ int i,j; while(scanf(%d,cur_ro)==1){ scanf(%d,cur_col); for(i=1;i=cur_ro;i++){ for(j=1;j=cur_col;j++){ scanf(%lld,data[i][j].cur_val); } } dp(); print(); } } void dp(void){ int i,j; for(i=1;i=cur_ro;i++) data[i][cur_col].cur_sum=data[i][cur_col].cur_val; for(j=cur_col-1;j0;j--){ for(i=1;i=cur_ro;i++){ min3(i,j); } } } void min3(int row,int col){ int a,b,c; long long sum_a,sum_b,sum_c; b=row; sum_b=data[row][col+1].cur_sum; a=row-1; c=row+1; if(row==1) a=cur_ro; if(row==cur_ro) c=1; sum_a=data[a][col+1].cur_sum; sum_c=data[c][col+1].cur_sum; if(sum_asum_b){ if(sum_asum_c){ data[row][col].nextro=a; data[row][col].cur_sum=sum_a+data[row][col].cur_val; } else if(sum_a==sum_c){ if(ac){ data[row][col].nextro=a; data[row][col].cur_sum=sum_a+data[row][col].cur_val; } else{ data[row][col].nextro=c; data[row][col].cur_sum=sum_c+data[row][col].cur_val; } } else{ data[row][col].nextro=c; data[row][col].cur_sum=sum_c+data[row][col].cur_val; } } else if(sum_a==sum_b){ if(ab){ if(sum_asum_c){ data[row][col].nextro=a; data[row][col].cur_sum=sum_a+data[row][col].cur_val; } else if(sum_a==sum_c){ if(ac){ data[row][col].nextro=a; data[row][col].cur_sum=sum_a+data[row][col].cur_val; } else{ data[row][col].nextro=c; data[row][col].cur_sum=sum_c+data[row][col].cur_val; } } else{ data[row][col].nextro=c; data[row][col].cur_sum=sum_c+data[row][col].cur_val; } } else{ if(sum_bsum_c){ data[row][col].nextro=b; data[row][col].cur_sum=sum_b+data[row][col].cur_val; } else if(sum_b==sum_c){ if(bc){ data[row][col].nextro=b; data[row][col].cur_sum=sum_b+data[row][col].cur_val; } else{ data[row][col].nextro=c; data[row][col].cur_sum=sum_c+data[row][col].cur_val; } } else{ data[row][col].nextro=c; data[row][col].cur_sum=sum_c+data[row][col].cur_val; } } } else{ if(sum_bsum_c){ data[row][col].nextro=b; data[row][col].cur_sum=sum_b+data[row][col].cur_val; } else if(sum_b==sum_c){ if(bc){ data[row][col].nextro=b; data[row][col].cur_sum=sum_b+data[row][col].cur_val; } else{ data[row][col].nextro=c; data[row][col].cur_sum=sum_c+data[row][col].cur_val; } } else{ data[row][col].nextro=c; data[row][col].cur_sum=sum_c+data[row][col].cur_val; } } } void print(void){ int min_ro,i; long long min_sum; if(cur_ro!=0) min_ro=1; else min_ro=0; if(cur_col!=0) min_sum=data[1][1].cur_sum; else min_sum=0; for(i=2;i=cur_ro;i++){ if(min_sumdata[i][1].cur_sum){ min_sum=data[i][1].cur_sum; min_ro=i; } } printf(%d,min_ro); for(i=1;icur_col;i++){ min_ro=data[min_ro][i].nextro; printf( %d,min_ro); } printf(\n%lld\n,min_sum); } On 12/13/06, mukesh tiwari [EMAIL PROTECTED] wrote: hi Lego Haryanto i tried ur metoh but still not working ...here is my code and i m tired with this program . i am not getting even a single method to find lexicographic shortest path. #includestdio.h int min1(int k,int m,int n) { int min; min=k; if(minm) min=m; if(minn) min=n; return(min); } main() { int m1[100][100],a[100][100],i,j,m,n,min,k,arr[100],t,min2,t1,t2,t3,v1; while(scanf(%d%d,m,n)==2) { for(i=0;im;i++) for(j=0;jn;j++) scanf(%d,a[i][j]); for(i=0;im;i++) m1[i][0]=a[i][0]; for(j=1;jn;j++) for(i=0;im;i++) m1[i][j]=a[i][j]+min1(m1[(i+m-1)%m][j-1],m1[i][j-1],m1[(i+1)%m][j-1]); /*for(i=0;im;i++) { for(j=0;jn;j++) printf(%d,m1[i][j]); printf(\n); } printf(\n);*/ min2=m1[0][n-1]; k=0; for(i=1;im;i++) if(m1[i][n-1]min2) { min2=m1[i][n-1]; k=i;
[algogeeks] Re: problem regarding lexicographic path
hi Lego Haryanto i tried ur metoh but still not working ...here is my code and i m tired with this program . i am not getting even a single method to find lexicographic shortest path. #includestdio.h int min1(int k,int m,int n) { int min; min=k; if(minm) min=m; if(minn) min=n; return(min); } main() { int m1[100][100],a[100][100],i,j,m,n,min,k,arr[100],t,min2,t1,t2,t3,v1; while(scanf(%d%d,m,n)==2) { for(i=0;im;i++) for(j=0;jn;j++) scanf(%d,a[i][j]); for(i=0;im;i++) m1[i][0]=a[i][0]; for(j=1;jn;j++) for(i=0;im;i++) m1[i][j]=a[i][j]+min1(m1[(i+m-1)%m][j-1],m1[i][j-1],m1[(i+1)%m][j-1]); /*for(i=0;im;i++) { for(j=0;jn;j++) printf(%d,m1[i][j]); printf(\n); } printf(\n);*/ min2=m1[0][n-1]; k=0; for(i=1;im;i++) if(m1[i][n-1]min2) { min2=m1[i][n-1]; k=i; } //printf(k=%d min=%d\n,k+1,min2); arr[n-1]=k; //printf(min=%d arr[%d]=%d\n,min2,n-1,arr[n-1]); for(j=n-2;j=0;j--) { //printf(j=%d ,j); min=m1[(arr[j+1]+m-1)%m][j]; t1=(arr[j+1]+m-1)%m; t=t1; if(minm1[arr[j+1]][j]) { min=m1[arr[j+1]][j]; t2=arr[j+1]; t=t2; } else if(min==m1[arr[j+1]][j]) { t2=arr[j+1]; if(t1t2) t=t2; else t=t1; } if(minm1[(arr[j+1]+1)%m][j]) { min=m1[(arr[j+1]+1)%m][j]; t3=(arr[j+1]+1)%m; t=t3; } else if(min==m1[(arr[j+1]+1)%m][j]) { t3=(arr[j+1]+1)%m; if(tt3) t=t3; } arr[j]=t; //printf(min=%d arr[%d]=%d\n,min,j,t); } for(i=0;i=n-1;i++) printf(%d ,arr[i]+1); printf(\n%d\n,min2); } } --~--~-~--~~~---~--~~ 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-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem 4.2 from Introduction to algorithms
wrb wrote: in arrange 1..n there are n different numbers. how can you fill A[1..n] without any one of them? That occurred to me as well, but I assumed that it must be allowed that for A[i] == A[j], i != j because otherwise it would be impossible for there to be any missing numbers. 2006/12/1, W Karas [EMAIL PROTECTED]: Norbert wrote: Hi, please help me solve this problem. It's something like that: given an array A[1...n] filled with different integers in range [1...n], find a missing number. The only operation which you can use is get_ith_bit_from_pos_n(i, n) = i'th bit of A[n]. This can be solved in O(n) time. But how? Assuming: 1. the stuff about reading bit by bit is a pointless irritant. 2. it's OK to destroy the contents of A. 3. the entries of A can be set to zero. 4. O(1) aux space usage is OK. for (scan = 1; scan = N; scan++) { curr = A[scan]; if (curr != 0) for ( ; ; ) { next = A[curr]; if (next == 0) break; A[curr] = 0; curr = next; } } for (scan = 1; scan = N; scan++) if (A[scan] != 0) return(scan); // Else no number missing. return(0); The inner for loop would execute at most 2N times in total, so the algorithm is O(N) . --=_Part_50614_9096516.1164934509339 Content-Type: text/html; charset=ISO-8859-1 X-Google-AttachSize: 1801 divin arrange 1..n there are n different numbers. how can you fill A[1..n] without any one of them?/div divbrbr /div divspan class=gmail_quote2006/12/1, W Karas a href=mailto:[EMAIL PROTECTED][EMAIL PROTECTED]/a:/span blockquote class=gmail_quote style=PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solidbrNorbert wrote:br Hi, please help me solve this problem. It's something like that: givenbr an array A[1...n] filled with different integers in range [1...n], br find a missing number. The only operation which you can use isbr get_ith_bit_from_pos_n(i, n) = i'th bit of A[n]. This can be solved inbr O(n) time. But how?brbrAssuming:br1. the stuff about reading bit by bit is a pointless irritant. br2. it's OK to destroy the contents of A.br3. the entries of A can be set to zero.br4. O(1) aux space usage is OK.brbrfor (scan = 1; scan = N; scan++)br{br curr = A[scan];br if (curr != 0)br for ( ; ; ) br {br next = A[curr];br if (next == 0)br break;br A[curr] = 0;br curr = next;br }br}brbrfor (scan = 1; scan = N; scan++)brif (A[scan] != 0)br return(scan);brbr// Else no number missing.brreturn(0);brbrThe inner for loop would execute at most 2N times in total,brso the algorithm is O(N) .brbrbr --=_Part_50614_9096516.1164934509339-- sp;nbsp; }br}brbrfor (scan = 1; scan lt;= N; scan++)brif (A[scan] != 0)br nbsp;nbsp; return(scan);brbr// Else no number missing.brreturn(0);brbrThe inner for loop would execute at most 2N times in total,brso the algorithm is O(N) .brbrbr --=_Part_50614_9096516.1164934509339-- --~--~-~--~~~---~--~~ 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-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem 4.2 from Introduction to algorithms
Norbert wrote: Hi, please help me solve this problem. It's something like that: given an array A[1...n] filled with different integers in range [1...n], find a missing number. The only operation which you can use is get_ith_bit_from_pos_n(i, n) = i'th bit of A[n]. This can be solved in O(n) time. But how? Assuming: 1. the stuff about reading bit by bit is a pointless irritant. 2. it's OK to destroy the contents of A. 3. the entries of A can be set to zero. 4. O(1) aux space usage is OK. for (scan = 1; scan = N; scan++) { curr = A[scan]; if (curr != 0) for ( ; ; ) { next = A[curr]; if (next == 0) break; A[curr] = 0; curr = next; } } for (scan = 1; scan = N; scan++) if (A[scan] != 0) return(scan); // Else no number missing. return(0); The inner for loop would execute at most 2N times in total, so the algorithm is O(N) . --~--~-~--~~~---~--~~ 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-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem 4.2 from Introduction to algorithms
in arrange 1..n there are n different numbers. how can you fill A[1..n] without any one of them? 2006/12/1, W Karas [EMAIL PROTECTED]: Norbert wrote: Hi, please help me solve this problem. It's something like that: given an array A[1...n] filled with different integers in range [1...n], find a missing number. The only operation which you can use is get_ith_bit_from_pos_n(i, n) = i'th bit of A[n]. This can be solved in O(n) time. But how? Assuming: 1. the stuff about reading bit by bit is a pointless irritant. 2. it's OK to destroy the contents of A. 3. the entries of A can be set to zero. 4. O(1) aux space usage is OK. for (scan = 1; scan = N; scan++) { curr = A[scan]; if (curr != 0) for ( ; ; ) { next = A[curr]; if (next == 0) break; A[curr] = 0; curr = next; } } for (scan = 1; scan = N; scan++) if (A[scan] != 0) return(scan); // Else no number missing. return(0); The inner for loop would execute at most 2N times in total, so the algorithm is O(N) . --~--~-~--~~~---~--~~ 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-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem 4.2 from Introduction to algorithms
Is this extracting i'th bit from a[X] or just extracting Integer from i th index of an array??? if its the later, then get the number and sum up by using OR operation not sure:-) then subtract it from n(n+1)/2=missing Number --~--~-~--~~~---~--~~ 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-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem 4.2 from Introduction to algorithms
extract(i, n) - i'th bit from position n in an array A - i'th bit of A[n] On 11/17/06, Idris [EMAIL PROTECTED] wrote: Is this extracting i'th bit from a[X] or just extracting Integer from i th index of an array??? if its the later, then get the number and sum up by using OR operation not sure:-) then subtract it from n(n+1)/2=missing Number --~--~-~--~~~---~--~~ 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-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem 4.2 from Introduction to algorithms
1) Scan through the array counting number of 0s and 1s in MSB, as well as separating the 0s into an array arr0 and 1s into an array arr1 (if you do not want to use extra space you can use splitting around pivot pass of quicksort). 2) You would know how many 0s and 1s should be present in MSB for the number 1 ... n (this would be n/2 and n/2 if n is a power of 2). 3) Either the 0s or 1s would be less, so the missing number has that digit as MSB. 4) Take that bucket i.e. arr0 or arr1 and repeat steps 1 to 3. The complexity of this is n + n/2 + n/4 ... = 2n = O(n). -Dhyanesh On 11/17/06, Arun [EMAIL PROTECTED] wrote: the original problem if the array is unsorted, u can do it, by counting the number of 1's (and hence 0's), in each bit position. (i.e vertically scan thru all the numbers once for each bit position). given any n, u know how many 1's shud be present in msb,2nd msb and so-on. based on this u can find the missing number but this is O(n . (number of bit positions - which is atmost lg(n)) ) still too slow. There is an O(n) solution :) to make the problem easier I have made the assumption that array is sorted :-) since the array is sorted , u know that there will be 2 ^(n-1) 0's followed by 2 ^(n-1) 1's in the MSB(most significatn bit) and 2 ^(n-2) 0's and followed by 2^(n-1) 1's repeated twice. So in general, u have for ith significant bit (i=1 means msb), 2^(n-i) 0s then 2^(n-i) 1s repeated i times. Now just do a binary search. Starting with the msb, extract(i,n/2) . if its 1(supposed to be 0), the missing number is in first half(and msb of missing number is 0). do the same for second msb and so on... comlpexity = O(lg n) , for n=2^k. On 11/17/06, Norbert [EMAIL PROTECTED] wrote: extract(i, n) - i'th bit from position n in an array A - i'th bit of A[n] On 11/17/06, Idris [EMAIL PROTECTED] wrote: Is this extracting i'th bit from a[X] or just extracting Integer from i th index of an array??? if its the later, then get the number and sum up by using OR operation not sure:-) then subtract it from n(n+1)/2=missing Number --~--~-~--~~~---~--~~ 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-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem 4.2 from Introduction to algorithms
neat solution :) On 11/17/06, Dhyanesh (ધયાનેશ) [EMAIL PROTECTED] wrote: 1) Scan through the array counting number of 0s and 1s in MSB, as well as separating the 0s into an array arr0 and 1s into an array arr1 (if you do not want to use extra space you can use splitting around pivot pass of quicksort). 2) You would know how many 0s and 1s should be present in MSB for the number 1 ... n (this would be n/2 and n/2 if n is a power of 2). 3) Either the 0s or 1s would be less, so the missing number has that digit as MSB. 4) Take that bucket i.e. arr0 or arr1 and repeat steps 1 to 3. The complexity of this is n + n/2 + n/4 ... = 2n = O(n). -Dhyanesh On 11/17/06, Arun [EMAIL PROTECTED] wrote: the original problem if the array is unsorted, u can do it, by counting the number of 1's (and hence 0's), in each bit position. ( i.e vertically scan thru all the numbers once for each bit position). given any n, u know how many 1's shud be present in msb,2nd msb and so-on. based on this u can find the missing number but this is O(n . (number of bit positions - which is atmost lg(n)) ) still too slow. There is an O(n) solution :) to make the problem easier I have made the assumption that array is sorted :-) since the array is sorted , u know that there will be 2 ^(n-1) 0's followed by 2 ^(n-1) 1's in the MSB(most significatn bit) and 2 ^(n-2) 0's and followed by 2^(n-1) 1's repeated twice. So in general, u have for ith significant bit (i=1 means msb), 2^(n-i) 0s then 2^(n-i) 1s repeated i times. Now just do a binary search. Starting with the msb, extract(i,n/2) . if its 1(supposed to be 0), the missing number is in first half(and msb of missing number is 0). do the same for second msb and so on... comlpexity = O(lg n) , for n=2^k. On 11/17/06, Norbert [EMAIL PROTECTED] wrote: extract(i, n) - i'th bit from position n in an array A - i'th bit of A[n] On 11/17/06, Idris [EMAIL PROTECTED] wrote: Is this extracting i'th bit from a[X] or just extracting Integer from i th index of an array??? if its the later, then get the number and sum up by using OR operation not sure:-) then subtract it from n(n+1)/2=missing Number --~--~-~--~~~---~--~~ 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-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem
The minimum case would be if you can place all these 4 input rectangles in the vertical plane of the resultant recatangle, and along its diagonal. So suppose dimensions of 4 rectangles are (x1,y1),(x2,y2),(x3,y3),(x4,y4) and of the resultant rectangle is (x,y). Then solution is all (x,y) that satisfy the condition min(x1,y1,x2,y2,x3,y3,x4,y4) = (x,y)^(1/2). Thanks, Satish --~--~-~--~~~---~--~~ 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-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem
Yeah, its from ioi. 1)the solution is on their site. basically there are like 6 ways to put rectangles together given their order and orientation. so, you just loop through all permutations and orientation, and try each of the 6 possibilities(which are shown on their site), and select a minimum. --~--~-~--~~~---~--~~ 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-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem
Can the 4 overlap? From: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] On Behalf Of mohamad momenian Sent: Tuesday, November 07, 2006 4:09 PM To: algogeeks@googlegroups.com Subject: [algogeeks] Problem Hi i have a problem please help me The input of problem is : width and height of 4 rectangle that is between 1,50 and thewe mustcalculate widthand height ofallof rectangles that can coverthis 4 rectangles and it'sareabecome minimum and we can place 4 rectangle vertically or horizontally in the result rectangle --~--~-~--~~~---~--~~ 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-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem
No they can't over lap thank you for your attention On 11/7/06, shisheng li [EMAIL PROTECTED] wrote: Can the 4 overlap? From: algogeeks@googlegroups.com [mailto: algogeeks@googlegroups.com] On Behalf Of mohamad momenianSent: Tuesday, November 07, 2006 4:09 PM To: algogeeks@googlegroups.comSubject: [algogeeks] Problem Hi i have a problem please help me The input of problem is : width and height of 4 rectangle that is between 1,50 and thewe mustcalculate widthand height ofallof rectangles that can coverthis 4 rectangles and it'sareabecome minimum and we can place 4 rectangle vertically or horizontally in the result rectangle --~--~-~--~~~---~--~~ 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-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem
I did not get the point:-we mustcalculate widthand height ofallof rectangles that can coverthis 4 rectangles and it'sareabecome minimumcan you give some example? On 11/7/06, mohamad momenian [EMAIL PROTECTED] wrote: No they can't over lap thank you for your attention On 11/7/06, shisheng li [EMAIL PROTECTED] wrote: Can the 4 overlap? From: algogeeks@googlegroups.com [mailto: algogeeks@googlegroups.com] On Behalf Of mohamad momenianSent: Tuesday, November 07, 2006 4:09 PM To: algogeeks@googlegroups.comSubject: [algogeeks] Problem Hi i have a problem please help me The input of problem is : width and height of 4 rectangle that is between 1,50 and thewe mustcalculate widthand height ofallof rectangles that can coverthis 4 rectangles and it'sareabecome minimum and we can place 4 rectangle vertically or horizontally in the result rectangle --~--~-~--~~~---~--~~ 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-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem
On 11/7/06, Malay Bag [EMAIL PROTECTED] wrote: I did not get the point:- we must calculate width and height of all of rectangles that can cover this 4 rectangles and it's area become minimum can you give some example? I think this problem is from IOI95 http://olympiads.win.tue.nl/ioi95/task/pack.html On 11/7/06, mohamad momenian [EMAIL PROTECTED] wrote: No they can't over lap thank you for your attention On 11/7/06, shisheng li [EMAIL PROTECTED] wrote: Can the 4 overlap? From: algogeeks@googlegroups.com [mailto: [EMAIL PROTECTED] On Behalf Of mohamad momenian Sent: Tuesday, November 07, 2006 4:09 PM To: algogeeks@googlegroups.com Subject: [algogeeks] Problem Hi i have a problem please help me The input of problem is : width and height of 4 rectangle that is between 1,50 and the we must calculate width and height of all of rectangles that can cover this 4 rectangles and it's area become minimum and we can place 4 rectangle vertically or horizontally in the result rectangle --~--~-~--~~~---~--~~ 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-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem
it will be better if u will give at least one sample input and output. On 11/7/06, mohamad momenian [EMAIL PROTECTED] wrote: Hi i have a problem please help me The input of problem is : width and height of 4 rectangle that is between 1,50 and thewe mustcalculate widthand height ofallof rectangles that can coverthis 4 rectangles and it'sareabecome minimum and we can place 4 rectangle vertically or horizontally in the result rectangle [EMAIL PROTECTED] --~--~-~--~~~---~--~~ 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-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem
Yes that is from ioi95 | INPUT.TXT | | OUTPUT.TXT ||___| ||| 1 2 | | 40 || 2 3 | | 4 10 || 3 4 | | 5 8 || 4 5 | || |___| Example input and output On 11/7/06, Manish Garg [EMAIL PROTECTED] wrote: it will be better if u will give at least one sample input and output. On 11/7/06, mohamad momenian [EMAIL PROTECTED] wrote: Hi i have a problem please help me The input of problem is : width and height of 4 rectangle that is between 1,50 and thewe mustcalculate widthand height ofallof rectangles that can coverthis 4 rectangles and it'sareabecome minimum and we can place 4 rectangle vertically or horizontally in the result rectangle [EMAIL PROTECTED] --~--~-~--~~~---~--~~ 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-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem
Hi, 0 x y z N-1 is the requirement. Lei --~--~-~--~~~---~--~~ 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: Problem
Is the solution always x = N-4, y = N-3, z = N-2 ? Suppose we are looking for x and y to minimize the sum. Sum = a[i]*x + a[j]*y, where 0 = i = x j = y = N. It is always bigger than a[i]*x + a[j]*x, because x y and all numbers are positive. We have to have a y so when y is the last one, the sum is the minimum. Similarly, z should be the last one too. Any counterexample? Lei --~--~-~--~~~---~--~~ 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: Problem
This is a brute force method. Is there any method by which we could reduce the no. of computations , or some early checks could be made for reducing the execution time of the algorithm. --~--~-~--~~~---~--~~ 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: Problem
Hi, How come you are saying this as a brute force method. We are storing the results of previous computation in the dp array so that we don't compute the already computed values again and again. I think this is of order n^3. regards Arunachalam. On 4/4/06, learner [EMAIL PROTECTED] wrote: This is a brute force method. Is there any method by which we couldreduce the no. of computations , or some early checks could be made for reducing the execution time of the algorithm.-- ===want to know more about mehttp//ww.livejournal.com/users/arunachalam --~--~-~--~~~---~--~~ 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: problem about MATROID...
anybody can think on this problem? --~--~-~--~~~---~--~~ 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: Problem with recursion on C
Also note that this is one of the worse ways of doing permutations - and that the iterative way uses much less memory (recursion frames) - if u see what I mean. What I was needing is something like this: Given an N number I needed to print the following pattern: if N = 2 A B AA AB BA BB If N = 3 A B C AA AB AC BA BB BC CA CB CC AAA AAB AAC ABA ABB ABC ACA ACB ACC BAA BAB BAC BBA BBB BBC BCA BCB BCC CAA CAB CAC CBA CBB CBC CCA CCB CCC Recursion seems like a better fit. Doesn't it?
[algogeeks] Re: Problem with recursion on C
No. It's illegal in any language. You're missing a closing brace.
[algogeeks] Re: Problem with recursion on C
With STL a simpler solution is possible: #include iostream #include algorithm using namespace std; int main() { int a[] = {1, 2, 3, 4, 5}; do { for (int i = 0; i 5; ++i) cout a[i] ; cout endl; }while(next_permutation(a, a + 5)); return 0; }
[algogeeks] Re: Problem with recursion on C
This is what I came up with: (this is technically C++ though) void f(int i, int j, int k, bool ri, bool rj, bool rk) // ri , rj, rk- whether to recurse on i,j,k or not respectively { if (!ri !rj !rk) return; if ( (i == 0) ri) { f(i,j,k,0,1,1); return; } else if ( (j == 0) rj) { f(i,j,k,ri,0,1); return; } else if ( (k == 0) rk) { f(i,j,k,ri,rj,0); return; } if (ri) { f(i-1,j,k,1,1,1); f(i,j-1,k,0,1,1); f(i,j,k,0,0,1); } else if (rj) { f(i,j-1,k,0,1,1); f(i,j,k,0,0,1); } else if (rk) { for (int p = 0; p = k; ++p) cout i j p endl; } } int main() { f(5,5,5,1,1,1); }