Team Name Codechef Problem With Solution

For today we at geekstocode will solve a competitive programming question. Which is the team name codechef problem. This programming question was asked in the Codechef February 2021 long challenge.

Thus, learning this problem will help you clear your concepts about strings and arrays. Moreover, this problem is a very important question for competitive coding challenges. Additionally, if you learn Team Name Codechef Solution, you will be able to solve many related problems easily.

Hence, without much delay, let’s get our coding brains to use and get started! 

Prerequisites to solving the Team Name Problem:

The two major and only prerequisites for solving the Team Name problem are Bruteforce algorithm and strings.

We have many articles and posts on strings to give a brief about them. Thus, make sure to check them out to recap your knowledge about strings. 

Therefore, let’s move on to the Bruteforce algorithm. 

As the name suggests, the brute force algorithm is the most straightforward way to approach and solve a problem. Hence, it checks all possible states of a problem to reach a solution. 

Hence, to understand it better, let us take a scenario.

For instance, if we have to find out the number of divisors of a number by the brute force method. 

n=16.

Then you will check the all numbers from 

1 to 16 which will divide  16

So we code it like this, 

  1. int divisor_count=0,n=16; 
  2. for (i =1;i<=n;i++) 
  3. if (n÷i==0) divisor_count++; 

Additionally, normal c code elaborates this algorithm. The above block of code is the brute force method to calculate the divisors of n.  Thus, for the total number of iterations, time complexity of this algorithm will be, 

O(n)O(n). But if we modify with more efficiency, it can reduce to, O(√n).

Problem Statement:

Сhef has assembled a football team! Now he needs to choose a name for his team. There are N words in English that Chef considers funny. These words are s1,s2,…,sN.

Chef thinks that a good team name should consist of two words such that they are not funny, but if we swap the first letters in them, the resulting words are funny. Note that under the given constraints, this means that a word is a non-empty string containing only lowercase English letters.

Can you tell Chef how many good team names there are?

Input

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains a single integer N.

The second line contains N space-separated strings s1,s2,…,sN.

Output

For each test case, print a single line containing one integer — the number of ways to choose a good team name.

Constraints

1≤T≤100

2≤N≤2⋅104

2≤|si|≤20 for each valid i

s1,s2,…,sN contain only lowercase English letters

s1,s2,…,sN are pairwise distinct

the sum of N over all test cases does not exceed 2⋅104

Subtasks

Subtask #1 (20 points): s1,s2,…,sN contain only letters ‘a’ and ‘b’

Subtask #2 (80 points): original constraints

Example Input

3

2

suf mas

3

good game guys

4

hell bell best test

Example Output

2

0

2

Explanation

Example case 1: The good team names are (“muf”, “sas”) and (“sas”, “muf”).

Second, Example case 2: There are no good team names because all funny words start with ‘g’.

Finally, Example case 3: The good team names are (“hest”, “tell”) and (“tell”, “hest”).

Team Name Codechef Solution:

Program:

#include <bits/stdc++.h>

#define pb push_back
#define ld long double
using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<string> S(n);
        for (int i = 0; i < n; i++) {
            cin >> S[i];
        }
        vector<pair<string, int>> suffixes;
        // We can also divide string in 2 parts - "first letter" and "all string except first letter"
        for (int i = 0; i < n; i++) {
            string suf = "";
            for (int x = 1; x < (int) S[i].size(); x++) {
                suf += S[i][x];
            }
            // suf will be taken as all strings except the first letter. 
            suffixes.pb({suf, i});
        }
        // Now we will compress all suffixes. Because we want to make array with property:
        // "suffixes i and j are equal if and only if compress_i == compress_j"
        //Then, we sort the suffixes since it is simple to construct this array.
        sort(suffixes.begin(), suffixes.end());
        vector<int> compress(n);
        for (int i = 1; i < n; i++) {
            if (suffixes[i].first == suffixes[i - 1].first) {
                compress[suffixes[i].second] = compress[suffixes[i - 1].second];
            } else {
                compress[suffixes[i].second] = 1 + compress[suffixes[i - 1].second];
            }
        }
        // is_word[i][j] signifies the statement "is there a funny word with first letter number i, and suffix with "compress number" j"
        vector<vector<bool>> is_word(26, vector<bool>(n, false));
        for (int i = 0; i < n; i++) {
            // for i-th word we set needed is_word cell to true
            is_word[S[i][0] - 'a'][compress[i]] = true;
        }
        // Next, we will use the bruteforce for  first letters in both words in good team name
        int ans = 0;
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                // Then, we iterate over all n possible suffixes
                int cnt_10 = 0, cnt_01 = 0;
                for (int x = 0; x < n; x++) {
                    if (is_word[i][x] && !is_word[j][x]) {
                        cnt_10++;
                    } else if (!is_word[i][x] && is_word[j][x]) {
                        cnt_01++;
                    }
                }
                // We can combine each "01" suffix with each "10" suffix, so in total cnt_10 * cnt_01
                ans += cnt_10 * cnt_01;
            }
        }
        cout << ans << '\n';
    }
}


Program Explanation:

We first divide all words in two parts – first letter and whole word except first letter.

Then, we numbered the first letters with numbers from 0 to 25.  And whole word except first letter from 0 to n using coordinate compression or map or hashes, which works in 

O(|s_i| * n * log(n)). 

Then, we Iterate over first letter in both words which gives 26 x 26 possibilities. For instance, Let us assume the f1 as the first letter in first word and f2 as first letter in second word.

After that, we iterate over n which is the variable for compressed suffixes. We then calculate cnt01 which will be the number of suffixes that there is not a funny word which will start with f1. But there is a funny word which starts with f2 and cnt10 will now be the number of suffixes such that there is not a funny word which starts with f2. But there is a funny word which starts with f1.

Finally, we calculate the number of good team names with this first letters  with the formula cnt01 *cnt10 . 

Therefore, the answer is the sum of this value over all the first letter in both words. 

And, total asymptotics : O(∣si​∣∗nlog(n)+26∗26∗n). 

Conclusion:

In conclusion, the Team Name codechef problem is an easy problem. With some basic idea about strings and other algorithms, you can easily solve this competitive coding problem. 

Moreover, the solution we have provided is only one of many approaches to the problem. You can try to understand and code on your own if you understand the concept. 

Thus, practice as many coding problems as possible to brush up your programming skills. 

If you have any doubts in Team name codechef solution, we would love to assist you.

See you in our next post!

Leave a Comment

Your email address will not be published. Required fields are marked *