Re: [algogeeks] Algorithm to determine the largest number of envelopes that can be nested inside one another.
You can order the envelopes by area!
Wladimir Araujo Tavares
http://www.si.ufc.br/~wladimir <http://www.si.ufc.br/%7Ewladimir/>
"Fiz uma faculdade! Só não fiz a segunda porque acabaram os tijolos."
On Tue, Oct 19, 2010 at 11:23 AM, Wladimir Tavares wrote:
> This problem is a variation of Longest Increasing Subsequence (LIS). The
> faster algorithm é O(n log n)
>
> http://en.wikipedia.org/wiki/Longest_increasing_subsequence
>
> http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence
>
>
> Wladimir Araujo Tavares
> http://www.si.ufc.br/~wladimir <http://www.si.ufc.br/%7Ewladimir/>
> "Fiz uma faculdade! Só não fiz a segunda porque acabaram os tijolos."
>
>
>
>
>
> On Mon, Oct 18, 2010 at 7:53 PM, Marcelo Amorim Menegali <
> mmeneg...@gmail.com> wrote:
>
>> The problem statement doesn't make it clear, but I guess one can rotate
>> the envelopes (i.e. exchange x_i and y_i).
>> I mean, in the example case of {(1,2),(2,13),(5,10),(7,9),(9,1)}, isn't
>> (1,2),(1,9),(5,10) a valid solution (with length 3), instead of the ones
>> shown (with length 2)?
>>
>>
>> On Sat, Oct 16, 2010 at 5:40 PM, nishaanth wrote:
>>
>>> ya...finding the longest subsequence is the simplest method...and its
>>> nlogn..
>>>
>>> It works...it similar to box stacking problem
>>>
>>>
>>> On Fri, Oct 1, 2010 at 6:00 AM, adit.sh...@gmail.com <
>>> adit.sh...@gmail.com> wrote:
>>>
>>>> The problem here is more about finding the most optimal solution and not
>>>> just solution.
>>>> Rgds
>>>> Adi
>>>> -Original Message-
>>>> From: Sathaiah Dontula
>>>> Sent: 29/09/2010, 09:25
>>>> To: algogeeks@googlegroups.com
>>>> Subject: Re: [algogeeks] Algorithm to determine the largest number of
>>>> envelopes that can be nested inside one another.
>>>>
>>>>
>>>> I think we can do like this,
>>>>
>>>> 1. Sort all the xi's in ascending order -> nlog(n)
>>>> 2. Then find the longest increasing sequence of yi's -> nlog(n)
>>>> 3. complexity will be nlog(n).
>>>>
>>>> Thanks,
>>>> Sathaiah Dontula
>>>>
>>>> On Tue, Sep 28, 2010 at 11:37 PM, Prashant Kulkarni <
>>>> prashant.r.k...@gmail.com> wrote:
>>>>
>>>> > i think it is similar to finding max in a list O(n) or sorting
>>>> algorithm
>>>> > O(n log n)
>>>> >
>>>> > -- Prashant Kulkarni
>>>> >
>>>> >
>>>> >
>>>> >
>>>> > On Tue, Sep 28, 2010 at 11:33 PM, Rahul Singal <
>>>> rahulsinga...@gmail.com>wrote:
>>>> >
>>>> >> A possible solution i can think is create a directed graph where
>>>> each
>>>> >> vertex is a envelope and edges are from a bigger envelope to smaller
>>>> >> envelope ( one which can fit in bigger envelope ) . Now the problem
>>>> is
>>>> >> reduce to finding longest path in the graph .
>>>> >>
>>>> >> Regards
>>>> >> Rahul
>>>> >>
>>>> >> --
>>>> >> 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.
>>>> >
>>>>
>>>> --
>>&g
Re: [algogeeks] Algorithm to determine the largest number of envelopes that can be nested inside one another.
This problem is a variation of Longest Increasing Subsequence (LIS). The
faster algorithm é O(n log n)
http://en.wikipedia.org/wiki/Longest_increasing_subsequence
http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence
Wladimir Araujo Tavares
http://www.si.ufc.br/~wladimir <http://www.si.ufc.br/%7Ewladimir/>
"Fiz uma faculdade! Só não fiz a segunda porque acabaram os tijolos."
On Mon, Oct 18, 2010 at 7:53 PM, Marcelo Amorim Menegali <
mmeneg...@gmail.com> wrote:
> The problem statement doesn't make it clear, but I guess one can rotate the
> envelopes (i.e. exchange x_i and y_i).
> I mean, in the example case of {(1,2),(2,13),(5,10),(7,9),(9,1)}, isn't
> (1,2),(1,9),(5,10) a valid solution (with length 3), instead of the ones
> shown (with length 2)?
>
>
> On Sat, Oct 16, 2010 at 5:40 PM, nishaanth wrote:
>
>> ya...finding the longest subsequence is the simplest method...and its
>> nlogn..
>>
>> It works...it similar to box stacking problem
>>
>>
>> On Fri, Oct 1, 2010 at 6:00 AM, adit.sh...@gmail.com <
>> adit.sh...@gmail.com> wrote:
>>
>>> The problem here is more about finding the most optimal solution and not
>>> just solution.
>>> Rgds
>>> Adi
>>> -Original Message-----
>>> From: Sathaiah Dontula
>>> Sent: 29/09/2010, 09:25
>>> To: algogeeks@googlegroups.com
>>> Subject: Re: [algogeeks] Algorithm to determine the largest number of
>>> envelopes that can be nested inside one another.
>>>
>>>
>>> I think we can do like this,
>>>
>>> 1. Sort all the xi's in ascending order -> nlog(n)
>>> 2. Then find the longest increasing sequence of yi's -> nlog(n)
>>> 3. complexity will be nlog(n).
>>>
>>> Thanks,
>>> Sathaiah Dontula
>>>
>>> On Tue, Sep 28, 2010 at 11:37 PM, Prashant Kulkarni <
>>> prashant.r.k...@gmail.com> wrote:
>>>
>>> > i think it is similar to finding max in a list O(n) or sorting
>>> algorithm
>>> > O(n log n)
>>> >
>>> > -- Prashant Kulkarni
>>> >
>>> >
>>> >
>>> >
>>> > On Tue, Sep 28, 2010 at 11:33 PM, Rahul Singal <
>>> rahulsinga...@gmail.com>wrote:
>>> >
>>> >> A possible solution i can think is create a directed graph where each
>>> >> vertex is a envelope and edges are from a bigger envelope to smaller
>>> >> envelope ( one which can fit in bigger envelope ) . Now the problem is
>>> >> reduce to finding longest path in the graph .
>>> >>
>>> >> Regards
>>> >> Rahul
>>> >>
>>> >> --
>>> >> 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.
>>> >
>>>
>>> --
>>> 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
>&g
Re: [algogeeks] Algorithm to determine the largest number of envelopes that can be nested inside one another.
The problem statement doesn't make it clear, but I guess one can rotate the
envelopes (i.e. exchange x_i and y_i).
I mean, in the example case of {(1,2),(2,13),(5,10),(7,9),(9,1)}, isn't
(1,2),(1,9),(5,10) a valid solution (with length 3), instead of the ones
shown (with length 2)?
On Sat, Oct 16, 2010 at 5:40 PM, nishaanth wrote:
> ya...finding the longest subsequence is the simplest method...and its
> nlogn..
>
> It works...it similar to box stacking problem
>
>
> On Fri, Oct 1, 2010 at 6:00 AM, adit.sh...@gmail.com > wrote:
>
>> The problem here is more about finding the most optimal solution and not
>> just solution.
>> Rgds
>> Adi
>> -Original Message-
>> From: Sathaiah Dontula
>> Sent: 29/09/2010, 09:25
>> To: algogeeks@googlegroups.com
>> Subject: Re: [algogeeks] Algorithm to determine the largest number of
>> envelopes that can be nested inside one another.
>>
>>
>> I think we can do like this,
>>
>> 1. Sort all the xi's in ascending order -> nlog(n)
>> 2. Then find the longest increasing sequence of yi's -> nlog(n)
>> 3. complexity will be nlog(n).
>>
>> Thanks,
>> Sathaiah Dontula
>>
>> On Tue, Sep 28, 2010 at 11:37 PM, Prashant Kulkarni <
>> prashant.r.k...@gmail.com> wrote:
>>
>> > i think it is similar to finding max in a list O(n) or sorting
>> algorithm
>> > O(n log n)
>> >
>> > -- Prashant Kulkarni
>> >
>> >
>> >
>> >
>> > On Tue, Sep 28, 2010 at 11:33 PM, Rahul Singal > >wrote:
>> >
>> >> A possible solution i can think is create a directed graph where each
>> >> vertex is a envelope and edges are from a bigger envelope to smaller
>> >> envelope ( one which can fit in bigger envelope ) . Now the problem is
>> >> reduce to finding longest path in the graph .
>> >>
>> >> Regards
>> >> Rahul
>> >>
>> >> --
>> >> 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.
>> >
>>
>> --
>> 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.
>>
>>
>
>
> --
> S.Nishaanth,
> Computer Science and engineering,
> IIT Madras.
>
> --
> 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] Algorithm to determine the largest number of envelopes that can be nested inside one another.
ya...finding the longest subsequence is the simplest method...and its nlogn.. It works...it similar to box stacking problem On Fri, Oct 1, 2010 at 6:00 AM, adit.sh...@gmail.com wrote: > The problem here is more about finding the most optimal solution and not > just solution. > Rgds > Adi > -Original Message- > From: Sathaiah Dontula > Sent: 29/09/2010, 09:25 > To: algogeeks@googlegroups.com > Subject: Re: [algogeeks] Algorithm to determine the largest number of > envelopes that can be nested inside one another. > > > I think we can do like this, > > 1. Sort all the xi's in ascending order -> nlog(n) > 2. Then find the longest increasing sequence of yi's -> nlog(n) > 3. complexity will be nlog(n). > > Thanks, > Sathaiah Dontula > > On Tue, Sep 28, 2010 at 11:37 PM, Prashant Kulkarni < > prashant.r.k...@gmail.com> wrote: > > > i think it is similar to finding max in a list O(n) or sorting algorithm > > O(n log n) > > > > -- Prashant Kulkarni > > > > > > > > > > On Tue, Sep 28, 2010 at 11:33 PM, Rahul Singal >wrote: > > > >> A possible solution i can think is create a directed graph where each > >> vertex is a envelope and edges are from a bigger envelope to smaller > >> envelope ( one which can fit in bigger envelope ) . Now the problem is > >> reduce to finding longest path in the graph . > >> > >> Regards > >> Rahul > >> > >> -- > >> 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. > > > > -- > 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. > > -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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] Algorithm to determine the largest number of envelopes that can be nested inside one another.
The problem here is more about finding the most optimal solution and not just solution. Rgds Adi -Original Message- From: Sathaiah Dontula Sent: 29/09/2010, 09:25 To: algogeeks@googlegroups.com Subject: Re: [algogeeks] Algorithm to determine the largest number of envelopes that can be nested inside one another. I think we can do like this, 1. Sort all the xi's in ascending order -> nlog(n) 2. Then find the longest increasing sequence of yi's -> nlog(n) 3. complexity will be nlog(n). Thanks, Sathaiah Dontula On Tue, Sep 28, 2010 at 11:37 PM, Prashant Kulkarni < prashant.r.k...@gmail.com> wrote: > i think it is similar to finding max in a list O(n) or sorting algorithm > O(n log n) > > -- Prashant Kulkarni > > > > > On Tue, Sep 28, 2010 at 11:33 PM, Rahul Singal wrote: > >> A possible solution i can think is create a directed graph where each >> vertex is a envelope and edges are from a bigger envelope to smaller >> envelope ( one which can fit in bigger envelope ) . Now the problem is >> reduce to finding longest path in the graph . >> >> Regards >> Rahul >> >> -- >> 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. > -- 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] Algorithm to determine the largest number of envelopes that can be nested inside one another.
I think we can do like this, 1. Sort all the xi's in ascending order -> nlog(n) 2. Then find the longest increasing sequence of yi's -> nlog(n) 3. complexity will be nlog(n). Thanks, Sathaiah Dontula On Tue, Sep 28, 2010 at 11:37 PM, Prashant Kulkarni < prashant.r.k...@gmail.com> wrote: > i think it is similar to finding max in a list O(n) or sorting algorithm > O(n log n) > > -- Prashant Kulkarni > > > > > On Tue, Sep 28, 2010 at 11:33 PM, Rahul Singal wrote: > >> A possible solution i can think is create a directed graph where each >> vertex is a envelope and edges are from a bigger envelope to smaller >> envelope ( one which can fit in bigger envelope ) . Now the problem is >> reduce to finding longest path in the graph . >> >> Regards >> Rahul >> >> -- >> 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. > -- 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] Algorithm to determine the largest number of envelopes that can be nested inside one another.
i think it is similar to finding max in a list O(n) or sorting algorithm O(n log n) -- Prashant Kulkarni On Tue, Sep 28, 2010 at 11:33 PM, Rahul Singal wrote: > A possible solution i can think is create a directed graph where each > vertex is a envelope and edges are from a bigger envelope to smaller > envelope ( one which can fit in bigger envelope ) . Now the problem is > reduce to finding longest path in the graph . > > Regards > Rahul > > -- > 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] Algorithm to determine the largest number of envelopes that can be nested inside one another.
A possible solution i can think is create a directed graph where each vertex is a envelope and edges are from a bigger envelope to smaller envelope ( one which can fit in bigger envelope ) . Now the problem is reduce to finding longest path in the graph . Regards Rahul -- 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] Algorithm to determine the largest number of envelopes that can be nested inside one another.
You are given an unlimited number of each of n different types of envelopes. The dimensions of envelope type i are xi × yi.(i is in sub script) In nesting envelopes inside one another, you can place envelope A inside envelope B if and only if the dimensions A are strictly smaller than the dimensions of B. Algorithm to determine the largest number of envelopes that can be nested inside one another. -- 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.
