# Brute Force passed in (Chef, Chefina and Their Friendship)

I read many codes and they apply brute force and it passes how?

``````def get_ans(string):
n = len(string)
ans = 0
for i in range(2,n,2):
if(string[:i//2]==string[(i//2):i]):
if(string[i:((n+i)//2)] == string[(n+i)//2:n]):
ans += 1

print(ans)
``````

This solution is passed but I did this why i got tle?

``````bool valid(string s,lli start,lli end){
lli i =start;
lli j = (start+end)/2;
lli mid = j;
while(i<mid and j<end){
if(s[i]!=s[j])
return false;
i++;
j++;
}
return true;
}

int main(){
fastio
lli t=1;
cin>>t;
chandan2();
while(t--) {
string s;
cin>>s;
lli cnt=0;
lli n=sz(s);
for(lli i=2;i<=n-2;i+=2){
if(valid(s,0,i) and valid(s,i,n))
cnt++;
}
cout<<cnt<<endl;
}
return 0;
}``````
3 Likes

One case that was causing TLE to my brute force solution was when all the characters are same. Handling it separately by answering (n-2)/2 . It passed all test cases.

Same here. I killed so much of my time coding and debugging a Rabin-Karp style approach with expected time complexity O(n). Still it got TLE. Whereas people using substrings in C++ have got AC.

1 Like

Codechef sucks in strong and sheer stress testing !!

7 Likes

Exactly, I tried Z-function and saw the amount of people that solved it and doubted my solution.

Same here , I spent lot of time optimising it using longest prefix suffix array that we calculate in KMP algorith whereas bruteforce solution got passed of many guys. Thats really bad.

``````def get_ans(string):
n = len(string)
ans = 0
for i in range(2, n, 2):
if (string[:i // 2] == string[(i // 2):i]) and (string[i:((n + i) // 2)] == string[(n + i) // 2:n]):
ans += 1

print(ans)

for _ in range(5):
string = "a"*(10**5)
get_ans(string)
``````

This solution get TLE in CC compiler as in question already mention that sum of length o string in all test case may be upto 10^6 now see this above solution …it will give TLE

@rishup_nitdgp @admin this is so wrong that even brute force runs and very weak test cases 1 Like

Just poor test cases. It just shows that the author is partial towards certain languages(c++). Its true that c++ is very popular, but I didn’t expect such things from official codechef contests.
example-CodeChef: Practical coding for everyone and CodeChef: Practical coding for everyone

LOL. I used substrings in C++ and got a TLE verdict thrice.

``````#include <bits/stdc++.h>

using namespace std;

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
string s;
cin >> s;
int n = s.size();
int c = 0;
for (int i = 1; i < n/2; ++i)
{
c += (int)(s.substr(0, 2*i).substr(0, i) == s.substr(0, 2*i).substr(i, i) && s.substr(2*i, n-2*i).substr(0, (n-2*i)/2) == s.substr(2*i, n-2*i).substr((n-2*i)/2, (n-2*i)/2));
}
cout << c << '\n';
}
}
``````

@admin @rishup_nitdgp q2 should be judged again with strong test case

5 Likes

Why am I Getting TLE in Below Question in May Cook-Off? I too Similar to this!

My Solution :

Tell me one thing (anyone tell me) why same type of solution ( Brute force) when we use substr function in c++ it will be accepted but when i make my own substr function or let’s say function to check validity (as i mentioned abve) it got tle ? Is “Substr” function is faster?
and one more thing why substr function of java give TLE while C++ give AC verdict ?

2 Likes

I know it’s frustrating and I might sound biased but I don’t think that would be fair, since a lot of people who submitted using substr() (including me) would’ve tried other string matching methods if they got a TLE. But I left the question and went to the next because it was AC.

I think they should rather rejudge with test cases so that all O(n^2) codes(that are correct) pass. That would be fair to everyone

Bro i got TLE using substr!

My Submission-CodeChef: Practical coding for everyone

I don’t find any other efficient way of extracting substring from string other than substr

The standard library `substr` is probably faster because the compiler knows exactly what it does and can optimize it better. Java is often slower than C++ so a solution that TLEs in Java and ACs in C++ is normal.

But CC allows multiplier for JAVA as in c++ if Time lmit is 1 sec then in java its 2 I think ?

Who said it got accepted? I was pissed because I got TLE thrice. So there’s no issue with a custom `substr()` function. I believe that the test cases are poor.

I agree that rejudging with strong tests isn’t ideal but I think what you’re suggesting is worse. If we let all O(N^2) solutions pass then all the people who were naive enough to try a brute force gets AC quickly while all the people who correctly determined that O(N^2) should be too slow wasted a bunch of time implementing the intended solution.

2 Likes

see this my solution using substr func (after contest) → CodeChef: Practical coding for everyone

1 Like

bhai…there are sites where all languages have same time limit.
codechef atleast has 5X for python.
if u are using python from so long…then u should know when it works
and when to use c++.