[algogeeks] How many ways n points can be connected
Hi All, can there be a formulato which we can estimate how many ways (n-1) lines can connect n points in the same way how many ways n lines can connect n points and so onthere is one way that we store the information in adjacency list or in adjacency matrixand will check for the same for every event in sample space.is there any other way that can optimize this calculation or may it possible that we can directly calculate it. . rspr -- 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]
hi, I am trying the following problem, but not getting the logic... http://www.codechef.com/problems/CHEFBRO -- 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: How many ways n points can be connected
Let's start with n-1 lines Build up the edges like this: Start by connecting any point to any other point. There are n*(n-1)/2 ways to do this. Then add edges from a connect point to an unconnected point. For the first edge added this way, there are 2*(n-2) options. After that it is 3*(n-3), 4*(n-4)...(n-1)*1. But that generates all of the orders in which the edges can be added, so you have to divide out (n-1)!. If you simplify that out, you get n!/2. For more than n-1 lines you need to specify the constraints. Can there be multiple edges connecting the same pair of points? Either way, look for the pattern in the number of ways the edges can be selected and multiply it out. Don On Feb 7, 10:03 pm, rspr ravishanker@gmail.com wrote: Hi All, can there be a formulato which we can estimate how many ways (n-1) lines can connect n points in the same way how many ways n lines can connect n points and so onthere is one way that we store the information in adjacency list or in adjacency matrixand will check for the same for every event in sample space.is there any other way that can optimize this calculation or may it possible that we can directly calculate it. . rspr -- 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] contest about to begin http://www.spoj.pl/ARHN/ in 5 minutes
http://www.spoj.pl/ARHN/ 10,000 at stake -- 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: contest about to begin http://www.spoj.pl/ARHN/ in 5 minutes
On Wed, Feb 8, 2012 at 8:53 PM, Shalini Sah mischievous@gmail.comwrote: http://www.spoj.pl/ARHN/ 10,000 at stake -- 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: How many ways n points can be connected
@Don: I had the similar approach, but I didn't think of dividing by (n-1)! Why is this needed? -- I think this is to avoid the cases in which, just the order of picking the nodes is different and lines drawn are same. How is this (n-1)! -- i might be missing the the very basic thing.. plz correct. -- 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/-/BMUax98JaNAJ. 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: Find all longest increasing subsequence of length k
@atul , its application of LIS LCS problem , isn't it ? Thanks Shashank -- 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/-/x2c4hvfZCuUJ. 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: How many ways n points can be connected
The approach of adding one edge connecting a connected point to an unconnected point will produce every possible set of n-1 edges which connect all the points, but it will include duplicates, because it can generate all of those edges in any order. There are (n-1)! possible orders that the same set of edges can be generated, so to get the number of unique sets of edges, you have to divide by (n-1)!. Don On Feb 8, 11:43 am, sravanreddy001 sravanreddy...@gmail.com wrote: @Don: I had the similar approach, but I didn't think of dividing by (n-1)! Why is this needed? -- I think this is to avoid the cases in which, just the order of picking the nodes is different and lines drawn are same. How is this (n-1)! -- i might be missing the the very basic thing.. plz correct. -- 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: How many ways n points can be connected
@Don: thank you. each possible arrangement of lines can be done in (n-1)! ways.. and only one is needed of 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/-/WlW-U-4MBUgJ. 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: doubt about macro.......
@Dave: you mentioned that there is a way to fix the issue caused by calleing swap(t,u,int) -- how can we fix this in preprocessor directive? -- 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/-/aG0npils_E8J. 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: doubt about macro.......
@Sravanreddy001: Add curly braces...
swap(a,b,c) {c t;t=a;a=b;b=t;}
Dave
On Feb 8, 1:28 pm, sravanreddy001 sravanreddy...@gmail.com wrote:
@Dave:
you mentioned that there is a way to fix the issue caused by calleing
swap(t,u,int) -- how can we fix this in preprocessor directive?
--
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] How many ways n points can be connected
Here is an DP solution: (consider only simple graph, with at most 1 line between any 2 distinct points, and no point connect to itself) Suppose f(n,m) is the number of ways m lines can connect n points. Then f(n,m) = 0 when m n-1 or m n(n-1)/2; For graph with n vertices and m edges (connected or disconnected), the overall count is C(n*(n-1)/2, m). There are 2 types: 1) connected: The number is f(n,m) that to be computed. 2) disconnected: Consider the connected component containing vertex 1, suppose it has n' vertices and m' edges. Then: a. there are C(n-1, n'-1) ways to select the points in the component b. there f(n',m') ways to connect the n' points using m' edges c. the rest n-n' vertices and m-m' edges can be arbitrarily placed. In summary, f(n,m) = C(n*(n-1)/2, m) - ∑(∑C(n-1, n'-1) * f(n', m') * C((n-n')*(n-n'-1)/2, m-m') for m' in [n'-1,m]) for n' in [1, n-1] (C(N, K) is binomial coefficient choosing K from N) The overall time complexity is O(m^2*n^2), and space complexity is O(mn) On 2012-2-8 12:03, rspr wrote: Hi All, can there be a formulato which we can estimate how many ways (n-1) lines can connect n points in the same way how many ways n lines can connect n points and so onthere is one way that we store the information in adjacency list or in adjacency matrixand will check for the same for every event in sample space.is there any other way that can optimize this calculation or may it possible that we can directly calculate it. . rspr -- 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: Find all longest increasing subsequence of length k
@Shashank: its LIS problem but desired complexity is : O(k*n*logn) On Wed, Feb 8, 2012 at 11:51 PM, WgpShashank shashank7andr...@gmail.comwrote: @atul , its application of LIS LCS problem , isn't it ? Thanks Shashank -- 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/-/x2c4hvfZCuUJ. 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] determining if frequency is greater than n/2
Hello everyone, suppose we have an array of size n and a number, say x, and we have to determine whether the number x is present in the array more then n/2 times or not? can we have an O(log n) algo for determining it..?..pls help...!!! -- -- Prakhar Jain IIIT Allahabad B.Tech IT 3rd Year Mob no: +91 9454992196 E-mail: rit2009...@iiita.ac.in jprakha...@gmail.com -- 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] determining if frequency is greater than n/2
http://www.geeksforgeeks.org/archives/503 here is O(n) soln. On Thu, Feb 9, 2012 at 1:15 AM, Prakhar Jain jprakha...@gmail.com wrote: Hello everyone, suppose we have an array of size n and a number, say x, and we have to determine whether the number x is present in the array more then n/2 times or not? can we have an O(log n) algo for determining it..?..pls help...!!! -- -- Prakhar Jain IIIT Allahabad B.Tech IT 3rd Year Mob no: +91 9454992196 E-mail: rit2009...@iiita.ac.in jprakha...@gmail.com -- 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] spoj
I have been doing this question for a time but was not able to solve it. It is based josephus problem ? Has anybody any idea http://www.spoj.pl/problems/WTK/ -- *UTKARSH SRIVASTAV CSE-3 B-Tech 3rd Year @MNNIT ALLAHABAD* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks]
Question: You are given 100 stations and distance between each adjacent stations. Now you have to select 10 stations(means 10 hops) among those 100 stations in such a way that maximum of distance between any 2 hops will be minimised. By default 1 and 100 stations are selected , so you need to choose only 8 more stations.??? -- 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.
