@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 <bagana.bharatku...@gmail.com>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 > <rkchoudhary0...@gmail.com>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 >> <bagana.bharatku...@gmail.com>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 <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. >>> >>> >>> >> >> -- >> 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.
