How to solve Rich Substring(RICHSTR) from August 19 Cook-Off?

help
, , ,
1

Can anybody please share their approach?

1 Like
2

I was going for
if s[i] == s[i+1] or s[i] == s[i+2]
but that failed, idk why.
Every rich substring will satisfy this. Some examples:
aab , aba, abb
aaab, …
ababa,abbaa, …

1 Like
3

Me too. I checked for contiguous ones only, and it failed.

1 Like
4

Editorial will be uploaded soon :upside_down_face::upside_down_face:

1 Like
5

Looking forward to it! :smiley:

6

Yupp waiting for announcement also this might be unrated contest

7

what about if s[i+1]==s[i+2]? Including that, and keeping a list of the starting indexes of the 3-length rich strings should do the job.

8

That’s unfortunate, given that I somehow got a somewhat respectable rank(82) lol. I’m such a noob. XD

9

i don’t think rated or unrated is such a big deal. just improve :innocent:

4 Likes
10

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
11

I got a WA instead of a TLE. So, something fishy is going on…

1 Like
12

Yes, right now I was trying to do just that.
Can anyone point out the error in this?
https://www.codechef.com/viewsolution/26015287

13

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 :disappointed_relieved:

14

Yup. My bruteforce like approach got TLE.

15

“YES” and “NO”, not “Yes” and “No”

1 Like
16
  1. It should be r-l<3
  2. You need to run two loops separately till n-2 and n-3 so that you don’t access array values out of bound.
  3. This will timeout because it’s O(n*q)
17

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 :frowning:

1 Like
18

Yeah that applies to codechef as well :laughing:

1 Like
19

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
20

I had thought of checking the substring of size 3 only…but okay wow didn’t think so much ahead!
Thanks a lot XD