SPOJ PLD

Link : PLD

Category : Hashing

Hint : Consider substrings of S of length k and substrings of Reverse(S) of length k. If the hash value of one substring of S matches with hash value of substring of Reverse(S), and second starts when first ends, there is a match!

Solution : Well, the hint says pretty much all of it, except for a good hash function. For hash value of substring Si to Sj, we better not take O(k) time (else program is O(N*K) and gets TLE), hence I used the polynomial hash function

Hash({S_i to S_j})=(S_ia⁰+S_i+1a¹+S_i+2a²...)%p
Where a and p were primes (p was because of good hash spread, a was for no good reason :D ). This hash function allows Hash({S_i to S_j}) to be computed from Hash({S_i-1 to S_j-1}) in O(1) time, giving the complexity of hashing all substrings of S of length k O(N).

To do the index match (S's substring ends where Reverse(S)'s starts), keep a sorted vector at all hash values, and so a binary search.

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 HASHFAC 137
	#define MOD 1000003
	ll pow_log(ll base,ll exp){
	if(exp==0) return 1;
	else if(exp==1) return base;
	else if(exp%2==0){
	ll val=pow_log(base,exp/2);
	return (val*val)%MOD;
	}
	else{
	return (base*pow_log(base,exp-1))%MOD;
	}
	}
	bool binSearch(vector<int> *v,int val,int l,int h){
	if(h-l<=1){
	if((*v)[l]==val || (*v)[h]==val) return true;
	return false;
	}
	int m=(h+l)/2;
	if((*v)[m]==val) return true;
	else if((*v)[m]>val) return binSearch(v,val,l,m);
	return binSearch(v,val,m,h);
	}
	bool has(vector<int> *v,int val){
	if(v->size()==0 or (*v)[0]>val or (*v)[v->size()-1]<val) return false;
	return binSearch(v,val,0,v->size()-1);
	}
	int main(){
	int k,n;
	string str;
	readint(k);
	cin>>str;
	n=str.length();
	ll divfactor=pow_log(HASHFAC,MOD-2);
	ll multfactor=pow_log(HASHFAC,k-1);
	vector<int>* v=new vector<int>[MOD];
	// hash first k values
	ll hashval=0;
	ll fac=1;
	for(int i=0;i<k;i++){
	hashval=(hashval+fac*(str[i]-'a'))%MOD;
	fac=(fac*HASHFAC)%MOD;
	}
	v[hashval].push_back(k-1);
	#ifdef db
	cout<<hashval<<endl;
	#endif
	for(int i=k;i<n;i++){
	hashval=(hashval+MOD-(str[i-k]-'a'))%MOD;;
	hashval=(hashval*divfactor)%MOD;
	hashval=(hashval+(str[i]-'a')*multfactor)%MOD;
	v[hashval].push_back(i);
	#ifdef db
	cout<<hashval<<endl;
	#endif
	}
	int count=0;
	hashval=0;
	fac=1;
	for(int i=n-1;i>=n-k;i--){
	hashval=(hashval+fac*(str[i]-'a'))%MOD;
	fac=(fac*HASHFAC)%MOD;
	}
	if(has(&v[hashval],n-1)){
	count++;
	}
	for(int i=n-k-1;i>=0;i--){
	hashval=(hashval+MOD-(str[i+k]-'a'))%MOD;;
	hashval=(hashval*divfactor)%MOD;
	hashval=(hashval+(str[i]-'a')*multfactor)%MOD;
	if(has(&v[hashval],i+k-1)){
	count++;
	}
	}
	printf("%d\n",count);
	return 0;
	}

view raw pld.cpp hosted with ❤ by GitHub

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

Hello World!

Like all my recent ‘first’s, I’ll like to call this my “Hello World” post :D

And like all “Hello World”s, there’s nothing much to write, so I would like to end with my favourite quote:

  

“When a man is willing and eager, the Gods join in” – Aeschylus