TLE in CHEFSHIP(CookOff)

general
, ,
1

I don’t know why i am getting TLE in CHEFSHIP.
Problem Link- CodeChef: Practical coding for everyone
My Submission - CodeChef: Practical coding for everyone

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!

2

Anyone Please help.
Thanks in advance!

3

Use hashing/some string algo

1 Like
4

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
5

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

6

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
7

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

1 Like
8

Thank you so much i will see to it.

9

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

10

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

1 Like
12

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

13

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
14

I am not applying bruteforce

15

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
16

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

17

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
18

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

19

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

1 Like
20

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

21

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