Spoj( ONEZERO ) – Ones and zeros

Problem link: http://www.spoj.com/problems/ONEZERO/

Suppose the number that you want is X. X mod N = 0.

So you need to store only N states i.e. 0 to n-1. Start with 1.

Implement bfs approach. If the current state modulo is Y, append 0 to it i.e calculate Y*10 + 0 and find its modulo which will lead you to a new modulo state.

Similary append 1 to Y. i.e calculate Y*10 + 1 and find its modulo.

Example: if Y=11 append 0 to it to get 110 and append 1 to Y to get 111.

Have a parent array which will store the previous modulo state from which the current modulo state is reached. This parent array also acts as checkpoint to check if a modulo state is already visited or not.

Have a value array to store the value (1 or 0) that is appended to the parent modulo state to get the current modulo state.

Once the modulo state 0 is reached stop bfs and backtrack using parent array and value array to get the number (i.e smallest multiple of the number n consisting only of digits 1 and 0 beginning with 1).

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <string>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	#include <stdio.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	#define mod 1000003
	int parent[20005];
	typedef long long int ll;
	queue<int>q;
	int temp,currentState;
	int value[20005];
	void solve(int n){
	q.push(1);
	parent[1]=0;
	while(!q.empty()){
	currentState=q.front();
	q.pop();
	if(currentState==0){
	stack<int> s;
	while(parent[currentState]){
	s.push(value[currentState]);
	currentState=parent[currentState];
	}
	s.push(1);
	while(!s.empty()){
	printf("%d",s.top());
	s.pop();
	}
	printf("\n");
	break;
	}
	temp=(currentState*10)%n;
	if(parent[temp]==-1){
	q.push(temp);
	parent[temp]=currentState;
	value[temp]=0;
	}
	temp=currentState*10+1;
	temp%=n;
	if(parent[temp]==-1){
	q.push(temp);
	parent[temp]=currentState;
	value[temp]=1;
	}
	}
	}
	int main(){
	int t,n;
	scanf("%d",&t);
	while(t--){
	while(!q.empty()){
	q.pop();
	}
	REP(i,20000)
	parent[i]=-1;
	scanf("%d",&n);
	solve(n);
	}
	}

view raw ONEZERO.cpp hosted with ❤ by GitHub

Spoj (QUE1) Queue (Rookie)

problem link – http://www.spoj.com/problems/QUE1/

Vector of pairs is used to store the height and count of taller person standing before.

This problem can be solved by sorting the vector based on height.

Assign the final position for each person i in the answer array by moving them C empty positions from the index 0 where

C = count of taller person who are standing before person i

Detailed explanation is in the comments of the code below.

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	#include <stdio.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	#define MAX 10000005
	typedef long long int ll;
	int ans[1005];
	int main(){
	int t,n;
	vector<pair<int,int> >arr;
	scanf("%d",&t);
	while(t--){
	scanf("%d",&n);
	arr.resize(n);
	memset(ans,0,sizeof ans);
	//height
	REP(i,n){
	scanf("%d",&arr[i].first);
	}
	//count of ppl whose height is greater than the person at position i
	REP(i,n){
	scanf("%d",&arr[i].second);
	}
	//sort the vector of pairs based on the height
	sort(arr.begin(),arr.end());
	int greaterCount=0;
	REP(i,n){
	//greaterCount = count of ppl whose height is greater than the person at position i
	greaterCount=arr[i].second;
	REP(j,n){
	//if there is no person whose height is greater than the height of current person (positioned at i) is found
	//and if position j in ans array is not filled yet,then assign that person to position j
	if(greaterCount==0&&ans[j]==0){
	ans[j]=arr[i].first;
	break;
	}
	//decrement the greaterCount eachtime when an unfilled answer position is found
	//this implicitly means: decrement the greaterCount eachtime when a person with height greater than the current person i is found
	if(ans[j]==0)
	greaterCount--;
	}
	}
	REP(i,n){
	printf("%d ",ans[i]);
	}
	printf("\n");
	}
	}

view raw QUE1.cpp hosted with ❤ by GitHub

Spoj(SCUBADIV) – Scuba diver

problem link : http://www.spoj.com/problems/SCUBADIV/

This is similar to the classic “knapsack” dynamic programming problem.

Recurrence relation:

dp[n][O][N] = minimum total weight of cylinders required to have O and N capacity of oxygen and nitrogen (capacity of oxygen and nitrogen can exceed) provided n cylinders

dp[i][co][cn]=min(solve(i-1,co,cn),solve(i-1,max(co-oxi[i-1],0),max(cn-nitro[i-1],0))+w[i-1]);

where oxi[i-1] and nitro[i-1] denotes the oxygen and nitrogen capacity of ith cylinder,

w[i-1] denotes the weight of ith cylinder

Terminating conditions:

dp[0][0][0] = 0

dp[0][oxi][nitro]=INFINITY where oxi>0 and nitro>0

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	#include <stdio.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	typedef long long int ll;
	const int MAX = 1024;
	const int INF = 999999999;
	int N, O, n, t, cs;
	int nitro[MAX], oxi[MAX], w[MAX];
	int dp[MAX][22][80], visited[MAX][22][80];
	int solve(int i, int co, int cn)
	{
	if(dp[i][co][cn]!=-1){
	return dp[i][co][cn];
	}
	if(co==0&&cn==0){
	dp[i][co][cn]= 0;
	}
	else if(i==0){//if we considered all cylinders and if co and cn are still not equal to zero
	//then its not possible to satisfy the required condition. Hence return INF in order to eliminate all
	//recursive paths leading to this status
	dp[i][co][cn]= INF;
	}else{
	//either select the ith cylinder or move on to i-1th cylinder
	//Be careful about the index:
	//ith cylinder oxi[i-1] capacity of oxygen and nitro[i-1] capacity of nitrogen
	dp[i][co][cn]=min(solve(i-1,co,cn),solve(i-1,max(co-oxi[i-1],0),max(cn-nitro[i-1],0))+w[i-1]);
	}
	return dp[i][co][cn];
	}
	int main()
	{
	scanf("%d", &t);
	while(t--){
	scanf("%d %d %d", &O, &N, &n);
	for(int i=0;i<n+1;i++)
	for(int j=0;j<O+1;j++)
	for(int k=0;k<N+1;k++)
	dp[i][j][k]=-1;
	for(int i = 0; i < n; i++)
	scanf("%d %d %d", &oxi[i], &nitro[i], &w[i]);
	//dp[n][O][N] gives the minimum total weight of cylinders required to have O and N capacity of oxygen
	//and nitrogen (capacity of oxygen and nitrogen can exceed)
	printf("%d\n", solve(n, O, N));
	}
	return 0;
	}

view raw SCUBADIV.cpp hosted with ❤ by GitHub

Spoj(GAMES) – HOW MANY GAMES

Brute force will give you TLE even though it will pass initial test cases.

The logic behind this problem is to represent the average score x in the form of a/b where b is minimum.

We know x=a/b . First let us bring x in the form of a/b by multiplying x with pow(10,number of digits after decimal point)

Example: x=30.25 Here we multiply x with pow(10,2) so now a=3025 and b=100

Now we have to reduce the fraction a/b to its least form.

The greatest common divisor is useful for reducing fractions to be in lowest terms. For example, gcd(42, 56) = 14, therefore,

Similarly 3025/100=121*25/4*25=121/4

Now we find gcd(a,b) which is nothing but gcd(x*pow(10,numberOfDigitsAfterDecimalPoint),pow(10,numberOfDigitsAfterDecimalPoint))

FInally answer is b/gcd(a,b)

Where b = pow(10,numberOfDigitsAfterDecimalPoint)

a = x*pow(10,numberOfDigitsAfterDecimalPoint)

So ans for average score x=30.25 is 100/gcd(3025,100)=100/25=4

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	int gcd(int a,int b){
	if(a<b)
	return gcd(b,a);
	if(b==0)
	return a;
	return gcd(b,a%b);
	}
	int main(){
	int t;
	scanf("%d",&t);
	while(t--){
	string str;
	cin>>str;
	int len=str.length();
	int c=0;
	int decimalPointFlag=0;
	for(int i=len-1;i>=0;i--){
	if(str[i]=='.'){
	decimalPointFlag=1;
	break;
	}
	else{
	c++;
	}
	}
	int power=0;
	int number=0;
	int numerator;
	if(decimalPointFlag){
	for(int i=0;i<len;i++){
	if(str[i]!='.'){
	number=number*10+str[i]-'0';
	}
	}
	power=pow(10,c);
	numerator=number;
	printf("%d\n",power/gcd(numerator,power));
	}
	else{
	printf("1\n");
	}
	}
	}

view raw GAMES.cpp hosted with ❤ by GitHub

Spoj(MIXTURES) Mixtures – Dynamic Programming

I always love solving Harry Potter theme based problems.This one http://www.spoj.com/problems/MIXTURES/ was  fun solving.

Its based on classic DP problem Matrix Chain multiplication.

Task :

Minimize the  amount of smoke that Harry can get when mixing all the mixtures together.

Solution:

If you look into the problem statement carefully you will know that harry can mix only adjacent  mixtures together. So for example m1,m2,m3 are the mixtures he can either mix m1,m2 first or m2,m3 first.

i.e you can either split the mixture set as {m1} and {m2,m3}

OR

{m1,m2} and {m3}

Let dp[a][b]=minimum smoke produced on mixing mixtures a to b

SO its all about splitting the mixtures into 2 subsets and each of that subsets into 2 sub-subsets and so on such that smoke produced(smoke generated in mixing subsets s1 ans s2 is sum(elements in s1)%100 X sum(elements in s2)%100) is minimized. Aim of the problem  boils down to minimizing the product of the 2 mixtures to be mixed.

Hence our recurrence relation is going to be

dp[a][b]=min(dp[a][k]+dp[k+1][b]+sum(a,k)*sum(k+1,b)) for all k where a<=k<b

Here sum(a,b) defines (sum of all elements from a to b )%100

Base case is dp[i][i]=0

[gist https://gist.github.com/vishnujayvel/9030639]

Spoj(RPLB) Blueberries

Yet another Knapsack based problem

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	int n,W,wt[1001];
	int dp[1001][1001];
	int solve(int i,int w){
	if(i>n)
	return w;
	if (dp[i][w]!=-1)
	return dp[i][w];
	if((wt[i]+w)<=W)
	dp[i][w]=max(solve(i+2,w+wt[i]),solve(i+1,w));
	else
	dp[i][w]=solve(i+1,w);
	return dp[i][w];
	}
	int main(){
	int t;
	scanf("%d",&t);
	FOR(j,1,t+1){
	scanf("%d %d",&n,&W);
	FOR(i,1,n+1){
	scanf("%d",&wt[i]);
	}
	memset(dp,-1,sizeof dp);
	printf("Scenario #%d: %d\n",j,solve(1,0));
	}
	}

view raw RPLB.cpp hosted with ❤ by GitHub

Spoj(EDIST) – Edit Distance -Dynamic Programming

 

http://www.spoj.com/problems/EDIST/

Consider the string SAT .We need to convert it into SAIT

there are 3 possibilities as seen in the picture

So the recursive rule goes like this

dp[i,j]=edit distance for strings of length i and j

dp[i,j]= min(dp[i-1,j-1]+(X[i-1]!=Y[j-1]),dp[i-1,j]+1,dp[i,j-1]+1)

Here X and Y are strings with 0 based index i.e  X[i-1] denotes ith character in X

With the base conditions

dp[0,j]=j //just insertions

dp[j,0]=j //just deletions

	#include<iostream>
	#include<string.h>
	using namespace std;
	char str1[2001];
	char str2[2001];
	int dp[2001][2001];
	int main(){
	int t;
	cin>>t;
	while(t--){
	cin>>str1>>str2;
	int d1,d2,d3,i,j,len1,len2;
	len1=strlen(str1);
	len2=strlen(str2);
	for( i=0;i<=len1;i++)
	dp[i][0]=i;
	for( j=1;j<=len2;j++)
	dp[0][j]=j;
	for( i=1;i<=len1;i++){
	for( j=1;j<=len2;j++){
	d1=((str1[i-1]==str2[j-1])?0:1)+dp[i-1][j-1];//substitution-->if last character same dont do anything(0) else replace last char(1
	d2=dp[i][j-1]+1; // convert (s+ch1) to (t+ch2) by inserting in ch2. so dp (s+ch1,t)+1 +1 for ch2 insertion
	//insertion-->str2 of j-1 length is converted to
	d3=dp[i-1][j]+1;//deletion -->convert (s+ch1) to (t+ch2) by deleting ch1 from s.so dp[s,t+ch2]+1 +1 for ch1 deletion
	//finding minimum of 3
	if(d1<d2&&d1<d3)
	dp[i][j]=d1;
	else{
	if(d2<d3)
	dp[i][j]=d2;
	else
	dp[i][j]=d3;
	}
	}
	}
	cout<< dp[len1][len2];
	cout<<endl;
	}
	}

view raw EDIST.cpp hosted with ❤ by GitHub

Spoj (SUBS) – String it out

http://www.spoj.com/problems/SUBS/

There is  a very interesting algorithmic approach for this problem

(Thanks to topcoder forum from where i got this idea)

To find the maximum power using which X can be expanded such that X is a subsequence in Y

highest possible power = length_of_Y/length_of_X

lowest power= 0

Now using binary search find the maximum valid power whose value is in the range [0,highest possible power]

[gist https://gist.github.com/vishnujayvel/7907760 ]

Spoj (DSUBSEQ) – Distinct Subsequences

http://www.spoj.com/problems/DSUBSEQ/

Consider the string “ABCD”

Let dp[i] = { number of subsequences possible from string[1…i]}

Note : we are considering 1 based string array

what are all the possible subsequences

dp[0] = 1   { }

dp[1]= 2   { } ,A

dp[2] = 4  { } ,A ,B ,AB

dp[3] = 8  { } ,A ,B ,AB ,C ,AC,BC,ABC

dp[4] = 16 { } ,A ,B ,AB ,C ,AC,BC,ABC,D,AD,BD,ABD,CD,ACD,BCD ,ABCD

So do we get some kind of pattern ?

yes!

dp[i]= dp[i-1]*2

(sum of all subseq till string[1…i-1] + sum of subseq till string[1…i-1] concatenated with character string[i])

There one more case we have to consider

if we have duplicate characters in the string then our subsequence will also be duplicated

To prevent that have a last[ ] array to store position of string[i] which occured before

last[string[i]]= last occurence of string[i]

substract subsequence count occured till position (last[string[i]]-1) since it is repeated again

so the correct recursion rule is

dp[i]=dp[i-1]*2;

if(last[string[i]]>0)

dp[i]=(dp[i]-dp[last[string[i]]-1]);

Spoj(STAMPS) Stamps

http://www.spoj.com/problems/STAMPS/

Very simple problem indeed.

Code is self explanatory

[gist https://gist.github.com/vishnujayvel/f2bb08a9f20986b1b322]