How to avoid TLE in CHEFSHIP

general
1

To all those who are getting TLE in CHEFSHIP , your code is giving TLE on those strings in which all the characters are the same
There is some fixed answer for those special strings , try to figure it out !
:slight_smile:

2 Likes
2

what is wrong in my code?

cook your dish here

def ans(s,i,j,c=0):
    N=len(s)
    if 2*i>=len(s):
        return c
    elif (N-(2*i))%2!=0:
        j=(N-2*(i+1))//2
        return ans(s,i+1,j,c)
    elif 2*i+j<len(s) and s[:int(i)]==s[int(i):int(2*i)] and s[2*i:2*i+j]==s[2*i+j:]:
        c+=1
        j=(N-2*(i+1))//2
        return ans(s,i+1,j,c)
    else:
        return ans(s,i+1,(N-2*(i+1))//2,c)
def main(s):
    d=Counter(s)
    for i in d:
        if d[i]%2!=0:
            return 0
    N=len(s)
    if N-2>0:
        return ans(s,1,(N-2)//2,0)
    else:
        return 0
t=int(input())
for _ in range(t):
    s=str(input())
    print(main(s))```
    
Or in which testcase it will fail?
3

one very smart observation is just find if all the character are same then return (1 + (n-4)/2)
And your code will get surely AC

1 Like
4

int n=s.length();
ll count=0;
for(int i=1;i<=(n/2)-1;++i)
{
if((s.substr(0,i)==s.substr(i,i)) && (s.substr(2*i,(n/2)-i)==s.substr((n/2)+i,(n/2)-i)))
{
count++;
}
}
cout<<count<<"\n";

try this.

6

What’s the reason behind this?

7

LOL you dont have to avoid TLE , testers themself avoided it

5 Likes
8

Here’s my solution using old school substr function. My AC submission

1 Like
9

This is ridiculous. My code is basically the same but I got a TLE 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

i think i am doing the same thing but getting TLE
My Submission - https://www.codechef.com/viewsolution/33308621

11

I think this is bcoz there are many calls of substr here

12

But the complexity of substr() is O(n). And the sum of lengths in any iteration will be |s| and in this case, n = |s| .

1 Like