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.
