### daayan's blog

By daayan, history, 9 months ago, ,

One can use this program to find out whether your name exists in the Indian Cricket Team. The inspiration to create this came from Internet posts claiming that our Prime Minister Mr. Narendra Modi's name is so special that it exists in Team India's World Cup 2019 team. After running this program, there is a high probability that your or your friend's name might also be so special. I encourage you to try it out.

In case it's not clear, following is the output of the program on giving "Narendra Modi" as input:

 shikhardhawa N
rohitsh A rma
vi R atkohli
vijaysha N kar
har D ikpandya
lokeshr A hul

M ahendrasinghdhoni
m O hammedshami
D ineshkarthik
jaspr I tbumrah


I have implemented the program using simple backtracking. I would be interested in finding out more efficient methods to solve this problem.

#include <bits/stdc++.h>

using namespace std;

#define reset(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(int i=a;i<b;i++)
#define pb push_back

const int N =15;
vector<int> alpha_p[26];

void kata(){
cout<<"There is no team India in you :(\n";
exit(0);
}

int getnum(char c){
if(c>='a')return (int)(c-'a');
return (int)(c-'A');
}

bool getorder(int pos,string &name,vector<int> &order,bool *used)
{

if(pos>=name.size())return true;
if(name[pos]==' ')return getorder(pos+1,name,order,used);

int alpha_no=getnum(name[pos]);
for(int i=0;i<alpha_p[alpha_no].size();i++){
int v=alpha_p[alpha_no][i];
if(used[v])continue;
order[pos]=v;
used[v]=true;
if(getorder(pos+1,name,order,used)){
return true;
}
order[pos]=-1;
used[v]=false;
}
return false;
}

void display(vector<int> &v,string &name){
int pos[name.size()];
int mx=0;
for(int i=0;i<name.size();i++){
if(name[i]==' '){
pos[i]=0;continue;
}
int j=0;
while(getnum(players[v[i]][j])!=getnum(name[i]))j++;
pos[i]=j;
mx=max(mx,j);
}
for(int i=0;i<name.size();i++){
if(name[i]==' '){
cout<<endl;continue;
}
for(int j=0;j<pos[i];j++)cout<<(char)tolower(players[v[i]][j]);
cout<<" "<<(char)toupper(players[v[i]][pos[i]])<<" ";
for(int j=pos[i]+1;j<players[v[i]].size();j++)cout<<(char)tolower(players[v[i]][j]);
cout<<endl;
}
}

int main(){
string name;
getline(cin,name);
// name=remove_spaces(name);
if(name.size()>N)kata();
if(name.size()==0)kata();

rep(i,0,N){
rep(j,0,players[i].size()){
alpha_p[getnum(players[i][j])].pb(i);
}
}
vector<int> order(name.size(),-1);
bool used[N];
reset(used);
bool hua=getorder(0,name,order,used);

if(!hua)kata();

display(order,name);

return 0;
}


• +9

 » 9 months ago, # |   0 Auto comment: topic has been updated by Daayan (previous revision, new revision, compare).
 » 9 months ago, # |   +3 lmao, modern problems require modern solutions
 » 9 months ago, # |   +27 I believe you can model this problem as maximum matching in a bipartite graph. Imagine you have $n$ players in your team, and your name consists of $m$ letters. To model the problem, define a vertex $p_i \quad \forall 1 \leq i \leq n$ (for every player in the team), and also define a vertex $c_j \quad \forall 1 \leq j \leq m$ (for every letter in the name). Then, for the $i$-th player, you should add an edge $p_i \leftrightarrow c_j$ if the letter $c_j$ appears in the name of the $i$-th player. Finally, once you have modelled the problem in this way, an answer to the problem you propose can be found if the cardinality of a maximum matching equals $m$ (the amount of letters in the name).Hence, to solve this problem you can use your favorite maximum bipartite matching algorithm.