TLE in CHEFSHIP(CookOff)

I don’t know why i am getting TLE in CHEFSHIP.
Problem Link- https://www.codechef.com/COOK118B/problems/CHEFSHIP
My Submission - https://www.codechef.com/viewsolution/33308621

i know that complexity of substr is O(n)

Can anybody tell any alternative way to extract substring from a string in an efficient way except substr
or
Can anybody point out a mistake so that i can change something in my code and get AC?

Thanks in Advance!

Anyone Please help.
Thanks in advance!

Use hashing/some string algo

1 Like

Which one would be best suitable for this particular problem? I want to learn it so that I can get rid of the TLE on my own.

1 Like

Thanks @galencolin for your kind reply.
Can you elaborate?

Something like this. What you want is to get the hash of any substring in quick (like O(1)) time, then you can just try every length, so the complexity would be O(N) to hash and O(1) per O(N) lengths, leading to O(N) in total.

4 Likes

@zephxr can you plz explain your approach… I too used substr() and got AC in C++.

1 Like

Thank you so much i will see to it.

I stored all possible segment length in a vector pair and iterated and checked the condition using substr but getting TLE

My Submission - https://www.codechef.com/viewsolution/33308621

I did a pretty straightforward code using subtsr function and it got accepted, have a look. My submission for AC

1 Like

Bro Can You Tell where i am getting wrong.I am doing the same thing which you are doing.

If you are trying to submit after the contest with brute force method you would get tle as test cases have been changed.

1 Like

I am not applying bruteforce

It is a brute force solution. You could have optimised it. You need not take substrings so many times. Apart from that string mapping can be done in constant time using hashing

2 Likes

But many users got AC with the method i am doing.So i asked.

Now test cases have been changed. At the time of contest if you would have done it by applying substr in a little optimized way yours would have passed as well. Test cases were weak so brute force solutions also passed.

2 Likes

Can you elaborate that optimized way?
I will learn something new

https://cp-algorithms.com/string/string-hashing.html
Read from this.

1 Like

No bro i am not talking about hashing.I was asking about using substr smartly which you were talking about.

Don’t make vectors of lengths rather use loop only:
int len=s.size()
int k =( len-2) /2
for(int i=1;I<=k;i++)
{
string b1, b2, c1, c2;
b1=s.substr(0, i) ;
b2=s.substr(i, i) ;
// do c1 c2 as well and compare b1, b2 and c1, c2
}
Your code consumes some extra time in vector operations and substring can be made only 4 times. It would have been accepted.

1 Like