Re: [algogeeks] variation of LIS problem
if all the elements are positive then we can reverse the array and multiply
all of them by -1. Now apply LIS algorithm O(nlog(n)) and since it gives
the answer for all k<=n with the minimum sum, this will be the answer
multiplied by -1.
On Sat, Oct 26, 2013 at 12:12 AM, kumar raja wrote:
> I think O(nlogn) solution is possible for this problem. First find the
> largest increasing subsequence in O(nlogn) time.
>
> http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
>
> From this one u have LIS array M and parent array P. Now traverse through
> the array M and for all the length values >= k , u can print the "k"
> elements using Parent array P. I guess the step of printing the array
> elements wont be greater than O(n logn).
>
> So it is bounded by O(nlogn) . In the worst case it might go up to
> O(n^2). But i am not sure of this.
>
>
> On 25 October 2013 00:17, atul anand wrote:
>
>> OK, i got now why you were using min-heap.
>>
>> now consider this example :-
>>
>> 200,12,33,1,55,100
>>
>> K=3
>>
>> insert 200
>> 12 < 200...cannot insert
>> 33 < 200...cannot insert
>> .
>> .
>> .
>> 100<200 cannot insert
>>
>> output : 200 (not lenght of k)
>> output should be : 33,55,100
>>
>>
>> On 10/24/13, pankaj joshi wrote:
>> > Max-heap should not used in this case,
>> > why min heap? -- this is because program has to decide the smallest
>> element
>> > in k-group.
>> > in your example if i consider k =3 than
>> >
>> > insert 1
>> > insert 2
>> > insert 5
>> > insert 10
>> > size of heap ==4 so delete root of min- heap (which is 1),
>> > insert 100
>> > 30 cant insert because temp = 100 and 30> > insert 8 cant insert temp = 100 and 8> > (500>temp)size of heap ==4 so delete root of min-heap(which is 2)
>> > insert 555
>> >
>> > now if i check the heap elements
>> > {5, 10, 100 , 555}
>> >
>> >
>> >
>> > On Thu, Oct 24, 2013 at 11:25 PM, atul anand
>> > wrote:
>> >
>> >> in your updated algo , you should be using max-heap not min-heap.
>> >>
>> >> check your algo for :-
>> >>
>> >> 1,2,5,10,100,30,8,555
>> >>
>> >> let me know if it work fine.If it is working fine then i need more
>> >> clarity of your algo
>> >>
>> >> On 10/24/13, pankaj joshi wrote:
>> >> > @Saurabh:
>> >> > As per the question the elements of sub-sequence should be
>> increasing,
>> >> > so the solution will be {5} and as per the program.
>> >> > * but as written longest sub-sequence of k =2, so it should be {2,3}
>> >> > for
>> >> > this case. (there should be backtrack in this case.)
>> >> >
>> >> > @atul: increasing sub sequence is checked by condition, not by
>> >> > Min-heap,
>> >> > but min heap is used for storing the largest elements.
>> >> > So it is preferable DS,
>> >> >
>> >> >
>> >> > On Thu, Oct 24, 2013 at 8:35 PM, atul anand > >
>> >> > wrote:
>> >> >
>> >> >> @pankaj : how can you maintain increasing sub-sequence using
>> >> >> heapyour soln is for finding finding K largest element in the
>> >> >> array...so it wont work.
>> >> >>
>> >> >> On 10/24/13, Saurabh Paliwal wrote:
>> >> >> > check for {5,2,3} and K = 2.
>> >> >> >
>> >> >> >
>> >> >> >
>> >> >> > On Thu, Oct 24, 2013 at 7:41 PM, pankaj joshi <
>> joshi10...@gmail.com>
>> >> >> wrote:
>> >> >> >
>> >> >> >> @ Saurabh,
>> >> >> >>
>> >> >> >> I have done a correction on algo
>> >> >> >>
>> >> >> >> temp =0
>> >> >> >> loop n to a[]
>> >> >> >> if a[i]>temp
>> >> >> >>if min-heap(root) < a[i]
>> >> >> >> if min-heap(count)==k
>> >> >> >> delete root in min- heap
>> >> >> >> inseart a[i] in min - heap
>> >> >> >>
>> >> >> >> As i have made the condition: min-heap, (condition size should be
>> >> >> >> always
>> >> >> >> k) for this particular case.
>> >> >> >>
>> >> >> >> And in the example {5,2,1,10,9,30,8,55} if K =3
>> >> >> >>
>> >> >> >> insert 5
>> >> >> >> 2 is less so do nothing
>> >> >> >> 1 is less so do nothing
>> >> >> >> insert 10
>> >> >> >> 9 is less so do nothing
>> >> >> >> insert 30
>> >> >> >> 8 is less so do nothing
>> >> >> >> insert 55 (before inserting 50 delete the root of heap as count
>> of
>> >> >> >> heap
>> >> >> >> ==
>> >> >> >> 3), deleted root was - 5
>> >> >> >> so the output will be
>> >> >> >> {10,30,55}
>> >> >> >>
>> >> >> >> and if k is 4
>> >> >> >> than
>> >> >> >> {5, 10, 30 , 55)
>> >> >> >>
>> >> >> >>
>> >> >> >> On Thu, Oct 24, 2013 at 6:20 PM, Saurabh Paliwal <
>> >> >> >> saurabh.paliwa...@gmail.com> wrote:
>> >> >> >>
>> >> >> >>> You must be mistaken in the definition of heaps, or maybe the
>> >> >> >>> question,
>> >> >> >>> look at the updated question I put up there.
>> >> >> >>>
>> >> >> >>>
>> >> >> >>> On Thu, Oct 24, 2013 at 5:48 PM, pankaj joshi
>> >> >> >>> wrote:
>> >> >> >>>
>> >> >>
>> >> >> hi all,
>> >> >>
>> >> >> nlog(k) is the solution i think.
>> >> >> can anyone suggest more optimal?
>> >> >> solution:
>> >> >> create a min-heap, (condition size should be always k)
>> >> >>
>> >> >> temp =0
>> >>
Re: [algogeeks] variation of LIS problem
I think O(nlogn) solution is possible for this problem. First find the
largest increasing subsequence in O(nlogn) time.
http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
>From this one u have LIS array M and parent array P. Now traverse through
the array M and for all the length values >= k , u can print the "k"
elements using Parent array P. I guess the step of printing the array
elements wont be greater than O(n logn).
So it is bounded by O(nlogn) . In the worst case it might go up to O(n^2).
But i am not sure of this.
On 25 October 2013 00:17, atul anand wrote:
> OK, i got now why you were using min-heap.
>
> now consider this example :-
>
> 200,12,33,1,55,100
>
> K=3
>
> insert 200
> 12 < 200...cannot insert
> 33 < 200...cannot insert
> .
> .
> .
> 100<200 cannot insert
>
> output : 200 (not lenght of k)
> output should be : 33,55,100
>
>
> On 10/24/13, pankaj joshi wrote:
> > Max-heap should not used in this case,
> > why min heap? -- this is because program has to decide the smallest
> element
> > in k-group.
> > in your example if i consider k =3 than
> >
> > insert 1
> > insert 2
> > insert 5
> > insert 10
> > size of heap ==4 so delete root of min- heap (which is 1),
> > insert 100
> > 30 cant insert because temp = 100 and 30 > insert 8 cant insert temp = 100 and 8 > (500>temp)size of heap ==4 so delete root of min-heap(which is 2)
> > insert 555
> >
> > now if i check the heap elements
> > {5, 10, 100 , 555}
> >
> >
> >
> > On Thu, Oct 24, 2013 at 11:25 PM, atul anand
> > wrote:
> >
> >> in your updated algo , you should be using max-heap not min-heap.
> >>
> >> check your algo for :-
> >>
> >> 1,2,5,10,100,30,8,555
> >>
> >> let me know if it work fine.If it is working fine then i need more
> >> clarity of your algo
> >>
> >> On 10/24/13, pankaj joshi wrote:
> >> > @Saurabh:
> >> > As per the question the elements of sub-sequence should be
> increasing,
> >> > so the solution will be {5} and as per the program.
> >> > * but as written longest sub-sequence of k =2, so it should be {2,3}
> >> > for
> >> > this case. (there should be backtrack in this case.)
> >> >
> >> > @atul: increasing sub sequence is checked by condition, not by
> >> > Min-heap,
> >> > but min heap is used for storing the largest elements.
> >> > So it is preferable DS,
> >> >
> >> >
> >> > On Thu, Oct 24, 2013 at 8:35 PM, atul anand
> >> > wrote:
> >> >
> >> >> @pankaj : how can you maintain increasing sub-sequence using
> >> >> heapyour soln is for finding finding K largest element in the
> >> >> array...so it wont work.
> >> >>
> >> >> On 10/24/13, Saurabh Paliwal wrote:
> >> >> > check for {5,2,3} and K = 2.
> >> >> >
> >> >> >
> >> >> >
> >> >> > On Thu, Oct 24, 2013 at 7:41 PM, pankaj joshi <
> joshi10...@gmail.com>
> >> >> wrote:
> >> >> >
> >> >> >> @ Saurabh,
> >> >> >>
> >> >> >> I have done a correction on algo
> >> >> >>
> >> >> >> temp =0
> >> >> >> loop n to a[]
> >> >> >> if a[i]>temp
> >> >> >>if min-heap(root) < a[i]
> >> >> >> if min-heap(count)==k
> >> >> >> delete root in min- heap
> >> >> >> inseart a[i] in min - heap
> >> >> >>
> >> >> >> As i have made the condition: min-heap, (condition size should be
> >> >> >> always
> >> >> >> k) for this particular case.
> >> >> >>
> >> >> >> And in the example {5,2,1,10,9,30,8,55} if K =3
> >> >> >>
> >> >> >> insert 5
> >> >> >> 2 is less so do nothing
> >> >> >> 1 is less so do nothing
> >> >> >> insert 10
> >> >> >> 9 is less so do nothing
> >> >> >> insert 30
> >> >> >> 8 is less so do nothing
> >> >> >> insert 55 (before inserting 50 delete the root of heap as count of
> >> >> >> heap
> >> >> >> ==
> >> >> >> 3), deleted root was - 5
> >> >> >> so the output will be
> >> >> >> {10,30,55}
> >> >> >>
> >> >> >> and if k is 4
> >> >> >> than
> >> >> >> {5, 10, 30 , 55)
> >> >> >>
> >> >> >>
> >> >> >> On Thu, Oct 24, 2013 at 6:20 PM, Saurabh Paliwal <
> >> >> >> saurabh.paliwa...@gmail.com> wrote:
> >> >> >>
> >> >> >>> You must be mistaken in the definition of heaps, or maybe the
> >> >> >>> question,
> >> >> >>> look at the updated question I put up there.
> >> >> >>>
> >> >> >>>
> >> >> >>> On Thu, Oct 24, 2013 at 5:48 PM, pankaj joshi
> >> >> >>> wrote:
> >> >> >>>
> >> >>
> >> >> hi all,
> >> >>
> >> >> nlog(k) is the solution i think.
> >> >> can anyone suggest more optimal?
> >> >> solution:
> >> >> create a min-heap, (condition size should be always k)
> >> >>
> >> >> temp =0
> >> >> loop n to a[]
> >> >> if a[i]>temp
> >> >> if min-heap(root) < a[i]
> >> >> delete root in min- heap
> >> >> inseart a[i] in min - heap
> >> >>
> >> >> at the end of main loop the min-heap will contain the final
> >> >> sequence.
> >> >>
> >> >> On Thu, Oct 24, 2013 at 8:50 AM, atul anand
> >> >> wrote:
> >> >>
> >> >> > @Saurabh Paliwal : yes
> >> >> >
> >> >> > On 10/24/13,
