UVA – 11456 – Train Sorting


#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>

using namespace std;
int * LIS_Lengths(vector<int> a, int dir) {
	int* lis = new int[a.size()];
	memset(lis, sizeof(lis), 0);

	for (size_t i = 0; i < a.size(); i++) {
		int longest = 0;
		for (size_t j = 0; j < i; j++)
			if (a[j] > a[i] == dir && lis[j] > longest)
				longest = lis[j];
		lis[i] = longest + 1;
	}
	return lis;
}

int main() {
	int N, n, T;
	cin >> T;
	while (T-- && (cin >> N)) {
		vector<int> a;
		while (N-- && (cin >> n))
			a.push_back(n);
		reverse(a.begin(), a.end());

		int* lis = LIS_Lengths(a, 0);
		int* lds = LIS_Lengths(a, 1);

		int MAX_LIS = 0;
		for (size_t i = 0; i < a.size(); i++)
			MAX_LIS = max(lis[i] + lds[i] - 1, MAX_LIS);

		cout << MAX_LIS << endl;
	}
	return 0;
}
Advertisements

2 thoughts on “UVA – 11456 – Train Sorting

  1. Habib says:

    why u reverse the vector????i think we can get lis directly from the vector and reversing that vector and performing lis algo then we could get lds…is it true???

  2. Habib says:

    uva 10534 sol: It works fine about my thought bt it didn’t work on uva 11456 .plz help me thnx…

    #include
    #include
    #include
    #include

    using namespace std;

    vectorSequence;
    vectorI;
    vectorL;
    vectorLD;
    const int inf = 2000000000;

    int n;
    int LisNlogK() { // which runs the NlogK LIS algorithm
    int i; // auxilary variable for iteration
    I.clear();
    L.clear();
    I.push_back(-inf);// I[0] = -infinite
    L.push_back(inf);
    for( i = 1; i < n; i++ ){ // observe that i <= n are given
    I.push_back(inf); // I[1 to n] = infinite
    L.push_back(inf);
    }

    int LisLength = 0; // keeps the maximum position where a data is inserted

    for( i = 0; i < n; i++ ) { // iterate left to right
    int low, high, mid; // variables to perform binary search
    low = 0; // minimum position where we to put data in I[]
    high = LisLength; // the maximum position

    while( low <= high ) { // binary search to find the correct position
    mid = ( low + high ) / 2;
    if( I[mid] high and we put our item in I[low]
    I[low] = Sequence[i];
    L[i]=low;
    if( LisLength < low ) // LisLength contains the maximum position
    LisLength = low;
    }

    return LisLength; // return the result
    }
    int LisNlogKD() { // which runs the NlogK LIS algorithm
    int i; // auxilary variable for iteration
    I.clear();
    LD.clear();
    I.push_back(-inf);// I[0] = -infinite
    LD.push_back(inf);
    for( i = 1; i < n; i++ ){ // observe that i <= n are given
    I.push_back(inf); // I[1 to n] = infinite
    LD.push_back(inf);
    }

    int LisLength = 0; // keeps the maximum position where a data is inserted

    for( i = 0; i < n; i++ ) { // iterate left to right
    int low, high, mid; // variables to perform binary search
    low = 0; // minimum position where we to put data in I[]
    high = LisLength; // the maximum position

    while( low <= high ) { // binary search to find the correct position
    mid = ( low + high ) / 2;
    if( I[mid] high and we put our item in I[low]
    I[low] = Sequence[i];
    LD[i]=low;
    if( LisLength < low ) // LisLength contains the maximum position
    LisLength = low;
    }

    return LisLength; // return the result
    }
    int main() {
    freopen("input.txt","r",stdin);
    int a;
    while(scanf("%d",&n)==1 && n){
    Sequence.clear();
    for(int i=1;i>a;
    Sequence.push_back(a);
    }
    int result=LisNlogK();
    reverse(Sequence.begin(),Sequence.end());
    result=LisNlogKD();
    reverse(LD.begin(),LD.end());
    //cout<<result<<endl;
    //cout<<"LIs is : ";
    for(int i=0;i<L.size();i++)cout<<L[i]<<" ";cout<<endl;
    //cout<<"LDS IS : ";
    for(int i=0;i<LD.size();i++)cout<<LD[i]<<" ";cout<<endl;
    result=-1;
    for(int i=0;i<n;i++)
    result=max(result,min(L[i],LD[i]));
    cout<<2*result-1<<endl;
    }
    return 0;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: