Help needed in TeamName problem

help
1

My code is giving tle just for one case.Please help me to optimize it.

image
image1364×699 23.2 KB

Here’s the code:

#include<bits/stdc++.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD 1000000007
#define ll long long int

int main() {

fastio;

int t = 1;
cin>>t;

while(t--) {
	int n;
	cin>>n;
	
	vector<string> names(n);
	unordered_set<string> s;
	for(int i = 0; i < n; i++) {
		cin>>names[i];
		s.insert(names[i]);
	}
	
	int ans = 0;
	
	for(int i = 0; i < n; i++) {
		string a = names[i];
		for(int j = i + 1; j < n; j++) {
			if(a[0] == names[j][0]) continue;
			
			string x = a[0] + names[j].substr(1);
			string y = names[j][0] + a.substr(1);
			if(s.find(x) != s.end() or s.find(y) != s.end()) continue;
			
			ans += 1;
		}
	}		
	
	cout<<ans * 2<<endl;
}

return 0;

}

1 Like
2

Your solution is O(N^{2})

You can’t optimize this method further.
Try to think of some other way of counting utilizing the given properties, so that you can count bunch of them together instead of counting them one by one.