@aalok_sathe and @alphastar: Say a= {1, 2, 3, 7, 8}, b= {1, 5, 6, 7, 8} and k=2. Swapping a[n-1] and b[0] gives the same skewness as swapping b[n-1] and a[0]. Which one do you choose? If you swap a[n-1] with b[0] you can get an arrangement with skewness 12 after the next swap. If you swap b[n-1] with a[0] the minimum skewness you can get after another swap is 14. How do you break the ties efficiently?

Here’s what I did for Bookshelves (got AC in contest; expecting 200 overall): Note that the largest book must contribute to the skewness. Our objective is to minimize the other book which contributes. To do this, we must bring the larger books to one of the arrays so that the maximum book of the other array is as small as possible. Let’s try the first case: we try to bring the large books to array a. Suppose there are p instances of the largest book in the second array. We need to bring these p instances to the first array. If we have enough amount of swaps and space available, we do this and do the same thing with the second largest book and so on. (Note that you must also take care that the total number of elements in the first array cannot exceed n.) Then do the same thing for the second array and print whichever solution is optimal. This can be implemented nicely with maps in O(n log n).