for studious students II i came up with following solution during the contest but it didnt work in 6 min time.
is there a better solution possible. and how to do that.
Also can anyone provide a detailed explanation for problem A and C.
#include<map>
#include<iostream>
#include<string>
#include<queue>
using namespace std;
#define mod 1000000007
struct CompareMethod
{
bool operator()(const std::string &a, const std::string &b) const
{
if(a.length()>b.length())
return 0;
return 1;
}
};
int main()
{
int t;
cin >> t;
while(t--)
{
string s;
cin >> s;
map<string,int>dp;
priority_queue<string,vector<string>,CompareMethod>q;
dp[s]=1;
q.push(s);
while(!q.empty())
{
string n=q.top();
//cout << n <<"\n";
q.pop();
for(int i=0;i<n.length();i++)
{
for(int j=i+1;j<n.length();j++)
{ bool pa=0,pb=0;
for(int k=i;k<=j;k++)
if(n[k]=='a')
pa=1;
else
pb=1;
if(pa==1 && pb==1)
{ string tmp1,tmp2,tmp;
tmp1=n.substr(0,i);
tmp2=n.substr(j+1,n.length()-j);
tmp=tmp1+"a"+tmp2;
if(dp.find(tmp)==dp.end())
q.push(tmp);
dp[tmp]+=dp[n];
dp[tmp]=dp[tmp]%mod;
tmp1=n.substr(0,i);
tmp2=n.substr(j+1,n.length()-j);
tmp=tmp1+"b"+tmp2;
if(dp.find(tmp)==dp.end())
q.push(tmp);
dp[tmp]+=dp[n];
dp[tmp]=dp[tmp]%mod;
}
else if(pa==1)
{ string tmp1,tmp2,tmp;
tmp1=n.substr(0,i);
tmp2=n.substr(j+1,n.length()-j);
tmp=tmp1+"a"+tmp2;
if(dp.find(tmp)==dp.end())
q.push(tmp);
dp[tmp]+=dp[n];
dp[tmp]=dp[tmp]%mod;
}
else if(pb==1)
{ string tmp1,tmp2,tmp;
tmp1=n.substr(0,i);
tmp2=n.substr(j+1,n.length()-j);
tmp=tmp1+"b"+tmp2;
if(dp.find(tmp)==dp.end())
q.push(tmp);
dp[tmp]+=dp[n];
dp[tmp]=dp[tmp]%mod;
}
}
}
}
int ans=0;
for(map<string,int>::iterator it=dp.begin();it!=dp.end();it++)
{ ans+=dp[it->first];//cout <<it->first << " : "<<dp[it->first] << "\n";
}
cout << ans << "\n";
}
}
is there a better solution possible. and how to do that.
Also can anyone provide a detailed explanation for problem A and C.
#include<map>
#include<iostream>
#include<string>
#include<queue>
using namespace std;
#define mod 1000000007
struct CompareMethod
{
bool operator()(const std::string &a, const std::string &b) const
{
if(a.length()>b.length())
return 0;
return 1;
}
};
int main()
{
int t;
cin >> t;
while(t--)
{
string s;
cin >> s;
map<string,int>dp;
priority_queue<string,vector<string>,CompareMethod>q;
dp[s]=1;
q.push(s);
while(!q.empty())
{
string n=q.top();
//cout << n <<"\n";
q.pop();
for(int i=0;i<n.length();i++)
{
for(int j=i+1;j<n.length();j++)
{ bool pa=0,pb=0;
for(int k=i;k<=j;k++)
if(n[k]=='a')
pa=1;
else
pb=1;
if(pa==1 && pb==1)
{ string tmp1,tmp2,tmp;
tmp1=n.substr(0,i);
tmp2=n.substr(j+1,n.length()-j);
tmp=tmp1+"a"+tmp2;
if(dp.find(tmp)==dp.end())
q.push(tmp);
dp[tmp]+=dp[n];
dp[tmp]=dp[tmp]%mod;
tmp1=n.substr(0,i);
tmp2=n.substr(j+1,n.length()-j);
tmp=tmp1+"b"+tmp2;
if(dp.find(tmp)==dp.end())
q.push(tmp);
dp[tmp]+=dp[n];
dp[tmp]=dp[tmp]%mod;
}
else if(pa==1)
{ string tmp1,tmp2,tmp;
tmp1=n.substr(0,i);
tmp2=n.substr(j+1,n.length()-j);
tmp=tmp1+"a"+tmp2;
if(dp.find(tmp)==dp.end())
q.push(tmp);
dp[tmp]+=dp[n];
dp[tmp]=dp[tmp]%mod;
}
else if(pb==1)
{ string tmp1,tmp2,tmp;
tmp1=n.substr(0,i);
tmp2=n.substr(j+1,n.length()-j);
tmp=tmp1+"b"+tmp2;
if(dp.find(tmp)==dp.end())
q.push(tmp);
dp[tmp]+=dp[n];
dp[tmp]=dp[tmp]%mod;
}
}
}
}
int ans=0;
for(map<string,int>::iterator it=dp.begin();it!=dp.end();it++)
{ ans+=dp[it->first];//cout <<it->first << " : "<<dp[it->first] << "\n";
}
cout << ans << "\n";
}
}