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

general
1

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
2

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.

3

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
4

Codechef sucks in strong and sheer stress testing !!

7 Likes
5

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

6

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.

7 
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:

1 Like
8

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

9

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

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

5 Likes
11

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

Question Link (CHEFSHIP) :

My Solution :

1.) CodeChef: Practical coding for everyone

2.) CodeChef: Practical coding for everyone

12

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
13

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

14

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

15

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.

16

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

18

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.

19

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
20

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

1 Like
21

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++.