Card Sorting – Longest Increasing Subsequence

Arrange the cards in groups so that all the cards in a group are of the same color. Next, sort the cards in each group by their value. Calculate the lowest number of moves needed to arrange cards. A move consists of changing a position of one of his cards.

Input :
The first line of input file contains two integers C and N, number of cards of the same color separated by a space character.
Each of the next C*N lines contains a pair of two integers X and Y, 1 ≤ X ≤ C, 1 ≤ Y ≤ N, separated by a space character.

Example :
2 2
2 1
1 2
1 1
2 2
then output would be 2

sorting-card

Algorithm Paradigm: Longest Increasing Susequence

As the problem states that we need to find out lowest number of moves to arrange cards, it triggers that we need to find minimum Counting of moves to sort a array.
So first Lets see how to find out minimum number of moves to sort an array using lis
1. Find LIS(longest Increasing subsequence) of an array
2. Once we have found the LIS, then we know that we have to move all elements which are not in LIS, so the number of moves is length(array)-length(LIS)

Minimum number of moves to sort an array = LengthOfArray – LengthOfLIS

Now lets see the problem again , here we need to find out cheapest way of moves to sort cards in each group.
Lets understand its solution:

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:

0  1  2  3  4  5  6  7  8  9  10 11
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:

  • we will compute array ‘v’ the correct position of each card for the given permutation.
  • Then we will find out Minimum number of moves to sort that array ‘v’ and store this value in min

Result is minimum of ‘min’ from all iterations.

For example:

Original Sequence:
R1 R2 R3 R4 G1 G2 G3 G4 B1 B2 B4 B3
If we have chosen (RGB) as one of the permutation , then array 'v' would be:
0  1  2  3  4  5  6  7  8  9  11 10
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

Its my advise to you see this solution only if you have tried this problem many times.

C++ solution:

#include <iostream> 
#include <algorithm>
#include<climits>
#include <vector>
using namespace std; 
int BinarySearch(vector<int> &arr,int *small,int n, int value)
{
   int low = 0;
   int high = n-1;
   int mid;
   while (low < high)
   {
       mid = low + ((high - low) / 2);
       //! if array's mid value is greater then search value then select
       //! high as mid , this is where we are making it a ceil binary search
       if (arr[small[mid]] > value)
           high = mid;
       else if (arr[small[mid]] < value)
           low = mid + 1;
       else
           return mid;// found
   }
   return low;// not found
}
 
//! function to print longest Increasing Subsequence with nlog(n) complexity
int LIS(vector<int> &arr, int n)
{
    int *small = new int[n];
    int size = 0;
    for(int i=0 ; i<n ;i++)
    {
        if(i == 0)
        {
            small[size] = i;
        }
        //! Find the "index" of the smallest element in array small, which is >=than X,
        //! and change it to X. Here parent[indexOfX] = S[index - 1].
        else if(arr[i] <= arr[small[size]])
        {
            int pos = BinarySearch(arr,small,size+1,arr[i]);
            small[pos] = i;
        }
        //! parent[indexOfX] = Last Element Of S
        else
        {
            size = size+1;
            small[size] = i;
        }
    }
    delete [] small;
    return (size+1);
 
}
 
int matrix[4][100];
int main( )
{ 
    int n,c;
    //Get Numbers of different colors and number
    cin>>c>>n;
    vector<int>v(n*c);
    vector<int> color;
    vector<int> number;
    //Get color and its corresponding number
    for(int i = 0;i<n*c;i++)
    {
        int num,col;
        cin>>col>>num;
        color.push_back(col);
        number.push_back(num);
    }
    
    //per is used to do permutation of given number of colors
    vector<int> per;
    for(int i=0; i<c; i++)
    {
    	per.push_back(i);
    }
    int mini = INT_MAX;
    //For each permutation we will find minimum number of moves required to
    // sort array v'.
    do
	{
    	int count = 0;
		for(int i=0; i<c; i++)
		{
			for(int j=0; j<n; j++)
			{
				matrix[per[i]][j] = count++;
			}
		}
		//Generate array 'v'
		for(int i=0; i<n*c; i++)
		{
			v[i] = matrix[color[i]-1][number[i]-1];
		}
		//Get minimum of all permutation in variable mini
		mini = std::min(mini, (n*c) - LIS(v,n*c));
    }while(next_permutation(per.begin(), per.end()));
    
    cout<<mini;

    return 0;
}

Gist Link

References:
http://www.spoj.com/problems/MCARDS/ – MCARDS

Site Footer