daayan's blog

By daayan, history, 5 years ago, In English

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
            k E darjadhav
     vijaysha N kar
          har D ikpandya
              R avindrajadeja
      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 string players[15]={"RohitSharma","ShikharDhawan","ViratKohli","KedarJadhav","VijayShankar","HardikPandya","RavindraJadeja","LokeshRahul","MahendraSinghDhoni","DineshKarthik","KuldeepYadav","YuvzendraChahal","MohammedShami","JaspritBumrah","BhuvneshwarKumar"};
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 pad[name.size()];
	reset(pad);
	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);
	}
	rep(i,0,name.size())pad[i]=mx-pos[i]+1;
	for(int i=0;i<name.size();i++){
		if(name[i]==' '){
			cout<<endl;continue;
		}
		for(int j=0;j<pad[i];j++)cout<<" ";
		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(){
	cout<<"Enter your name: \n"<<endl;
	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;
}	
  • Vote: I like it
  • +9
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by daayan (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

lmao, modern problems require modern solutions

»
5 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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.