RICHSTR - EDITORIAL

CodeChef: Practical coding for everyone mine also please debugg

The hint is for you only :man_facepalming:

You’re unnecessarily printing “NO” after taking the input n and ignoring the string as well as the subsequent queries.

I did almost same thing but getting TLE …Can you check it…
https://www.codechef.com/viewsolution/26022099

It is giving tle because we are taking Q queries for every test cases. So you need to use FAST IO in this case. I submitted your code using fast IO.

So sorry and yes thank you also.

Add these 2 lines at the start of your main():

std::cout.sync_with_stdio(false);
cin.tie(0);

Oh thankyou very much :blush: :blush:

Hello @taran_1407 ! Sir, i tried to implement the approach you had described in the editorial , but somehow i am getting wrong answer . Could you please point out my mistake ? ( Thanks in advance ! )
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int b[5000001];

int query(int l,int r,int low,int high,int index)
{
if(l<=low&&r>=high)
return b[index];

if(l>high||r<low||l<r)
	return 0;

int mid=(low+high)/2;

return(query(l,r,low,mid,2*index)||query(l,r,mid+1,high,2*index+1));

}

int main()
{
int t,m,o,i,n,q,l,r;
string s;
cin>>t;

while(t--)
{
   cin>>n>>q;
   cin>>s;
   o=1;
   m=n-2;

   while(o<m)
   	o=o<<1;
   
  // cout<<o<<"\n";

   for(i=0;i<=4*o+1;i++)
   	 b[i]=0;

   	for(i=0;i<m;i++)
   	{
   		if(s[i]==s[i+1]||s[i]==s[i+2]||s[i+1]==s[i+2])
   			b[i+o]=1;
   	}
    
    for(i=o-1;i>0;i--)
    {
       b[i]=b[2*i]|b[2*i+1];
    }
    
/*    for(i=0;i<=2*o;i++)
    {
       cout<<b[i] <<" ";
    }
 */     
   while(q--)
   {
   	 cin>>l>>r;
   	 cout<<(query(l,r-2,1,o,1)?"YES\n":"NO\n");
   }

   for(i=0;i<=4*o+1;i++)
   	 b[i]=0;
}
return 0;

}

I changed all cout , cin to printf and scanf. Defined all the arrays to be global. AND Got AC.

I really cannot figure out anything wrong with my code. Can anyone please help me out here?
My approach->

  1. Made a preprocess array containing if there’s a rich string of length 3 at index i
  2. In the queries
    a) check if length (l-r+1) < 3 → return false
    b) check if length >= 3 && length < 6 → check if any substring of this is rich by traversing precomputed array
    c) else, divide the range into 2 parts, check if there’s a rich string at mid pos, else recursively check in left and right parts
    However this approach is giving WA.
    Here’s my code →
    CodeChef: Practical coding for everyone

You can also do that. printf() and scanf() are faster than cout and cin. The reason the told you to add those two is because of this reason. You can google what those lines do.

Sir,
My Code is working in 0seconds on ideone.com AND IT IS DOING O(T*(Q+N)) Operations since I am precomputing and deriving the result for a query in O(1) time BUT I AM NOT GETTING WHAT IS THE SOURCE OF TLE IN THIS CODE whenever I submit it shows TLE there is only a minor mistake please help me identify that…

THIS IS MY Code Link
http://ideone.com/xJSVmz

DONE GOT MY MISTAKE… IT WAS that I was initialising withhin the loop

https://www.codechef.com/viewsolution/26037923

Can anyone tell me why I am getting a TLE ? The code is pretty much similar to the code given in the editorial

This problem can be easily solved in O(N+Q) using the following algorithm…
Let dp[i] denote the number of sub strings upto ‘i’ of length 3 that s[i],s[i-1],s[i-2] form a good substring i.e.
dp[i] = 1 + dp[i-1] , if s[i]==s[i-1] || s[i-1]==s[i-2] || s[i]==s[i-2]
dp[i] = dp[i-1] otherwise
Base case: dp[0] = dp[1] = 0
For each query just check if (r-l+1)>=3 && dp[r]-dp[l+1]>=1 , l+1 because from l+2 we have the information whether l,l+1,l+2 form a good substring.

1 Like

pls provide the link to your solution

https://www.codechef.com/viewsolution/26016624

https://www.codechef.com/viewsolution/26045052

please help me i am very close to the solution and have handled all the cases which i can think off.
it gives wrong answer after 0.14 seconds.

Thanks!

you can not create a 2d matrix for string.length=pow(10,5) .

1 Like

Ajay, how your rating got dropped by 433 in august 2018?