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.
