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

SPOJ PARADOX

Link : PARADOX

Category : Graphs

Hint : constructed an appropriate graph and do a depth-first traversal.

Solution : Consider this as a directed graph, with edge from vertex A to vertex B if statement A tells about statement B. Make list of incoming and outgoing edges for each vertex, and then do simple depth-first traversal on both, incoming and outgoing edges. If a statement claims opposite of the truth value assigned to an already visited node, then there is a paradox.

Note that for the traversal, the starting vertex can be anyone, and its truth value can be anything (true or false, because if truth value of one statement is changed, then truth value of all nodes reachable by it via directed/directing edges also gets flipped, hence preserving the PARADOX or NOT PARADOX answer.

Code:

	#include <iostream>
	#include <cstdio>
	#include <cstdlib>
	#include <cstring>
	#include <cmath>
	#include <algorithm>
	#include <vector>
	#include <list>
	#include <queue>
	#include <stack>
	#include <map>
	#include <utility>
	#include <climits>
	#include <cfloat>
	#include <cassert>
	using namespace std;
	#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
	int main(){
	int n,implies[101],state[101];
	vector<int>implied_by[101];
	bool vis[101],claims[101];
	string str;
	while(1){
	readint(n);
	if(n==0)return 0;
	for(int i=1;i<=n;i++){
	vis[i]=false;
	claims[i]=false;
	state[i]=false;
	implied_by[i].clear();
	}
	stack<int> q;
	for(int i=1;i<=n;i++){
	readint(implies[i]);
	cin>>str;
	if(str[0]=='t'){
	claims[i]=true;
	}
	implied_by[implies[i]].push_back(i);
	q.push(i);
	}
	bool good=true;
	while(q.size()>0){
	if(vis[q.top()]){
	q.pop();
	continue;
	}
	int curr=q.top();
	q.pop();
	vis[curr]=true;
	bool imp=not(state[curr] xor claims[curr]);
	if(!vis[implies[curr]]){
	state[implies[curr]]=imp;
	q.push(implies[curr]);
	}
	else if(state[implies[curr]]!=imp){
	good=false;
	break;
	}
	// now check impliers
	for(int i=0;i<implied_by[curr].size();i++){
	if(!good) break;
	imp=not(state[curr] xor claims[implied_by[curr][i]]);
	if(!vis[implied_by[curr][i]]){
	state[implied_by[curr][i]]=imp;
	q.push(implied_by[curr][i]);
	}
	else if(state[implied_by[curr][i]]!=imp){
	good=false;
	break;
	}
	}
	}
	if(good){
	printf("NOT PARADOX\n");
	}
	else{
	printf("PARADOX\n");
	}
	}
	return 0;
	}

view raw paradox.cpp hosted with ❤ by GitHub