April 2015 – Live with passion

1314

Asif NaeemApril 28, 2015

#include <iostream>
#include <cstdio>
#include <sstream>
#include <string>

using namespace std;

int n;
string str;

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n;
		cin>>str;
		int i=0,j=1,k;

		while(i<n && j<n)
		{
			for(k=0;k<n;k++)
			{
				if(str[(k+i)%n]!=str[(k+j)%n])
				break;
			}
			if(k==n)
			break;
			if(str[(k+i)%n]>str[(k+j)%n])
				i=i+k+1;
			else if(str[(k+i)%n]<str[(k+j)%n])
				j=j+k+1;
			if(i==j)
			j+=1;
		}
		cout<<((i>j)?j:i)<<"\n";
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <sstream>

#include <string>

using namespace std;

int n;

string str;

int main()

{

int t;

cin>>t;

while(t--)

{

cin>>n;

cin>>str;

int i=0,j=1,k;

while(i<n && j<n)

{

for(k=0;k<n;k++)

{

if(str[(k+i)%n]!=str[(k+j)%n])

break;

}

if(k==n)

break;

if(str[(k+i)%n]>str[(k+j)%n])

i=i+k+1;

else if(str[(k+i)%n]<str[(k+j)%n])

j=j+k+1;

if(i==j)

j+=1;

}

cout<<((i>j)?j:i)<<"\n";

}

return 0;

}

10199

Asif NaeemApril 28, 2015

#include <iostream>
#include <cstdio>
#include <vector>
#include <sstream>
#include <string>
#include <algorithm>
#include <queue>
#include <cstring>
#include <map>
#include <set>

using namespace std;

map<string,int> mp;
map<int,string> mp2;
vector<int> gr[105];
//vector<int> V;
bool visit[105];
bool ap[105];
int discTime[105];
int low[105];
int par[105];
int cnt;
set<string> SET;
void cutvertex(int u)
{
	static int dsc_time=0;
	low[u]=discTime[u]=dsc_time++;
	visit[u]=1;
	int child=0;
	for(int i=0;i<gr[u].size();i++)
	{
		int v = gr[u][i];
		if(visit[v]==0)
		{
			par[v]=u;
			child++;
			cutvertex(v);
			low[u]=min(low[u],low[v]);

			if(par[u]==-1 && child>1)
			{
				if(ap[u]==0)
				{
					ap[u]=1;
					SET.insert(mp2[u]);
					cnt++;
				}
			}
			else if(low[v]>=discTime[u] && par[u]!=-1)
			{
				if(ap[u]==0)
				{
					ap[u]=1;
					SET.insert(mp2[u]);
					cnt++;
				}
			}
		}
		else if(v!=par[u])
		{
			low[u]=min(low[u],discTime[v]);
		}
	}
}

int main()
{
	string s,s2;
	int N,R;
	int kase=1;
	bool flag=0;
	while(scanf("%d",&N),N)
	{
		mp.clear();
		mp2.clear();
		cnt=0;
		for(int i=0;i<105;i++)
		{
			gr[i].clear();
			visit[i]=0;
			ap[i]=0;
			par[i]=-1;
			discTime[i]=0;
			low[i]=0;
		}
		for(int i=1;i<=N;i++)
		{
			cin>>s;
			mp2[i]=s;
			mp[s]=i;
		}
		cin>>R;
		for(int i=1;i<=R;i++)
		{
			cin>>s>>s2;
			gr[mp[s]].push_back(mp[s2]);
			gr[mp[s2]].push_back(mp[s]);
		}
		SET.clear();
		for(int i=1;i<=N;i++)
		{
			if(visit[i]==0)
				cutvertex(i);
		}
		if(flag)
		cout<<"\n";
		flag=1;
		cout<<"City map #"<<kase++<<": "<<cnt<<" camera(s) found\n";
		for(set<string>::iterator it=SET.begin();it!=SET.end();++it)
		{
			cout<<*it<<"\n";
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

#include <iostream>

#include <cstdio>

#include <vector>

#include <sstream>

#include <string>

#include <algorithm>

#include <queue>

#include <cstring>

#include <map>

#include <set>

using namespace std;

map<string,int> mp;

map<int,string> mp2;

vector<int> gr[105];

//vector<int> V;

bool visit[105];

bool ap[105];

int discTime[105];

int low[105];

int par[105];

int cnt;

set<string> SET;

void cutvertex(int u)

{

static int dsc_time=0;

low[u]=discTime[u]=dsc_time++;

visit[u]=1;

int child=0;

for(int i=0;i<gr[u].size();i++)

{

int v = gr[u][i];

if(visit[v]==0)

{

par[v]=u;

child++;

cutvertex(v);

low[u]=min(low[u],low[v]);

if(par[u]==-1 && child>1)

{

if(ap[u]==0)

{

ap[u]=1;

SET.insert(mp2[u]);

cnt++;

}

else if(low[v]>=discTime[u] && par[u]!=-1)

{

if(ap[u]==0)

{

ap[u]=1;

SET.insert(mp2[u]);

cnt++;

}

else if(v!=par[u])

{

low[u]=min(low[u],discTime[v]);

}

int main()

{

string s,s2;

int N,R;

int kase=1;

bool flag=0;

while(scanf("%d",&N),N)

{

mp.clear();

mp2.clear();

cnt=0;

for(int i=0;i<105;i++)

{

gr[i].clear();

visit[i]=0;

ap[i]=0;

par[i]=-1;

discTime[i]=0;

low[i]=0;

}

for(int i=1;i<=N;i++)

{

cin>>s;

mp2[i]=s;

mp[s]=i;

}

cin>>R;

for(int i=1;i<=R;i++)

{

cin>>s>>s2;

gr[mp[s]].push_back(mp[s2]);

gr[mp[s2]].push_back(mp[s]);

}

SET.clear();

for(int i=1;i<=N;i++)

{

if(visit[i]==0)

cutvertex(i);

}

if(flag)

cout<<"\n";

flag=1;

cout<<"City map #"<<kase++<<": "<<cnt<<" camera(s) found\n";

for(set<string>::iterator it=SET.begin();it!=SET.end();++it)

{

cout<<*it<<"\n";

}

return 0;

}

482

Asif NaeemApril 26, 2015

#include <iostream>
#include <sstream>
#include <map>
#include <string>
#include <cstring>
#include <queue>
using namespace std;

map<int,string> mp;

int main()
{
	int* arr;
	string db;
	int t,n;
	string str,s1,s2,s3;
	queue<int> q;
	getline(cin,str);
	stringstream ss;
	ss<<str;
	ss>>t;
	getline(cin,str);
	while(t--)
	{
		getline(cin,s1);
		getline(cin,s2);
		//q.clear();

		ss.clear();
		ss<<s1;
		int mx=0;
		while(ss>>n)
		{
			q.push(n);
			if(n>mx)
			mx=n;
		}
		mp.clear();
		ss.clear();
		ss<<s2;
		while(!q.empty())
		{
			ss>>db;
			mp[q.front()]=db;
			q.pop();
		}
		if(t)
		getline(cin,s3);

		for(int i=1;i<=mx;i++)
		{
			cout<<mp[i]<<"\n";
		}
		if(t)
		cout<<"\n";
		//cout<<double(mp[i]*1.0)<<"\n";
	}
	return 0;
}

#include <iostream>

#include <sstream>

#include <map>

#include <string>

#include <cstring>

#include <queue>

using namespace std;

map<int,string> mp;

int main()

{

int* arr;

string db;

int t,n;

string str,s1,s2,s3;

queue<int> q;

getline(cin,str);

stringstream ss;

ss<<str;

ss>>t;

getline(cin,str);

while(t--)

{

getline(cin,s1);

getline(cin,s2);

//q.clear();

ss.clear();

ss<<s1;

int mx=0;

while(ss>>n)

{

q.push(n);

if(n>mx)

mx=n;

}

mp.clear();

ss.clear();

ss<<s2;

while(!q.empty())

{

ss>>db;

mp[q.front()]=db;

q.pop();

}

if(t)

getline(cin,s3);

for(int i=1;i<=mx;i++)

{

cout<<mp[i]<<"\n";

}

if(t)

cout<<"\n";

//cout<<double(mp[i]*1.0)<<"\n";

}

return 0;

}

Longest Increasing Subsequence

Asif NaeemApril 24, 2015

LIS problem has a recursive solution and this also can be solved using DP. Recursive solution:

#include <iostream>
#include <cstdlib>
using namespace std;

int lis(int arr[],int length,int *max_length)
{
        if(length==1)
        return 1;
        int res,max_end_here=1;
        //recursively we get all LIS those are ending with arr[0],arr[1]
        //...and arr[length-1] and if max ending with arr[length-1]
        //requires to be upadted then do it.
        for(int i=1;i<length;i++)
        {
                res = lis(arr,i,max_length);
                if(arr[i-1]<arr[length-1] && res+1>max_end_here)
                        max_end_here = res+1;
        }

        if(max_end_here>*max_length)
                *max_length = max_end_here;

        return max_end_here;
}
int main()
{
        int sz,max_length;
        int *arr;
        cout<<"Enter size:\n";
        cin>>sz;
        cout<<"Enter elements:\n";
        arr = (int*)malloc(sizeof(int)*sz);

        for(int i=0;i<sz;i++)
        {
                cin>>arr[i];
        }
        max_length = 1;
        lis(arr,sz,&max_length);
        cout<<"LIS size = "<<max_length<<"\n";

        free(arr);
        return 0;
}

#include <iostream>

#include <cstdlib>

using namespace std;

int lis(int arr[],int length,int *max_length)

{

if(length==1)

return 1;

int res,max_end_here=1;

//recursively we get all LIS those are ending with arr[0],arr[1]

//...and arr[length-1] and if max ending with arr[length-1]

//requires to be upadted then do it.

for(int i=1;i<length;i++)

{

res = lis(arr,i,max_length);

if(arr[i-1]<arr[length-1] && res+1>max_end_here)

max_end_here = res+1;

}

if(max_end_here>*max_length)

*max_length = max_end_here;

return max_end_here;

}

int main()

{

int sz,max_length;

int *arr;

cout<<"Enter size:\n";

cin>>sz;

cout<<"Enter elements:\n";

arr = (int*)malloc(sizeof(int)*sz);

for(int i=0;i<sz;i++)

{

cin>>arr[i];

}

max_length = 1;

lis(arr,sz,&max_length);

cout<<"LIS size = "<<max_length<<"\n";

free(arr);

return 0;

}

But the solution has overlapping substructure property The same solution is calculated more than once)it can be solved using DP. DP Solution:

#include <iostream>
#include <cstdlib>
#include <cstring>

using namespace std;

int DPLIS(int arr[],int length)
{
        int *LIS_ANS;
        LIS_ANS = (int*)malloc(sizeof(int)*length);

        //memset(LIS_ANS,1,sizeof(LIS_ANS));
        for(int i=0;i<length;i++)
                LIS_ANS[i]=1;

        for(int i=1;i<length;i++)
        {
                for(int j=0;j<i;j++)
                {
                        if( arr[i]>arr[j] && LIS_ANS[i] < LIS_ANS[j]+1 )
                        LIS_ANS[i] = LIS_ANS[j]+1;
                }
        }

        int mx = 2;

        for(int i=0;i<length;i++)
                if(mx<LIS_ANS[i])
                mx = LIS_ANS[i];

        free(LIS_ANS);

        return mx;
}
int main()
{
        int sz;
        int *arr;
        cout<<"Enter size:\n";
        cin>>sz;
        cout<<"Enter elements:\n";
        arr = (int*)malloc(sizeof(int)*sz);

        for(int i=0;i<sz;i++)
        {
                cin>>arr[i];
        }
        cout<<"LIS size = "<<DPLIS(arr,sz)<<"\n";

        free(arr);
        return 0;
}

#include <iostream>

#include <cstdlib>

#include <cstring>

using namespace std;

int DPLIS(int arr[],int length)

{

int *LIS_ANS;

LIS_ANS = (int*)malloc(sizeof(int)*length);

//memset(LIS_ANS,1,sizeof(LIS_ANS));

for(int i=0;i<length;i++)

LIS_ANS[i]=1;

for(int i=1;i<length;i++)

{

for(int j=0;j<i;j++)

{

if( arr[i]>arr[j] && LIS_ANS[i] < LIS_ANS[j]+1 )

LIS_ANS[i] = LIS_ANS[j]+1;

}

int mx = 2;

for(int i=0;i<length;i++)

if(mx<LIS_ANS[i])

mx = LIS_ANS[i];

free(LIS_ANS);

return mx;

}

int main()

{

int sz;

int *arr;

cout<<"Enter size:\n";

cin>>sz;

cout<<"Enter elements:\n";

arr = (int*)malloc(sizeof(int)*sz);

for(int i=0;i<sz;i++)

{

cin>>arr[i];

}

cout<<"LIS size = "<<DPLIS(arr,sz)<<"\n";

free(arr);

return 0;

}

Time complexity of this solution is O(N*N). Better Solution with Time Complexity O(N*logN): Lets assume

Continue Reading “Longest Increasing Subsequence” →

A vertex in an undirected connected graph is an articulation point (or cut vertex) iff removing it (and edges through it) disconnects the graph. Articulation points represent vulnerabilities in a connected network – single points whose failure would split the network into 2 or more disconnected components. They are useful for designing reliable networks. For

Continue Reading “315” →

11677

Asif NaeemApril 11, 2015

#include <iostream>

using namespace std;

int main()
{
	int h1,h2,m1,m2;
	int a,b;
	while(cin>>h1)
	{
		cin>>m1>>h2>>m2;
		if(h1+h2+m1+m2==0)
		break;

		a = h1*60+m1;
		b = h2*60+m2;
		if(b<a)
		{
			cout<<(24*60)-a+b<<"\n";
		}
		else
		{
			cout<<b-a<<"\n";
		}
	}

	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int h1,h2,m1,m2;

int a,b;

while(cin>>h1)

{

cin>>m1>>h2>>m2;

if(h1+h2+m1+m2==0)

break;

a = h1*60+m1;

b = h2*60+m2;

if(b<a)

{

cout<<(24*60)-a+b<<"\n";

}

else

{

cout<<b-a<<"\n";

}

return 0;

}

11777

Asif NaeemApril 8, 2015

#include <iostream>
#include <cstdio>
#include <sstream>
#include <string>

using namespace std;

int main()
{
	int tt,kase=1;
	double s,a,MN,avg;
	cin>>tt;

	while(tt--)
	{
		MN=25;
		s = 0;
		avg = 0;
		for(int i=0;i<4;i++)
		{
			cin>>a;
			s+=a;
		}
		for(int i=0;i<3;i++)
		{
			cin>>a;
			avg+=a;
			if(a<MN)
			MN=a;
		}
		avg-=MN;
		avg/=2;
		s+=avg;
		if(s>=90)
			cout<<"Case "<<kase++<<": A\n";
		else if(s>=80)
			cout<<"Case "<<kase++<<": B\n";
		else if(s>=70)
			cout<<"Case "<<kase++<<": C\n";
		else if(s>=60)
			cout<<"Case "<<kase++<<": D\n";
		else
			cout<<"Case "<<kase++<<": F\n";
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <sstream>

#include <string>

using namespace std;

int main()

{

int tt,kase=1;

double s,a,MN,avg;

cin>>tt;

while(tt--)

{

MN=25;

s = 0;

avg = 0;

for(int i=0;i<4;i++)

{

cin>>a;

s+=a;

}

for(int i=0;i<3;i++)

{

cin>>a;

avg+=a;

if(a<MN)

MN=a;

}

avg-=MN;

avg/=2;

s+=avg;

if(s>=90)

cout<<"Case "<<kase++<<": A\n";

else if(s>=80)

cout<<"Case "<<kase++<<": B\n";

else if(s>=70)

cout<<"Case "<<kase++<<": C\n";

else if(s>=60)

cout<<"Case "<<kase++<<": D\n";

else

cout<<"Case "<<kase++<<": F\n";

}

return 0;

}

473

Asif NaeemApril 8, 2015

This solution is based on 0/1 knapsack problem. dp[i][j][k] is the maximum amount of songs with i songs while k unit time is left in disk j.

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <string>

using namespace std;

int N,T,M;
int song[800];
int dp[800][100][100];

void DP()
{
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<=M;j++)
		{
			for(int k=0;k<=T;k++)
			{
				if(k<song[i])
				dp[i+1][j][k]=dp[i][j][k];
				else if(k>=song[i])
				dp[i+1][j][k]=max(dp[i][j][k-song[i]]+1,dp[i][j][k]);
				if(j)
				dp[i+1][j][k]=max(dp[i][j-1][T-song[i]]+1,dp[i+1][j][k]);
			}
		}
	}
}

int main()
{
	int tt;
	cin>>tt;

	while(tt--)
	{
		cin>>N>>T>>M;
		cin>>song[0];
		for(int i=1;i<N;i++)
		{
			scanf(", %d",&song[i]);
		}
		memset(dp,0,sizeof(dp));
		DP();

		int res = 0;
		for(int i=0;i<=N;i++)
		{
			res = max(res,dp[i][M][0]);
		}
		cout<<res<<"\n";
		if(tt)
		cout<<"\n";
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <sstream>

#include <cstring>

#include <string>

using namespace std;

int N,T,M;

int song[800];

int dp[800][100][100];

void DP()

{

for(int i=0;i<N;i++)

{

for(int j=0;j<=M;j++)

{

for(int k=0;k<=T;k++)

{

if(k<song[i])

dp[i+1][j][k]=dp[i][j][k];

else if(k>=song[i])

dp[i+1][j][k]=max(dp[i][j][k-song[i]]+1,dp[i][j][k]);

if(j)

dp[i+1][j][k]=max(dp[i][j-1][T-song[i]]+1,dp[i+1][j][k]);

}

int main()

{

int tt;

cin>>tt;

while(tt--)

{

cin>>N>>T>>M;

cin>>song[0];

for(int i=1;i<N;i++)

{

scanf(", %d",&song[i]);

}

memset(dp,0,sizeof(dp));

DP();

int res = 0;

for(int i=0;i<=N;i++)

{

res = max(res,dp[i][M][0]);

}

cout<<res<<"\n";

if(tt)

cout<<"\n";

}

return 0;

}

10943

Asif NaeemApril 7, 2015

#include <iostream>
#include <cstdio>
#include <cstring>

#define ll long long
using namespace std;

ll dp[105][105];//length,sum
int N,K;

void DP()
{
	memset(dp,0,sizeof(dp));

	for(int i=0;i<105;i++)
		dp[1][i]=1;

	for(int length = 2;length<=K;length++)
	{
		dp[length][0]=1;
		for(int sum=1;sum<=N;sum++)
		{
			for(int j=0;j<=sum;j++)
			{
				dp[length][sum]+=dp[length-1][sum-j];
				dp[length][sum]%=1000000;
			}
		}
	}

}
int main()
{
	while(scanf("%d%d",&N,&K),N+K)
	{
		DP();
		cout<<dp[K][N]<<"\n";
	}

	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#define ll long long

using namespace std;

ll dp[105][105];//length,sum

int N,K;

void DP()

{

memset(dp,0,sizeof(dp));

for(int i=0;i<105;i++)

dp[1][i]=1;

for(int length = 2;length<=K;length++)

{

dp[length][0]=1;

for(int sum=1;sum<=N;sum++)

{

for(int j=0;j<=sum;j++)

{

dp[length][sum]+=dp[length-1][sum-j];

dp[length][sum]%=1000000;

}

int main()

{

while(scanf("%d%d",&N,&K),N+K)

{

DP();

cout<<dp[K][N]<<"\n";

}

return 0;

}

10616

Asif NaeemApril 7, 2015

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int N,Q;
int M,D;
int num[210];
int tt;
int dp[210][15][25];

void DP()
{
	dp[0][0][0]=1;

	for(int i=1;i<=N;i++)
	{
		for(int j=0;j<=M;j++)
		{
			for(int k=0;k<D;k++)
			{
				dp[i][j][k]=dp[i-1][j][k];//as no element is added
				if(j)
				{
					int tmp = (D+k-num[i]%D)%D;//in case k-num[i]%10 is less than 0 , D is added
					dp[i][j][k]+=dp[i-1][j-1][tmp];
					//from i-1 elemnts j-1 elements selected where previous remainder was
					//tmp
				}
			}
		}
	}
}

int main()
{
	int kase=1,cnt=1;
	bool flag;
	while(scanf("%d%d",&N,&Q),N+Q)
	{
		for(int i=1;i<=N;i++)
			cin>>num[i];
		flag = 1;
		cnt = 1;
		for(int i=1;i<=Q;i++)
		{
			cin>>D>>M;
			memset(dp,0,sizeof(dp));
			DP();
			if(flag)
			{
				cout<<"SET "<<kase++<<":\n";
				flag = 0;
			}
			cout<<"QUERY "<<cnt++<<": ";
			cout<<dp[N][M][0]<<"\n";
		}


	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int N,Q;

int M,D;

int num[210];

int tt;

int dp[210][15][25];

void DP()

{

dp[0][0][0]=1;

for(int i=1;i<=N;i++)

{

for(int j=0;j<=M;j++)

{

for(int k=0;k<D;k++)

{

dp[i][j][k]=dp[i-1][j][k];//as no element is added

if(j)

{

int tmp = (D+k-num[i]%D)%D;//in case k-num[i]%10 is less than 0 , D is added

dp[i][j][k]+=dp[i-1][j-1][tmp];

//from i-1 elemnts j-1 elements selected where previous remainder was

//tmp

}

int main()

{

int kase=1,cnt=1;

bool flag;

while(scanf("%d%d",&N,&Q),N+Q)

{

for(int i=1;i<=N;i++)

cin>>num[i];

flag = 1;

cnt = 1;

for(int i=1;i<=Q;i++)

{

cin>>D>>M;

memset(dp,0,sizeof(dp));

DP();

if(flag)

{

cout<<"SET "<<kase++<<":\n";

flag = 0;

}

cout<<"QUERY "<<cnt++<<": ";

cout<<dp[N][M][0]<<"\n";

}

return 0;

}

Month: April 2015

1314

10199

482

Longest Increasing Subsequence

315

11677

11777

473

10943

10616

Archives

Categories