If we take examples shown above .. 3 3 1 1 3 --> we need 3 groups and 3 numbers are given.. no need to do anything. 3 2 1 2 4 --> we need to form 2 groups ..sort it. n-k=1-> first 1 element(s) has to be moved to other bigger elements. ans=1. 4 2 1 2 5 7 --> we need to form 2 groups.. sort it. n-k=2-> first 2 elements has to be moved to last k elements in any manner(doesn't matter). here ans=1+2=3.
This is what I understood. if there is any fault, please give a counter example. On Sat, Mar 23, 2013 at 8:30 PM, rakesh kumar <rkchoudhary0...@gmail.com>wrote: > I don't get it how sorting will get us to the solution > > > On Sat, Mar 23, 2013 at 7:23 PM, bharat b <bagana.bharatku...@gmail.com>wrote: > >> can any one give counter example where sorting doesn't work? >> >> >> On Sat, Mar 23, 2013 at 3:15 PM, rakesh kumar >> <rkchoudhary0...@gmail.com>wrote: >> >>> this was a facebook online programming contest question so right now >>> there is no link available for that >>> >>> >>> On Sat, Mar 23, 2013 at 2:59 PM, Lucifer <sourabhd2...@gmail.com> wrote: >>> >>>> Looks like a dp problem.. >>>> I have an idea.. >>>> I believe that u must have this problem hosted on a system having a >>>> code checker.. >>>> Can you provide the link to the same, so that we can see if the logic >>>> works.. >>>> >>>> >>>> On Saturday, 23 March 2013 14:29:42 UTC+5:30, rakesh kumar wrote: >>>>> >>>>> >>>>> There are N objects kept in a row. The ith object is at position x_i. >>>>>> You want to partition them into K groups. You want to move all objects >>>>>> belonging to the same group to the same position. Objects in two >>>>>> different >>>>>> groups may be placed at the same position. What is the minimum total >>>>>> amount >>>>>> by which you need to move the objects to accomplish this? >>>>>> >>>>>> Input: >>>>>> The first line contains the number of test cases T. T test cases >>>>>> follow. The first line contains N and K. The next line contains N space >>>>>> seperated integers, denoting the original positions x_i of the objects. >>>>>> >>>>>> Output: >>>>>> Output T lines, containing the total minimum amount by which the >>>>>> objects should be moved. >>>>>> >>>>>> Constraints: >>>>>> 1 <= T <= 1000 >>>>>> 1 <= K <= N <= 200 >>>>>> 0 <= x_i <= 1000 >>>>>> >>>>>> Sample Input: >>>>>> 3 >>>>>> 3 3 >>>>>> 1 1 3 >>>>>> 3 2 >>>>>> 1 2 4 >>>>>> 4 2 >>>>>> 1 2 5 7 >>>>>> >>>>>> Sample Output: >>>>>> 0 >>>>>> 1 >>>>>> 3 >>>>>> >>>>>> Explanation: >>>>>> >>>>>> For the first case, there is no need to move any object. >>>>>> For the second case, group objects 1 and 2 together by moving the >>>>>> first object to position 2. >>>>>> For the third case, group objects 1 and 2 together by moving the >>>>>> first object to position 2 and group objects 3 and 4 together by moving >>>>>> object 3 to position 7. Thus the answer is 1 + 2 = 3. >>>>>> >>>>>> >>>>>> I thought of sorting the array and then calculating difference but no >>>>>> success.Please help >>>>>> >>>>> >>>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To unsubscribe from this group and stop receiving emails from it, send >>>> an email to algogeeks+unsubscr...@googlegroups.com. >>>> For more options, visit https://groups.google.com/groups/opt_out. >>>> >>>> >>>> >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to algogeeks+unsubscr...@googlegroups.com. >>> For more options, visit https://groups.google.com/groups/opt_out. >>> >>> >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to algogeeks+unsubscr...@googlegroups.com. >> For more options, visit https://groups.google.com/groups/opt_out. >> >> >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
