Card Sorting - Longest Increasing Subsequence

card-sorting

#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;
}