i don’t think rated or unrated is such a big deal. just improve 
4 Likes
Though the idea seems correct, but I think it would still fail because of TLE, correct me If I am wrong but using this approach requires traversing the substring between L to R. Doing this for each query would result into a run time complexity of O(N^2) in the worst case. While the constraints only permit a complexity of O(N*log(N)).
Correct me If I am wrong.
1 Like
I got a WA instead of a TLE. So, something fishy is going on…
1 Like
Yes, right now I was trying to do just that.
Can anyone point out the error in this?
https://www.codechef.com/viewsolution/26015287
I didn’t read the question carefully and assumed that we have to return the max length of the valid substring…wasted a lot of time 
Yup. My bruteforce like approach got TLE.
“YES” and “NO”, not “Yes” and “No”
1 Like
- It should be r-l<3
- You need to run two loops separately till n-2 and n-3 so that you don’t access array values out of bound.
- This will timeout because it’s O(n*q)
NVM at least you tried. Too bad, I couldn’t realize this simple thing(since you want a character to repeat more than N/2 times, therefore one such character must always occur at alternate positions(and at contiguous positions at least once). I am such a noob 
1 Like
Yeah that applies to codechef as well 
1 Like
For a character to be a majority character in a string, it definitely shall be a majority element in a substring of size 3. So, I create a count table to calculate count of each character in the prefix till index i. Then for each substring of size 3, I find if there is an element that appears more than once. Incase there is such element, I increment prefix count. This prefix count stores the number of valid length 3 substrings with a majority element till index i.
Now, for each query, in O( 1 ), we can check if there is any substring of length 3 between l to r with a majority element by comparing prefix[r] and prefix[l + 1]( because prefix[l + 2] will store a substring of length 3 starting from index l.
My submission: CodeChef: Practical coding for everyone (Didn’t give contest but yeah)
3 Likes
I had thought of checking the substring of size 3 only…but okay wow didn’t think so much ahead!
Thanks a lot XD
Sorry bro but I disagree with all your statements.
- r-l < 2 is correct because it’s inclusive. So if l = 2 and r = 4, it should pass as S[2]…S[4] is a valid substring of length 3.
- It doesn’t access out of bound and all elements are covered in this loop too.
- It runs in time, but gets a WA. Complexity is not the issue here I guess, it’s the logic.
it should be r-l+1
// 20 char
Finally you will be 4 stars then? XD
Dammmn some people be carrying sick templates 
1 Like
Kabhi bhi kuch bhi kaam aajataa hai…
1 Like
too many templates…
Yes first point is wrong. Sorry for that.
Second one is misleading too. I should sleep now xD I meant you can miss last two index check for this loop.
Third applies when WA will not come. Consider a string like abcdef…xyzabcd…xyzaa and every query from 1 to 10^5
1 Like