why premutation are needed in MCARDS

Question

I was trying to solve MCARDS problem on spoj at http://www.spoj.com/problems/MCARDS/

I know it involves Longest increasing subsequnce logic , but after many attempts I did not figure out solution of this question , so I search for solution I find below solution:

int go (vector < int > &v) {
  int ans = 1;
    int n = v.size();
    vector < int > d(n, 1);
    for(int i = 1; i < n; ++i) {
        int mmax = -1;
        for(int j = 0; j < i; ++j) {
            if(v[j] < v[i] && (mmax == -1 || d[mmax] < d[j])) {
                mmax = j;
            }
        }
        if(mmax != -1) 
            d[i] += d[mmax];
        ans = max(ans, d[i]);
    }
    return ans;
}

int main () {
    int test_case;
#ifndef ONLINE_JUDGE
  IN("/home/tigran/Desktop/Debug/input.txt");
  OUT("/home/tigran/Desktop/Debug/output.txt");
  scanf("%d", &test_case);
#else
  test_case = 1;
#endif
    while(test_case--) {
        int c, n;
        scanf("%d%d", &c, &n);
        int t = n * c;
        vector < int > colors(t), values(t);
        for(int i = 0; i < t; ++i) {
            scanf("%d%d", &colors[i], &values[i]);
        }
        vector < int > ind;
        for(int i = 0; i < c; ++i) {
            ind.push_back(i);
        }
        int mmin = IINF;
        vector < int > v(t);
        do {
            int cnt = 0;
            for(int i = 0; i < c; ++i) {
                for(int j = 0; j < n; ++j) {
                    mat[ind[i]][j] = cnt++;
                }
            }
            for(int i = 0; i < t; ++i) {
                v[i] = mat[colors[i] - 1][values[i] - 1];
            }
            mmin = min(mmin, t - go(v));
        }while(next_permutation(ind.begin(), ind.end()));
        printf("%d\n", mmin);
    }
    return 0;
}

Whats the logic behind permutation in above solution?

Thanks in advance

Answer 1

This problem is trying to find the cheapest way of moving cards to get them into a correct order.

Permutation

Suppose we have red, green, and blue cards with numbers 1 to 4.

All the same colour have to be together, and inside each group, the numbers must be sorted.

Therefore there are 3!=3*2*1=6 possible correct final orders:

R1 R2 R3 R4 B1 B2 B3 B4 G1 G2 G3 G4  (RBG)
R1 R2 R3 R4 G1 G2 G3 G4 B1 B2 B3 B4  (RGB)
B1 B2 B3 B4 R1 R2 R3 R4 G1 G2 G3 G4  (BRG)
G1 G2 G3 G4 R1 R2 R3 R4 B1 B2 B3 B4  (GRB)
B1 B2 B3 B4 G1 G2 G3 G4 R1 R2 R3 R4  (BGR)
G1 G2 G3 G4 B1 B2 B3 B4 R1 R2 R3 R4  (GBR)

Each order is determined by a permutation of the colours (shown in brackets).

This solution works by iterating over each permutation of the colours.

For each permutation it computes in v the correct position of each card for the given permutation. The function go is used to compute the smallest number of moves to place v into sorted order.

For example, if we have chosen the permutation (RGB), and the cards were originally in order:

R1 R2 R3 R4 G1 G2 G3 G4 B1 B2 B4 B3

Then v would be computed as

0  1  2  3  4  5  6  7  8  9  11 10

and go would determine that one move was needed to sort the cards.

Counting moves to sort

The go function works out the smallest number of moves by computing the longest increasing subsequence in v.

Once we have found the LIS, then we know we have to move every card that is not in this subsequence, and so the number of moves is t-length of LIS. (t is the number of cards)

In our example, the longest increasing subsequence would be:

     0  1  2  3  4  5  6  7  8  9 10

which is of length 11, so the answer is 12-11=1