Re: [algogeeks] Re: sort in minimum cost
Given the list, you would never want to decrement the last element as you
want it to be the maximum.
so either retain or remove the last element
Lets consider the Minimum cost among the sequence i to j as Cost[i..j]
So if you remove the element j, you add j to the cost
Cost[i..j] = Min{ Min(cost[i..j-1])+j, SortByDecremet(Cost(i..j))}
in SortByDecrement returns the total cost of decrementing the elements i to
j-1 so that they are not greater than element j(such that the list is
non-decreasing).
If we solve this equation recursively then I think we will get the minmum
cost.
I hope this can be represented in a better way/better equation.
Correct me if anything is not taken care of .
On Tue, Apr 26, 2011 at 3:58 PM, snehal jain learner@gmail.com wrote:
@above
you cant increment
On Tue, Apr 26, 2011 at 3:48 PM, Naveen Agrawal nav.coo...@gmail.comwrote:
@snehal jain
4 9 8 7 8
o/p 4 7 7 7 8
cost 3 by decrementing 9 n 8
Yes, now question is clear but your last example is incorrect.
4 9 8 7 8
o/p 4 8 8 8 8
cost 2 = decrementing (9 to 8) + incrementing (7 to 8)
--
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.
--
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: sort in minimum cost
This seems longest increasing subsequence problem to me.. Thanks, Anurag On Mon, Apr 25, 2011 at 9:31 PM, snehal jain learner@gmail.com wrote: few eg input 4 7 12 3 1 output 4 7 12 cost: 4 by removing 3 n 1 eg 2 6 3 5 7 12 4 o/p 3 3 5 7 12 cost 7 by decrementing 6 by 3 and removing 4 eg 3 4 9 8 7 8 o/p 4 7 7 7 8 cost 3 by decrementing 9 n 8 i hope its clear now.. On Mon, Apr 25, 2011 at 9:16 PM, hary rathor harry.rat...@gmail.comwrote: just tell me what is input and what will the output. atleast 3 example -- 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. -- 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: sort in minimum cost
@snehal jain 4 9 8 7 8 o/p 4 7 7 7 8 cost 3 by decrementing 9 n 8 Yes, now question is clear but your last example is incorrect. 4 9 8 7 8 o/p 4 8 8 8 8 cost 2 = decrementing (9 to 8) + incrementing (7 to 8) -- 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: sort in minimum cost
@above you cant increment On Tue, Apr 26, 2011 at 3:48 PM, Naveen Agrawal nav.coo...@gmail.comwrote: @snehal jain 4 9 8 7 8 o/p 4 7 7 7 8 cost 3 by decrementing 9 n 8 Yes, now question is clear but your last example is incorrect. 4 9 8 7 8 o/p 4 8 8 8 8 cost 2 = decrementing (9 to 8) + incrementing (7 to 8) -- 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.
[algogeeks] Re: sort in minimum cost
I don't understand your example. If the input has only one 3, and the output has more than one, you have not sorted the elements. Do you mean alter the elements to make the array non-decreasing? Don On Apr 25, 4:21 am, snehal jain learner@gmail.com wrote: Given n elements, sort the elements. Here, only one operation is permitted decreaseValue.. Note that you cannot swap the values.. output should be a sorted list.. if input is 4 5 2 1 3 output is 3 3 3.. There can be many answers.. Give the optimum solution with minimum cost. where as cost is the sum of decreased amounts.. -- 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: sort in minimum cost
just tell me what is input and what will the output. atleast 3 example -- 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: sort in minimum cost
few eg input 4 7 12 3 1 output 4 7 12 cost: 4 by removing 3 n 1 eg 2 6 3 5 7 12 4 o/p 3 3 5 7 12 cost 7 by decrementing 6 by 3 and removing 4 eg 3 4 9 8 7 8 o/p 4 7 7 7 8 cost 3 by decrementing 9 n 8 i hope its clear now.. On Mon, Apr 25, 2011 at 9:16 PM, hary rathor harry.rat...@gmail.com wrote: just tell me what is input and what will the output. atleast 3 example -- 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.
