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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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
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.
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.
