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
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
- 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;
}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
Hi! S is vector of string, so it is literally 2d vector defined as 1d 
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
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 
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)Alternate approach-
Given problem can be solved using bit set as well-
-
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)
-
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)
-
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) -
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 -
We add this value to count and print the result once all pairs is done
O(sufixf^2) is time complexity achievedPython solution- CodeChef: Practical coding for everyone
great approach…
Time complexity is not O(n^2) in editorial