@bharat n=4 k =2
1 2 5 7 this is the explanation for the 3rd case given in the question 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. here the elements are the position of the objects 1,2,3,4 I hope i am clear now. On Sat, Mar 23, 2013 at 9:31 PM, bharat b <[email protected]>wrote: > @rakesh : u misunderstood the question .. > As per u'r ans to ex is ... > 1,3 to 2 --> cost = 1+3=4 > 10 to 9 --> cost = 10. => total cost = 10+4 =14. > > > > On Sat, Mar 23, 2013 at 9:26 PM, rakesh kumar > <[email protected]>wrote: > >> >> Ok here is a counter example for your solution >> >> for n= 5 ,k=2 >> 1 2 3 9 10 >> n-k=>3 so moving first 3 elements ans = 1+2+3 =6 >> >> but the answer should be 3 >> by placing center of 2 groups be 2,9 and moving 1 ,3 to 2 and 10 to 9 >> >> >> On Sat, Mar 23, 2013 at 9:09 PM, bharat b >> <[email protected]>wrote: >> >>> 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. >>> >>> >>> >> >> -- >> 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.
