TEAMNAME - Editorial

PROBLEM LINK:

Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest

Author: Vsevolod Lepeshov
Tester: Felipe Mota and Radoslav Dimitrov
Editorialist: Vsevolod Lepeshov

DIFFICULTY:

Easy

PREREQUISITES:

Strings, Bruteforce

PROBLEM:

There are N funny words s_1, s_2, \dots, s_N.
You have to calculate the number of ways to choose two words such that they are not funny, but if we swap the first letters in them, the resulting words are funny.

QUICK EXPLANATION:

Divide all words in two parts - first letter and whole word except first letter.

Numerate 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)).

Iterate over first letter in both words (26 * 26 options), let’s call f_1 - first letter in first word, f_2 - first letter in second word.

Iterate over n “compressed” suffixes. Let’s calculate cnt_{01} - number of suffixes such that there is not funny word which starts with f_1, but there is funny word that starts with f_2, and cnt_{10} - number of suffixes such that there is not funny word which starts with f_2, but there is funny word that starts with f_1.

The number of good team names with this first letters is cnt_{01} * cnt_{10}, so the answer is the sum of this values over all first letters in both words.

Total asymptotics: O(|s_i| * n * log(n) + 26 * 26 * n)

EXPLANATION:

Each word contains two parts - first letter and “whole word except first letter”. Let’s call “whole word except first letter” - suffix.
For example word “abba” have first letter “a” and suffix “bba”.

Let’s call f_i - number of first letter of s_i. 0 \le f_i \lt 26.

Note that we do not need the suffixs of the words themselves to solve the problem. The only thing we need is to quickly understand whether the suffixes of some words are equal.

So, we will construct array c_1, \dots, c_n such that the suffixes of s_i and s_j are equal if and only if c_i and c_j are equal.

One way to build such array is to sort all the words, and for the word s_i, set c_i as “The number of words lexicographically smaller than s_i”. This technique is called coordinate compression.

The second way: just use the map<string, int> (or dict in Python) which return c_i by suffix of s_i. Iterate over all suffixes: if suffix of s_i already in map you know c_i for it, else you can assign new c_i for this suffix and add it to map.

After that each word can be coded by pair - (f_i, c_i).

Let’s construct boolean 2d array isword[26][n]. isword[i][j] means - “Is there a word that coded by pair (i, j).” So, we will set isword[f_i][s_i] = true for all i from 1 to n, and false for other cells.

We want to understand when (X_1, Y_1), (X_2, Y_2) is good teamname. If it is good teamname - words (X_1, Y_1) and (X_2, Y_2) are not funny, but words (X_2, Y_1) and (X_1, Y_2) are funny. In other words:
isword[X_1][Y_1] = false
isword[X_2][Y_2] = false
isword[X_1][Y_2] = true
isword[X_2][Y_1] = true

Let’s iterate over first letters - X_1 and X_2. We want to count number of good teamnames such that first words starts with X_1 and second with X_2. We will sum this values over all X_1 and X_2 to get final answer.

Iterate over all suffixes and count number of Y_1 such that
isword[X_1][Y_1] = false
isword[X_2][Y_1] = true
Let’s call this number cnt_{01}

Also let’s count number of Y_2 such that
isword[X_2][Y_2] = false
isword[X_1][Y_2] = true
Let’s call this number cnt_{10}

So (X_1, Y_1), (X_2, Y_2) is good teamname if and only if Y_1 is in one of cnt_{01} values, and Y_2 in one of cnt_{10} values. So the total number is cnt_{01} * cnt_{10}. Sum this values over all X_1, X_2 to get final answer.

ALTERNATE EXPLANATION:

SOLUTIONS:

Setter's Solution
#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;
        // Actually, we can 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 is "all string except first letter"
            suffixes.pb({suf, i});
        }
        // Now we will compress all suffixes
        // We want to make array which have property:
        // "suffixes i and j are equal if and only if compress_i == compress_j"
        // It is simple to construct this array after sorting all suffixes
        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] means "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;
        }
        // Now we will bruteforse 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++) {
                // We will 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';
    }
}

VIDEO EDITORIAL:

6 Likes

Very nice editorial with a nice approach! For the problem, even a less efficient O(n^2) solution passes.

@admin I want to report a plag solution, where shall I do?

2 Likes

mine didn’t pass

1 Like
2 Likes

I did an O(n^2) solution with string hashing, it didn’t work for one task (TLE) . Can somebody please help, TIA.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<long long, long long>
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define eb emplace_back
#define ff first
#define ss second
#define lc(p) (p << 1)
#define rc(p) (p << 1) | 1
#define ps(x, y) fixed << setprecision(y) << x
#define mk(arr, n, type) type *arr = new type[n]
#define range(a, b) substr(a, b - a + 1)
#define trace(x) cerr << #x << ": " << x << endl
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define input(arr,n) FOR(i,0,n) cin>>a[i]
#define FOR(i,k,n) for ( int i=k; i<n; i++ )
#define ROF(i,k,n) for ( int i=k; i>n; i-- )
#define ll long long

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 20;
const int mod = 1e9 + 7;
const int base = 33;
 
int add(int a, int b, int mod){
    int res = (a + b) % mod;
    if(res < 0)
        res += mod;
    return res;
}
 
int mult(int a, int b, int mod){
    int res = (a * 1LL * b) % mod;
    if(res < 0)
        res += mod;
    return res;
}
 
int power(int a, int b, int mod){
    int res = 1;
    while(b){
        if((b % 2) == 1)
            res = mult(res, a, mod);
        a = mult(a, a, mod);
        b /= 2;
    }
    return res;
}
 
int pw[N];
int inv[N];
 
void precalc() {
    pw[0] = 1;
    for(int i = 1; i < N; i++)
        pw[i] = mult(pw[i - 1], base, mod);
    
    int pw_inv = power(base , mod - 2 , mod);
    inv[0] = 1;
    for(int i = 1; i < N; i++)
        inv[i] = mult(inv[i - 1], pw_inv, mod);
}
 
int build(string s){
    int n = s.length();
    int k= 0;
    for(int i = 0; i < n ; ++i){
       k = add((i == 0) ? 0 : k, mult(pw[i], s[i] - 'a' + 1, mod), mod);
    }
    return k;
}
 
int getHash(int x , int y, int H[N]){
    int res = add(H[y], (x == 0) ? 0 : -H[x - 1], mod);
    res = mult(res , (x == 0) ? 1 : inv[x], mod);
    return res;
}

void fnc()
{
    int n;
    cin>>n;
    precalc();
    string a[n];
    int H[n];
    unordered_map<int,int> m;
    FOR(i,0,n)
    {
        cin>>a[i];
        H[i] = build(a[i]);
        m[H[i]]=1;
    }

    int ans=0;

    FOR(i,0,n-1)
        FOR(j,i+1,n)
        {
            int s1 = H[j]-(a[j][0]-a[i][0]);
            if (m[s1]==1)
                continue;
            int s2 = H[i]-(a[i][0]-a[j][0]);
            if ( m[s2]!=1 )
                ans+=2;
        }
    cout<<ans;
}

int main(){
    FIO;
    int n;
    cin>>n;
    FOR(i,0,n)
    {
        fnc();
        cout<<"\n";
    }
}

Can somebody help me, why this didn’t pass the second last test case of the Subtask-2? I got TLE. Please let me know what I am doing wrong. If O(n^2) is fine in the Editorial, then it must be fine for me as well!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        FastReader sc=new FastReader();
          int t=sc.nextInt();
          while(t-- > 0)
        {int n=sc.nextInt();
        int count=0;
            HashSet<String> set=new HashSet<>(n);
          String input=sc.nextLine();
          String[] inputs;
          inputs=input.split(" ");
          for(String a:inputs)
           set.add(a);
            //System.out.println(set);
            //System.out.println("All pair possible!");
          for(int i=0;i<n;i++)
          {
              for(int j=0;j<n;j++)
              {
                  if(i!=j)
                  {
                      StringBuilder a= new StringBuilder(inputs[i]);
                      StringBuilder b = new StringBuilder(inputs[j]);
                      //debugging System.out.println(a.toString()+" "+b.toString());
                      a.setCharAt(0,inputs[j].charAt(0));
                      b.setCharAt(0,inputs[i].charAt(0));
                      //debugging System.out.println("Not Funny Test Candidates+"+a.toString()+" "+b.toString());
                      boolean notfunny= set.contains(a.toString())== false && set.contains(b.toString())==false;
                      if(notfunny)
                      {
                          count++;
                      }
                  }
              }
          }

            System.out.println(count);

        }
    }//main ends here
    //FastReader Integration

    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }//Fast Reader

}//class

1 Like

I guess your solution is slowing down due the .substr() function(especially the string concatenation step in the bool same() function) by testing your code against some large input, portion wise. Sorry I don’t know a quick fix for this…

t=int(input())
while t>0:
n=int(input())
l=list(map(str,input().split()))
k=dict.fromkeys(l,1)
k1={}
k2={}
for i in l:
try:
k1[i[1:]]+=1
k2[i[1:]].add(i[0])
except KeyError:
k1[i[1:]]=1
k2[i[1:]]={i[0]}
ans=0
for i in k2:
for j in k2:
c=len(k2[i].intersection(k2[j]))
c1=len(k2[j].intersection(k2[i]))
ans+=(k1[i]-c)*(k1[j]-c1)
print(ans)

t-=1
  1. List item

Bro, I guess editorial is talking about O(26 *26 *N) in last loop, before that it has sort which will be O(|si|*n*logn) , please check setter’s solution , effectively editor solution is O(NLogN) around, while yours is O(N^2), which will jump out of 10^8 or 10^9 giving TLE for 1 second time limit

Why are we multiplying cnt_10*cnt_01?
ans += cnt_10 * cnt_01;

Can someone please tell me why my solution is giving TLE in one subtask. I am using 2 loops only which will be of O(n^2) and using unordered map which takes O(1) time on an average to traverse.
I am attaching a screenshot of result as well.It would be great help. Thanks in advance.

 #include<bits/stdc++.h>
    using namespace std;
    typedef long long int ll;
    const ll mod =1e9+7; 


    int main()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);

        #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        #endif
        
        ll t;
        cin>>t;
        while(t--)
        {
            ll n;
            cin>>n;
            vector<string> v,ans1[30];
            unordered_set<string> alpha[30],words;
            unordered_map<string,ll> m ;
            string s;
            for(ll i=0;i<n;i++)
            {
                cin>>s;
                v.push_back(s);
                m[s]=1;
            }
            ll count = 0;
            ll size = v.size();
            for(ll i=0;i<size;i++)
            {
                for(ll j=i+1;j<size;j++)
                {
                    string a = v[i];
                    string b = v[j];
                    char c = a[0];
                    char d = b[0];
                        a[0] = d;
                        b[0] = c;   
                        if(m[a]!=1&&m[b]!=1)
                        {
                            count+=2;
                        }
                    
                }
            }
            cout<<count<<endl;
        }
        
        return 0;
    }
1 Like

vector S(n);
for (int i = 0; i < n; i++) {
cin >> S[i];
}
//cout<<S[0]<<endl;
vector<pair<string, int>> suffixes;
// Actually, we can 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]; :point_left:
}

how we can access vector to like a 2d vector it is defined as 1d

Hi! S is vector of string, so it is literally 2d vector defined as 1d :slight_smile:

can u please elaborate or give ex. or text where i can read about this
that if we defined vector of string (it will work as 2d )

i created 2 sets 1 containing all the first letters and the second containing all the sub-strings without the first letter. so using the product rule(PnC) the answer should be n(Set-1)*n(Set-2) - the number of funny names.

My solution passes all the test cases, can someone suggest why i’m not able to pass this.

#include
#include
using namespace std;
int main()
{
long long T;
cin >> T;
long long t = T;
long long arr[t];
long long I = 0;

while (T--)
{
    long long N;
    cin >> N;
    set<char> Ch;
    set<string> St;
    string W[N];

    for (long long i = 0; i < N; i++)
    {
        cin >> W[i];
    }
    for (long long i = 0; i < N; i++)
    {
        Ch.insert(W[i][0]);
        St.insert(W[i].substr(1));
    }
    arr[I++] = Ch.size() * St.size() - N;
}
for (long long i = 0; i < t; i++)
{
    cout << arr[i] << endl;
}

}

Man I did the same thing and still got TLE on 2nd last. Even I used O(n^2)
Someone help

The solution in the editorial is O(n log(n)). If you have O(n^2) it will not work. Just in case someone else falls in to this trap :slight_smile:

It’s showing TLE in last 2 test cases , can anyone help me with it

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

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t,n;
char a,b;
cin>>t;
while(t–)
{
cin>>n;
vectors;
string a1,b1,aa;
for(int i=0 ; i<n ; i++)
{
cin>>aa;
s.push_back(aa);
}
int count=0;
for(int i=0 ; i<n-1 ; i++)
{
for(int j=i+1 ; j<n ; j++)
{
a=s[i][0];
b=s[j][0];
a1=s[i];
b1=s[j];
a1[0]=b;
b1[0]=a;
if(s[i][0]!=s[j][0] && (find(s.begin() , s.end() , a1) == s.end() && find(s.begin() , s.end() , b1) == s.end()))
count=count+1;
}
}
count=2*count;
cout<<count<<"\n";
}
return 0;
}

Python Snippet . The guy in the video explains much clearer than the script below :grinning:

test = int(input())
for _ in range(test):
    n = int(input())
    arr =  input().split()
    suffixDict ={}
    for i in arr:
        if suffixDict.get(i[1:])== None:
            suffixDict[i[1:]]=[i[0]]
        else:
            suffixDict[i[1:]].append(i[0])
   
    ans=0
    iteratingArray =list( suffixDict.keys())
    for i in range(len(iteratingArray)):
        for j in range(i+1,len(iteratingArray)):
            setA = set(suffixDict[iteratingArray[i]])
            setB = set(suffixDict[iteratingArray[j]])
            comm = len(setA.intersection(setB))
            ans+= 2* (len(setA)-comm) * (len(setB)-comm)
            
    print(ans)