TEAMNAME - Editorial

[admin]

Use this for anything related to plagiarism - Reporting cheating, appeals, etc

Ideally, if you want to report that some users have cheated, or if you want to appeal against having been caught for plagiarism, you should only send an email to help@codechef.com, and wait for a few weeks to get a reply. But despite this instruction, if you do feel that you need to say something publicly, you can use this topic. Any other new topic that you start related to this will be closed, and you will also risk getting suspended.

[m_manas_s]

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";
    }
}

[aakaskrsingh1]

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

[anon10218360]

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…

[harish860]

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

[tushar_patil]

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

[unnoticed]

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

[saksham_s]

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;
    }

[akshay_012]

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];
}

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

[sevlll]

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

[akshay_012]

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 )

[karan51ngh]

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;
}

}

[sangkv97]

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

[tadek]

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

[shivansh961]

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;
}

[theyk]

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

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)

[rohanrtd9]

Alternate approach-
Given problem can be solved using bit set as well-

1. We give distinct bit id to each prefix alphabet( e.g let x=1 b=10 c=100 etc in case we have 3 alphabets in prefixes)

2. We maintain a map of suffixes where <suffix, val>, here val is an integer bitset and 1 bit represents prefixes that make funny word so if we have a funny words xbad, bbad; then ‘bad’ suffix will have val as 011 (continuing from example in point 1 taking 'x’and ‘b’ will result in funny word [hence bit 1 and 2 is set to 1] while taking ‘c’ will not so 3rd bit which belongs to ‘c’ is 0)

3. Then we iterate over set of distinct suffixes (let it be suffix) and take its XOR with all other suffixes (let it be suffix1)
   , let it be called res (result)

4. We take then take AND of res&suffix and call it m, and similarly res&suffix1 and call it n, then number of possible solutions between given pair of suffixes is bit_count(m)*bit_count(n) ( bit_count(n)bit_count(m) is taken next time when same pair is taken in reverse order)
   eg-
   let suffix ‘bad’ has val of suffix is 1010101
   and ‘cat’ has value of suffix1 val 1111100 then
   res is 0101001
   and m=0000001 & n=0101000 so possible ways is bit count(m) bit count(n)
   2 * 1 is our answer for given pair

5. We add this value to count and print the result once all pairs is done
   O(sufixf^2) is time complexity achieved

   Python solution- CodeChef: Practical coding for everyone

[kuldeep_11194]

great approach…

[priyabratamaji]

Time complexity is not O(n^2) in editorial

[anon79442027]

my O(n^2) solution gives TLE
https://www.codechef.com/viewsolution/48245664