Monday, February 20, 2012

Silly Sort (Spoj - 2277, UVa - 1016)

Today I'll discuss the problem Silly Sort from spoj, which is also in uva.

In this problem you have to sort an array of integers in ascending order. Quite familiar to you. But here you are only allowed to swap any two elements. And each swap has a cost which is the sum of those two elements. You have to sort the array in minimum cost.

Seems tricky, so let's brainstorm. At first we have to know which element will go to which place after the complete sort. We can easily calculate that by copying the array into another array and sorting that array. Let's say original array is a and sorted array is b. So b[i] will go to ith place for each i, in other word i is the destination of b[i]. First thing comes to our mind is, in each swap we will ensure that at least one element will move to it's destination. This will ensure minimum number of swaps, but will it confirm the minimum cost?

Let's work with the first example -
3
3 2 1
Sorted array will be -
1 2 3
So If we want to ensure at least one element will go to it's destination in each swap, then we have to swap 1 and 3, and after that that is our sorted array, cost is 4, which is minimum cost. So it's working for this example.

Let's try with another example
3
3 1 2
If we swap 3 and 1, then 1 will go to it's destination and the array will become - {1, 3, 2}, now we have to swap 3 and 2, then it will be sorted. Cost is (3 + 1) + (3 + 2) = 9. But in first move if we swap 1 and 2, it will become {3, 2, 1} and then swapping 3 and 1 will make it sorted and the cost will be (1 + 2) + (3 + 1) = 7. So two different ordering causes two different costs. So what will be our strategy?

Let's work with 4th example given with the problem -
6 
8 4 5 3 2 7 
Sorted array will be -
2 3 4 5 7 8

So, 2 will go to 8's place, 3 will go to 4's place, etc. Let's draw these relations.


In the above image, it is seen that 2 will go to 8's place, 8 will go to 7's place, 7 will go to 2's place. These three formed a cycle, another cycle is 3  4  5  3. So every input can be decomposed into some cycles.

So, our next approach is solving each cycles independently and sum of the costs for all cycles is our result. But what is the cost of solving a cycle. We see If we swap 2 and 8 of 2  8  7  2 cycle. 2 will go to it's destination, and 7  8  7 will form a smaller cycle.

If we swap two elements in a cycle of length K > 1 such that at least 1 element of this cycle will go to it's destination. Then after the swap, it will be splited into two cycles, one with length K - 1 and another one with length 1. We don't need to do anything with the cycle of length 1 because the element is already in it's destination.

Now for solving a cycle optimally, we need some observations -
1. Every element of this cycle will participate in at least 1 swap.
2. We need K - 1 swaps to sort this cycle. Each swap will add two elements to the cost. So 2 × (K - 1) elements will be added to the cost. There are K elements. So some elements will be added multiple times.

So if we want to move an element x to it's destination by swapping with another value, we should try to swap with the minimum value of that cycle. If we can do that for every element other than the smallest element. Than in the final cost, every element will be added once and the minimum element will be added K - 1 times. And we cannot make any less cost by confirming (1) and (2).  So this is the optimal approach to solve a cycle.

So In the above cycle 2  8  7  2, we'll swap 7 and 2 first. Cost is 9, then 8 and 2, cost is 10. So total cost is 19 for this cycle. In the same way, solving the second cycle 3 → → → 3 will cost 15. Total cost for this case is 34. This is the result of that example also.

Now let's try example 3 -
5 
1 8 9 7 6 
There are two cycles.
1  1
6  8  7  9  6

Solving the first cycle costs 0, and second cycle costs 42, total 42. But result is 41. So solving every cycles independently will not give the best result. Here in this example, the minimum element is 6 in the second cycle. As the cycle length is 4 it will be added 3 times which will cost 18. But if know there is an 1 in another cycle. We can borrow it by swapping with 6, which will cost 6 + 1 = 7, then do the sorting this time we use 1 instead of 6, this will add 3 instead of 18. After sorting 1 will be in place of 6's destination and we have to give the 1 back to it's own cycle and bring our 6 back. We can do it by one more swap which will cost another 7. So total cost 7 + 3 + 7 = 17 which is 1 less than 18. That's how the result is 41. So we'll try to borrow the minimum value of the whole given array and see whether it gives the optimal results or not.

Here is my simple solution in c++.

#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>

using namespace std;

int a[100000];
int b[100000];
bool vis[100000];

int main (void) {
    int N;
    int t = 0;
    while (scanf("%d", &N) && N) {
        t++;
        for (int i = 0; i < N; ++i) {
            scanf("%d", &a[i]);
            b[i] = a[i];
            vis[i] = false;
        }
        sort(b, b + N);

        // Map the numbers to their desired place after sort
        map<int, int> place;
        
        for (int i = 0; i < N; ++i) {
            place[b[i]] = i;
        }
    
        int res = 0;
        for (int i = 0; i < N; ++i) {
            if (vis[i] == false) {
                if (place[a[i]] == i) {
                    vis[i] = true;
                    continue;
                }
                // We're in new cycle
                int min_val = a[i];
                int num = 0;
                int sum = 0;
                int j = i;

                while (vis[j] == false) {
                    sum += a[j];
                    num++;
                    if (a[j] < min_val) {
                        min_val = a[j];
                    }
                    vis[j] = true;
                    j = place[a[j]];
                }
                sum -= min_val;
                res += sum + min_val * (num - 1);
                
                // Let's try to borrow the minimum value.
                // If it's less costly then update our result.
                if (2 * (b[0] + min_val) <
                    (min_val - b[0]) * (num - 1)) {
                    res -= (min_val - b[0]) * (num - 1) -
                           2 * (b[0] + min_val);
                }    
            }
        }
        printf("Case %d: %d\n\n", t, res);
    }
    return 0;
}