SPOJ GONESORT

Link : GONESORT

Category : Sequences, ad-hoc

Hint : What are the books that need not be moved. Try to find maximum set of such numbers.

Solution : Let the sequence be of N numbers, a₁,a₂,a₃ . . . a_N, and let the sorted sequence be b₁,b₂,b₃ . . . b_N. Suppose the numbers b_i,b_i+1,b_i+2. . . b_j are such that in sequence {a}_N, they appear in same order  (b_i+k occurs before b_i+k+1, but there can be other numbers apart from b_i to b_j in between them). In this case, all numbers apart from this subsequence can be put to order in N-(j-i+1) steps.

Now the problem is to find maximum contiguous increasing sequence in given set (maximum length sequence such that it appears continuously in sequence {b}_N and appears in increasing order in {a}_N  It can be easily done in O(N²)

Code:

	#include <iostream>
	#include <cstdio>
	#include <cstdlib>
	#include <cstring>
	#include <cmath>
	#include <algorithm>
	#include <vector>
	#include <list>
	#include <queue>
	#include <stack>
	#include <map>
	#include <set>
	#include <utility>
	#include <climits>
	#include <cfloat>
	#include <cassert>
	#define readint(n) scanf("%d",&n)
	#define readull(n) scanf("%llu",&n)
	#define readll(n) scanf("%lld",&n)
	#define readf(n) scanf("%f",&n)
	#define readd(n) scanf("%lf",&n)
	#define init(mem) memset(mem,0,sizeof(mem))
	#define ll long long int
	#define ull unsigned long long int
	using namespace std;
	#define db
	int main(){
	int t,n,mem[1000],mem2[1000];
	map<int,int> locate;
	readint(t);
	while(t--){
	readint(n);
	for(int i=0;i<n;i++){
	readint(mem[i]);
	mem2[i]=mem[i];
	}
	sort(mem2,mem2+n);
	for(int i=0;i<n;i++){
	locate[mem2[i]]=i;
	}
	for(int i=0;i<n;i++){
	mem[i]=locate[mem[i]];
	}
	// now max inc cont subseq
	int maxval=-1;
	for(int start_finder=0;start_finder<n;start_finder++){
	int cnt=0;
	int to_find=start_finder;
	for(int i=0;i<n;i++){
	if(mem[i]==to_find){
	cnt++;
	to_find++;
	}
	}
	maxval=max(maxval,cnt);
	}
	printf("%d\n",n-maxval);
	}
	return 0;
	}

view raw gonesort.cpp hosted with ❤ by GitHub