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

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

22

I mean yea, In such a scenario nothing would be fair lol

23

What did I do wrong then? :sob:
Is there any slight modification that will help me get it accepted or should I entirely change my approach?

24

Inbuilt functions are optimised. Thats why they are generally faster.

25

i m nt using python…and i dont think python has “5x” time limit either…

26

I don’t think anything should be done now. I in fact did not submit thinking O(n*n) would not pass. Only thing is that from future they should take care of test cases.

1 Like