Re: [algogeeks] Re: Find the maximum boxes which can fit each other?
@saurabh : I didn't understand. will u give an ex:. if it is a graph(not tree), how can u find longest path in O(n). On Thu, Apr 5, 2012 at 5:45 PM, Doom wrote: > @Don: Any ideas which oppose the above proposed solution? > > > On Saturday, 24 March 2012 21:52:49 UTC+5:30, Don wrote: >> >> Build a graph in which each box is a vertex and there is an edge from >> A to B if B can fit inside A. Then use the longest path algorithm to >> find the solution. >> Don >> >> On Mar 24, 1:55 am, Ratan wrote: >> > You are given a lot of cuboid boxes with different length, breadth and >> > height. You need to find the maximum subset which can fit into each >> > other. >> > For example: >> > If Box A has LBH as 7 8 9 >> > If Box B has LBH as 5 6 8 >> > If Box C has LBH as 5 8 7 >> > If Box D has LBH as 4 4 4 >> > then answer is A,B,D >> > >> > A box can fit into another only and only if all dimensions of that is >> > less than the bigger box. Also Rotation of boxes is not possible... >> > >> > can ny1 suggest a good algo for this? >> > >> > -- >> > -- >> > Ratan | 3rd Year | Information Technology | NIT ALLAHABAD > > -- > 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/-/C1yQ1v_QAboJ. > > 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: Find the maximum boxes which can fit each other?
@Don: Any ideas which oppose the above proposed solution? On Saturday, 24 March 2012 21:52:49 UTC+5:30, Don wrote: > > Build a graph in which each box is a vertex and there is an edge from > A to B if B can fit inside A. Then use the longest path algorithm to > find the solution. > Don > > On Mar 24, 1:55 am, Ratan wrote: > > You are given a lot of cuboid boxes with different length, breadth and > > height. You need to find the maximum subset which can fit into each > > other. > > For example: > > If Box A has LBH as 7 8 9 > > If Box B has LBH as 5 6 8 > > If Box C has LBH as 5 8 7 > > If Box D has LBH as 4 4 4 > > then answer is A,B,D > > > > A box can fit into another only and only if all dimensions of that is > > less than the bigger box. Also Rotation of boxes is not possible... > > > > can ny1 suggest a good algo for this? > > > > -- > > -- > > Ratan | 3rd Year | Information Technology | NIT ALLAHABAD -- 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/-/C1yQ1v_QAboJ. 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 the maximum boxes which can fit each other?
What is wrong with atul's solution of longest decreasing subsequece on length after sorting on area? I think the relationship is transitive as well. e.g. box a fits inside b. box b fits inside c by transitivity, box a fits inside c. Isn't this fine? On Saturday, 24 March 2012 22:25:33 UTC+5:30, Don wrote: > > There is more to it than a longest increasing subsequence because the > "greater than" relationship is not transitive. > Don > > On Mar 24, 3:05 am, atul anand wrote: > > ok you need to put box into a box... > > so first requirnment willl be to sort on the basis of area of box. > > after this bcoz you are adding one box into another...the box you are > > putting inside big box ..shud have base length less than a big box or it > > wont fit in...even if its area is smaller.. > > now we reduced this problem of finding longest inc subsequence on the > basis > > of base length. > > On 24 Mar 2012 13:14, "Ratan" wrote: > > > > > > > > > @atul can u plzz describe in detail the algo of modified subsequence > > > prob used here i m nt able to get it ... though tried a lot > > > > > On Sat, Mar 24, 2012 at 1:05 PM, atul anand > > > wrote: > > > > it is modified longest increasing subsequence problem.. > > > > > > On 24 Mar 2012 12:26, "Ratan" wrote: > > > > > >> You are given a lot of cuboid boxes with different length, breadth > and > > > >> height. You need to find the maximum subset which can fit into each > > > >> other. > > > >> For example: > > > >> If Box A has LBH as 7 8 9 > > > >> If Box B has LBH as 5 6 8 > > > >> If Box C has LBH as 5 8 7 > > > >> If Box D has LBH as 4 4 4 > > > >> then answer is A,B,D > > > > > >> A box can fit into another only and only if all dimensions of that > is > > > >> less than the bigger box. Also Rotation of boxes is not possible... > > > > > >> can ny1 suggest a good algo for this? > > > > > >> -- > > > >> -- > > > >> Ratan | 3rd Year | Information Technology | 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. > > > > > -- > > > -- > > > Ratan | 3rd Year | Information Technology | 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.- Hide quoted text - > > > > - Show quoted text - -- 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/-/a06lUGOcKvgJ. 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 the maximum boxes which can fit each other?
it depends on how you define the problem.finding the longest path in a graph required O(N) where n is the total number of states.Dons solution is not npc if i understand it right On 4/1/12, bharat b wrote: > @don : but, finding longest path in a graph is NPC ... we should comeup > with better solution > > On Sat, Mar 24, 2012 at 10:25 PM, Don wrote: > >> There is more to it than a longest increasing subsequence because the >> "greater than" relationship is not transitive. >> Don >> >> On Mar 24, 3:05 am, atul anand wrote: >> > ok you need to put box into a box... >> > so first requirnment willl be to sort on the basis of area of box. >> > after this bcoz you are adding one box into another...the box you are >> > putting inside big box ..shud have base length less than a big box or it >> > wont fit in...even if its area is smaller.. >> > now we reduced this problem of finding longest inc subsequence on the >> basis >> > of base length. >> > On 24 Mar 2012 13:14, "Ratan" wrote: >> > >> > >> > >> > > @atul can u plzz describe in detail the algo of modified subsequence >> > > prob used here i m nt able to get it ... though tried a lot >> > >> > > On Sat, Mar 24, 2012 at 1:05 PM, atul anand >> > > wrote: >> > > > it is modified longest increasing subsequence problem.. >> > >> > > > On 24 Mar 2012 12:26, "Ratan" wrote: >> > >> > > >> You are given a lot of cuboid boxes with different length, breadth >> and >> > > >> height. You need to find the maximum subset which can fit into each >> > > >> other. >> > > >> For example: >> > > >> If Box A has LBH as 7 8 9 >> > > >> If Box B has LBH as 5 6 8 >> > > >> If Box C has LBH as 5 8 7 >> > > >> If Box D has LBH as 4 4 4 >> > > >> then answer is A,B,D >> > >> > > >> A box can fit into another only and only if all dimensions of that >> is >> > > >> less than the bigger box. Also Rotation of boxes is not possible... >> > >> > > >> can ny1 suggest a good algo for this? >> > >> > > >> -- >> > > >> -- >> > > >> Ratan | 3rd Year | Information Technology | 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. >> > >> > > -- >> > > -- >> > > Ratan | 3rd Year | Information Technology | 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.- 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. >> >> > > > -- > > **Regards > * > * > > Bharat B | M.Tech II | C.S.E | IITM > * > * > *Ph: +91 8056127652* > > -- > 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 blog:geekinessthecoolway.blogspot.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] Re: Find the maximum boxes which can fit each other?
@don : but, finding longest path in a graph is NPC ... we should comeup with better solution On Sat, Mar 24, 2012 at 10:25 PM, Don wrote: > There is more to it than a longest increasing subsequence because the > "greater than" relationship is not transitive. > Don > > On Mar 24, 3:05 am, atul anand wrote: > > ok you need to put box into a box... > > so first requirnment willl be to sort on the basis of area of box. > > after this bcoz you are adding one box into another...the box you are > > putting inside big box ..shud have base length less than a big box or it > > wont fit in...even if its area is smaller.. > > now we reduced this problem of finding longest inc subsequence on the > basis > > of base length. > > On 24 Mar 2012 13:14, "Ratan" wrote: > > > > > > > > > @atul can u plzz describe in detail the algo of modified subsequence > > > prob used here i m nt able to get it ... though tried a lot > > > > > On Sat, Mar 24, 2012 at 1:05 PM, atul anand > > > wrote: > > > > it is modified longest increasing subsequence problem.. > > > > > > On 24 Mar 2012 12:26, "Ratan" wrote: > > > > > >> You are given a lot of cuboid boxes with different length, breadth > and > > > >> height. You need to find the maximum subset which can fit into each > > > >> other. > > > >> For example: > > > >> If Box A has LBH as 7 8 9 > > > >> If Box B has LBH as 5 6 8 > > > >> If Box C has LBH as 5 8 7 > > > >> If Box D has LBH as 4 4 4 > > > >> then answer is A,B,D > > > > > >> A box can fit into another only and only if all dimensions of that > is > > > >> less than the bigger box. Also Rotation of boxes is not possible... > > > > > >> can ny1 suggest a good algo for this? > > > > > >> -- > > > >> -- > > > >> Ratan | 3rd Year | Information Technology | 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. > > > > > -- > > > -- > > > Ratan | 3rd Year | Information Technology | 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.- 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. > > -- **Regards * * Bharat B | M.Tech II | C.S.E | IITM * * *Ph: +91 8056127652* -- 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: Find the maximum boxes which can fit each other?
There is more to it than a longest increasing subsequence because the "greater than" relationship is not transitive. Don On Mar 24, 3:05 am, atul anand wrote: > ok you need to put box into a box... > so first requirnment willl be to sort on the basis of area of box. > after this bcoz you are adding one box into another...the box you are > putting inside big box ..shud have base length less than a big box or it > wont fit in...even if its area is smaller.. > now we reduced this problem of finding longest inc subsequence on the basis > of base length. > On 24 Mar 2012 13:14, "Ratan" wrote: > > > > > @atul can u plzz describe in detail the algo of modified subsequence > > prob used here i m nt able to get it ... though tried a lot > > > On Sat, Mar 24, 2012 at 1:05 PM, atul anand > > wrote: > > > it is modified longest increasing subsequence problem.. > > > > On 24 Mar 2012 12:26, "Ratan" wrote: > > > >> You are given a lot of cuboid boxes with different length, breadth and > > >> height. You need to find the maximum subset which can fit into each > > >> other. > > >> For example: > > >> If Box A has LBH as 7 8 9 > > >> If Box B has LBH as 5 6 8 > > >> If Box C has LBH as 5 8 7 > > >> If Box D has LBH as 4 4 4 > > >> then answer is A,B,D > > > >> A box can fit into another only and only if all dimensions of that is > > >> less than the bigger box. Also Rotation of boxes is not possible... > > > >> can ny1 suggest a good algo for this? > > > >> -- > > >> -- > > >> Ratan | 3rd Year | Information Technology | 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. > > > -- > > -- > > Ratan | 3rd Year | Information Technology | 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.- 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: Find the maximum boxes which can fit each other?
Build a graph in which each box is a vertex and there is an edge from A to B if B can fit inside A. Then use the longest path algorithm to find the solution. Don On Mar 24, 1:55 am, Ratan wrote: > You are given a lot of cuboid boxes with different length, breadth and > height. You need to find the maximum subset which can fit into each > other. > For example: > If Box A has LBH as 7 8 9 > If Box B has LBH as 5 6 8 > If Box C has LBH as 5 8 7 > If Box D has LBH as 4 4 4 > then answer is A,B,D > > A box can fit into another only and only if all dimensions of that is > less than the bigger box. Also Rotation of boxes is not possible... > > can ny1 suggest a good algo for this? > > -- > -- > Ratan | 3rd Year | Information Technology | 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.
