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.
