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 <[email protected]>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 <[email protected]>wrote: > >> can any one give counter example where sorting doesn't work? >> >> >> On Sat, Mar 23, 2013 at 3:15 PM, rakesh kumar >> <[email protected]>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 <[email protected]> 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 [email protected]. >>>> 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 [email protected]. >>> 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 [email protected]. >> 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 [email protected]. > 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 [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
