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.
