[algogeeks] Re: Can you guys help me how to approach this problem !!!
On Dec 5, 3:14 pm, Harshith wrote: > I might be wrong here but, why can't you just sort the block A[i..j] > it will take O((j-i)log(j-i)) (there are many O(n logn) sorting > algorthms) steps and then just look if they are in sequence trivially > another j-i steps. Don't see what you are getting at. The max-min comparisions to determine if a block is consecutive is O(1), the total steps calculation is due to the number of blocks that need to be checked. > On Dec 3, 1:33 am, Vinoth Kumar wrote: > > > > > I kinda need the worst case also to be in nlogn. > > Any ideas guys ? > > > -- Vinod > > > On Dec 2, 11:02 pm, Geoffrey Summerhayes wrote: > > > > On Dec 2, 10:42 am, Geoffrey Summerhayes wrote: > > > > > It's a binary tree, [ 7 3 4 1 2 6 5 8] has children > > > > [ 7 3 4 1 2 6 5] and [ 3 4 1 2 6 5 8], all the way > > > > down to [ 7 3] [3 4] [4 1] ... > > > > > If you start at the bottom keeping track of min and max > > > > for each node, if max-min == node length - 1 the node > > > > if conseq. then it's just a matter of combining node > > > > together and working up the tree > > > > Darn! > > > > Total steps= n*n/2 - n/2 > > > > Anybody have a math trick? > > > > -- > > > Geoff- 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Can you guys help me how to approach this problem !!!
I think this problem can be reduced to: For a particular element in Superblock, find all the subblocks which contains next element or the NULL. For example, take first element i.e. 7, we need to find all the blocks which has 7 and has 3 or NULL as its next element in the subblock. Now suppose in first iteration, we found n1 subblocks which has either 7 or 7 and 3 (consecutively), If the next element is NULL, we include this subblock in final count otherwise we keep these subblocks for next iteration because subblock which are bad for first element are not good for other elements also. Thanks, On Sun, Dec 6, 2009 at 9:11 AM, Aditya Shankar wrote: > Hi, >Consider the sequence 1,2,3,4,5,6...,n. There are n^2 blocks, so the > question may not be correct. > > > Regards > Aditya Shankar > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Dinesh Bansal The Law of Win says, "Let's not do it your way or my way; let's do it the best way." -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Can you guys help me how to approach this problem !!!
Hi, Consider the sequence 1,2,3,4,5,6...,n. There are n^2 blocks, so the question may not be correct. Regards Aditya Shankar -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Can you guys help me how to approach this problem !!!
I might be wrong here but, why can't you just sort the block A[i..j] it will take O((j-i)log(j-i)) (there are many O(n logn) sorting algorthms) steps and then just look if they are in sequence trivially another j-i steps. On Dec 3, 1:33 am, Vinoth Kumar wrote: > I kinda need the worst case also to be in nlogn. > Any ideas guys ? > > -- Vinod > > On Dec 2, 11:02 pm, Geoffrey Summerhayes wrote: > > > > > On Dec 2, 10:42 am, Geoffrey Summerhayes wrote: > > > > It's a binary tree, [ 7 3 4 1 2 6 5 8] has children > > > [ 7 3 4 1 2 6 5] and [ 3 4 1 2 6 5 8], all the way > > > down to [ 7 3] [3 4] [4 1] ... > > > > If you start at the bottom keeping track of min and max > > > for each node, if max-min == node length - 1 the node > > > if conseq. then it's just a matter of combining node > > > together and working up the tree > > > Darn! > > > Total steps= n*n/2 - n/2 > > > Anybody have a math trick? > > > -- > > Geoff -- 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: Can you guys help me how to approach this problem !!!
I kinda need the worst case also to be in nlogn. Any ideas guys ? -- Vinod On Dec 2, 11:02 pm, Geoffrey Summerhayes wrote: > On Dec 2, 10:42 am, Geoffrey Summerhayes wrote: > > > > > It's a binary tree, [ 7 3 4 1 2 6 5 8] has children > > [ 7 3 4 1 2 6 5] and [ 3 4 1 2 6 5 8], all the way > > down to [ 7 3] [3 4] [4 1] ... > > > If you start at the bottom keeping track of min and max > > for each node, if max-min == node length - 1 the node > > if conseq. then it's just a matter of combining node > > together and working up the tree > > Darn! > > Total steps= n*n/2 - n/2 > > Anybody have a math trick? > > -- > Geoff -- 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: Can you guys help me how to approach this problem !!!
On Dec 2, 10:42 am, Geoffrey Summerhayes wrote: > > It's a binary tree, [ 7 3 4 1 2 6 5 8] has children > [ 7 3 4 1 2 6 5] and [ 3 4 1 2 6 5 8], all the way > down to [ 7 3] [3 4] [4 1] ... > > If you start at the bottom keeping track of min and max > for each node, if max-min == node length - 1 the node > if conseq. then it's just a matter of combining node > together and working up the tree Darn! Total steps= n*n/2 - n/2 Anybody have a math trick? -- Geoff -- 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: Can you guys help me how to approach this problem !!!
On Dec 2, 6:45 am, Vinoth Kumar wrote: > These are the steps for the O(n^2) solution > > n=length of A > for each subarray A[i,j] where j>i > min=min(A[i,j]) > max=max(A[i,j]) > if(max - min==size (A[i,j]) print A[i,j] > > min[A[i,j]]=min( A[j], min(A[i,j-1]) > similar one for max > > Note: > A[i,j] = A[i],A[i+1]A[j] > > I was wondering how to do the same problem in O(nlogn) > It's a binary tree, [ 7 3 4 1 2 6 5 8] has children [ 7 3 4 1 2 6 5] and [ 3 4 1 2 6 5 8], all the way down to [ 7 3] [3 4] [4 1] ... If you start at the bottom keeping track of min and max for each node, if max-min == node length - 1 the node if conseq. then it's just a matter of combining node together and working up the tree -- Geoff -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Can you guys help me how to approach this problem !!!
check this if How To Install Dreamweaver CS3 In Ubuntu Hardyhttp://eaziweb.blogspot.com/2009/12/how-to-install-dreamweaver-cs3-in.html Regards Shahzeb Farooq Chohan Software Engineer Cogilent Solutions Get your new Email address! Grab the Email name you've always wanted before someone else does! http://mail.promotions.yahoo.com/newdomains/aa/ -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Can you guys help me how to approach this problem !!!
These are the steps for the O(n^2) solution n=length of A for each subarray A[i,j] where j>i min=min(A[i,j]) max=max(A[i,j]) if(max - min==size (A[i,j]) print A[i,j] min[A[i,j]]=min( A[j], min(A[i,j-1]) similar one for max Note: A[i,j] = A[i],A[i+1]A[j] I was wondering how to do the same problem in O(nlogn) -- Vinod On Wed, Dec 2, 2009 at 11:48 AM, ranjmis wrote: > Vinod. Can you please mention steps for the O(n^2) solution that you > have thought of. > > On Dec 2, 9:50 am, Vinoth Kumar wrote: > > No need for the code guys. > > Can u give me a algo or pseudo code for this problem. > > I can think of a soln of O(n^2) but i need a algo for O(nlogn) > > > > > > > > On Wed, Dec 2, 2009 at 2:06 AM, NickLarsen wrote: > > > That doesn't quite get it, try the input [ 7 3 4 2 1 6 5 8] and your > > > idea would miss [3 4 2] > > > > > On Dec 1, 10:10 am, sharad kumar wrote: > > > > find out the subseq which are consecttive > > > > concatenate them at each level to get the entire set. > > > > > > On Tue, Dec 1, 2009 at 12:03 PM, Vinoth Kumar > > > > wrote: > > > > > > > Given an array A which holds a permutation of 1,2,...,n. A > sub-block A > > > > > [i..j] of an array A > > > > > is called a valid block if all the numbers appearing in A[i..j] are > > > > > consecutive numbers (may not be in order. > > > > > > > Given an array A= [ 7 3 4 1 2 6 5 8] > > > > > the valid blocks are [3 4], [1,2], [6,5], [3 4 1 2], [3 4 1 2 6 5], > [7 > > > > > 3 4 1 2 6 5], [7 3 4 1 2 6 5 8] > > > > > > > Give an O( n log n) algorithm to count the number of valid blocks. > > > > > > > -- Vinod > > > > > > > -- > > > > > > > You received this message because you are subscribed to the Google > > > Groups > > > > > "Algorithm Geeks" group. > > > > > To post to this group, send email to algoge...@googlegroups.com. > > > > > To unsubscribe from this group, send email to > > > > > algogeeks+unsubscr...@googlegroups.com > > > > > > > > > > > . > > > > > For more options, visit this group at > > > > >http://groups.google.com/group/algogeeks?hl=en. > > > > > -- > > > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to algoge...@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com > > > > > > . > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > > > -- > > Cheers, > > Vinod > > -- > > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Can you guys help me how to approach this problem !!!
Vinod. Can you please mention steps for the O(n^2) solution that you have thought of. On Dec 2, 9:50 am, Vinoth Kumar wrote: > No need for the code guys. > Can u give me a algo or pseudo code for this problem. > I can think of a soln of O(n^2) but i need a algo for O(nlogn) > > > > On Wed, Dec 2, 2009 at 2:06 AM, NickLarsen wrote: > > That doesn't quite get it, try the input [ 7 3 4 2 1 6 5 8] and your > > idea would miss [3 4 2] > > > On Dec 1, 10:10 am, sharad kumar wrote: > > > find out the subseq which are consecttive > > > concatenate them at each level to get the entire set. > > > > On Tue, Dec 1, 2009 at 12:03 PM, Vinoth Kumar > > > wrote: > > > > > Given an array A which holds a permutation of 1,2,...,n. A sub-block A > > > > [i..j] of an array A > > > > is called a valid block if all the numbers appearing in A[i..j] are > > > > consecutive numbers (may not be in order. > > > > > Given an array A= [ 7 3 4 1 2 6 5 8] > > > > the valid blocks are [3 4], [1,2], [6,5], [3 4 1 2], [3 4 1 2 6 5], [7 > > > > 3 4 1 2 6 5], [7 3 4 1 2 6 5 8] > > > > > Give an O( n log n) algorithm to count the number of valid blocks. > > > > > -- Vinod > > > > > -- > > > > > You received this message because you are subscribed to the Google > > Groups > > > > "Algorithm Geeks" group. > > > > To post to this group, send email to algoge...@googlegroups.com. > > > > To unsubscribe from this group, send email to > > > > algogeeks+unsubscr...@googlegroups.com > > > > > > . > > > > For more options, visit this group at > > > >http://groups.google.com/group/algogeeks?hl=en. > > > -- > > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Cheers, > Vinod -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Can you guys help me how to approach this problem !!!
No need for the code guys. Can u give me a algo or pseudo code for this problem. I can think of a soln of O(n^2) but i need a algo for O(nlogn) On Wed, Dec 2, 2009 at 2:06 AM, NickLarsen wrote: > That doesn't quite get it, try the input [ 7 3 4 2 1 6 5 8] and your > idea would miss [3 4 2] > > On Dec 1, 10:10 am, sharad kumar wrote: > > find out the subseq which are consecttive > > concatenate them at each level to get the entire set. > > > > On Tue, Dec 1, 2009 at 12:03 PM, Vinoth Kumar > > wrote: > > > > > > > > > Given an array A which holds a permutation of 1,2,...,n. A sub-block A > > > [i..j] of an array A > > > is called a valid block if all the numbers appearing in A[i..j] are > > > consecutive numbers (may not be in order. > > > > > Given an array A= [ 7 3 4 1 2 6 5 8] > > > the valid blocks are [3 4], [1,2], [6,5], [3 4 1 2], [3 4 1 2 6 5], [7 > > > 3 4 1 2 6 5], [7 3 4 1 2 6 5 8] > > > > > Give an O( n log n) algorithm to count the number of valid blocks. > > > > > -- Vinod > > > > > -- > > > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to algoge...@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com > > > > . > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > -- > > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > -- Cheers, Vinod -- 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: Can you guys help me how to approach this problem !!!
That doesn't quite get it, try the input [ 7 3 4 2 1 6 5 8] and your idea would miss [3 4 2] On Dec 1, 10:10 am, sharad kumar wrote: > find out the subseq which are consecttive > concatenate them at each level to get the entire set. > > On Tue, Dec 1, 2009 at 12:03 PM, Vinoth Kumar > wrote: > > > > > Given an array A which holds a permutation of 1,2,...,n. A sub-block A > > [i..j] of an array A > > is called a valid block if all the numbers appearing in A[i..j] are > > consecutive numbers (may not be in order. > > > Given an array A= [ 7 3 4 1 2 6 5 8] > > the valid blocks are [3 4], [1,2], [6,5], [3 4 1 2], [3 4 1 2 6 5], [7 > > 3 4 1 2 6 5], [7 3 4 1 2 6 5 8] > > > Give an O( n log n) algorithm to count the number of valid blocks. > > > -- Vinod > > > -- > > > 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 > .com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
