Re: [algogeeks] Maximum subset of cuboid boxes
@Senthilnathan: topological sort can be done in O(n) and we can solve LIS in O(n^2) (i'm not sure if the nlogn approach for LIS can be applied here) On 6/26/10, Senthilnathan Maadasamy wrote: > @Amir : What is the complexity of your approach? > > -- > 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.
Re: [algogeeks] Maximum subset of cuboid boxes
@Amir : What is the complexity of your approach? -- 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] Maximum subset of cuboid boxes
imagine the DAG where there is an edge from box i to box j iff box i fits in box j then applying topological sort you just need to find the longest path if you define operator "<" as if left operand fits in the right operand you just need to find the LIS which is the longest path On 6/23/10, Bhanu Pratap Singh wrote: > Hi Raj, > > What if the boxes are given in some different order. The solution given > depends very much on the order in which boxes are given. > > On Wed, Jun 23, 2010 at 2:10 PM, Raj N wrote: > >> Given a lot of cuboid boxes with different length, breadth and height. >> We need to find the maximum subset which can fit into each other. >> >> For example: >> If Box 1 has LBH as 7 8 9 >> If Box 2 has LBH as 5 6 8 >> If Box 3 has LBH as 5 8 7 >> If Box 4 has LBH as 4 4 4 >> >> then answer is 1,2,4 >> >> A box can fit into another only and only if all dimensions of that is >> less than the bigger box.Rotation of boxes is not possible. >> >> My approach: >> >> Constructing trees... >> Box 1 dim: 7,8,9 Make it as root1. The root also has a counter >> associated with it. Now count1=1. >> Then Box 2 dim: 5,6,8 < 7,8,9. Make it as a left child of root1 and >> count1=2. >> Box 3 dim: 5,8,7 doesn't fit in any and hence make it a tree by itself >> i.e root2 its count2=1. >> Box 4 dim: 4,4,4 it can be made as the left child of box 2 as well as >> Box 3. >> count1=3, count2=2. >> Print the reverse inorder traversal of the highest counter valued >> tree. >> >> Please correct me if I'm wrong. >> >> -- >> 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. >> >> > > > -- > Regards > Bhanu > Mobile +91 9886738496 > > -- > 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.
Re: [algogeeks] Maximum subset of cuboid boxes
No it doesn't. For example lets take this order: If Box 1 has LBH as 5 8 7 If Box 2 has LBH as 5 6 8 If Box 3 has LBH as 4 4 4 If Box 4 has LBH as 7 8 9 Box 1 dim: 5,8,7. It becomes root1. count1=1. Box2 dim: 5,6,8 cannot be made part of root1. So it becomes root2. count2=1 Box 3 dim: 4,4,4. It can be made as the left child of both root1 and root2. count1=2 count2=2 Box 4 dim: 7,8,9. It cannot be made part of the first tree, so root2->right will be box4. count2=3. As count2>count1, print the reverse inorder traversal of tree2 output will be: 4,2,3 On Wed, Jun 23, 2010 at 9:33 PM, Bhanu Pratap Singh wrote: > Hi Raj, > > What if the boxes are given in some different order. The solution given > depends very much on the order in which boxes are given. > > > On Wed, Jun 23, 2010 at 2:10 PM, Raj N wrote: > >> Given a lot of cuboid boxes with different length, breadth and height. >> We need to find the maximum subset which can fit into each other. >> >> For example: >> If Box 1 has LBH as 7 8 9 >> If Box 2 has LBH as 5 6 8 >> If Box 3 has LBH as 5 8 7 >> If Box 4 has LBH as 4 4 4 >> >> then answer is 1,2,4 >> >> A box can fit into another only and only if all dimensions of that is >> less than the bigger box.Rotation of boxes is not possible. >> >> My approach: >> >> Constructing trees... >> Box 1 dim: 7,8,9 Make it as root1. The root also has a counter >> associated with it. Now count1=1. >> Then Box 2 dim: 5,6,8 < 7,8,9. Make it as a left child of root1 and >> count1=2. >> Box 3 dim: 5,8,7 doesn't fit in any and hence make it a tree by itself >> i.e root2 its count2=1. >> Box 4 dim: 4,4,4 it can be made as the left child of box 2 as well as >> Box 3. >> count1=3, count2=2. >> Print the reverse inorder traversal of the highest counter valued >> tree. >> >> Please correct me if I'm wrong. >> >> -- >> 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. >> >> > > > -- > Regards > Bhanu > Mobile +91 9886738496 > > > > -- > 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.
Re: [algogeeks] Maximum subset of cuboid boxes
Hi Raj, What if the boxes are given in some different order. The solution given depends very much on the order in which boxes are given. On Wed, Jun 23, 2010 at 2:10 PM, Raj N wrote: > Given a lot of cuboid boxes with different length, breadth and height. > We need to find the maximum subset which can fit into each other. > > For example: > If Box 1 has LBH as 7 8 9 > If Box 2 has LBH as 5 6 8 > If Box 3 has LBH as 5 8 7 > If Box 4 has LBH as 4 4 4 > > then answer is 1,2,4 > > A box can fit into another only and only if all dimensions of that is > less than the bigger box.Rotation of boxes is not possible. > > My approach: > > Constructing trees... > Box 1 dim: 7,8,9 Make it as root1. The root also has a counter > associated with it. Now count1=1. > Then Box 2 dim: 5,6,8 < 7,8,9. Make it as a left child of root1 and > count1=2. > Box 3 dim: 5,8,7 doesn't fit in any and hence make it a tree by itself > i.e root2 its count2=1. > Box 4 dim: 4,4,4 it can be made as the left child of box 2 as well as > Box 3. > count1=3, count2=2. > Print the reverse inorder traversal of the highest counter valued > tree. > > Please correct me if I'm wrong. > > -- > 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. > > -- Regards Bhanu Mobile +91 9886738496 -- 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] Maximum subset of cuboid boxes
Given a lot of cuboid boxes with different length, breadth and height. We need to find the maximum subset which can fit into each other. For example: If Box 1 has LBH as 7 8 9 If Box 2 has LBH as 5 6 8 If Box 3 has LBH as 5 8 7 If Box 4 has LBH as 4 4 4 then answer is 1,2,4 A box can fit into another only and only if all dimensions of that is less than the bigger box.Rotation of boxes is not possible. My approach: Constructing trees... Box 1 dim: 7,8,9 Make it as root1. The root also has a counter associated with it. Now count1=1. Then Box 2 dim: 5,6,8 < 7,8,9. Make it as a left child of root1 and count1=2. Box 3 dim: 5,8,7 doesn't fit in any and hence make it a tree by itself i.e root2 its count2=1. Box 4 dim: 4,4,4 it can be made as the left child of box 2 as well as Box 3. count1=3, count2=2. Print the reverse inorder traversal of the highest counter valued tree. Please correct me if I'm wrong. -- 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.
