RICHSTR - EDITORIAL

Here is the Python Solution

plagiarism ////////////////

433 thats a big hit!

definitely worth it .

@taran_1407 where’s the seg tree approach ?

Your approach is correct but you have made an implementation mistake if the query is towards the end.
Eg for case
1
5 1
aaaaa
3 5
Your code gives NO but answer is YES.

yes i realised my mistake, i used upperbound on L rather than L-1, i corrected it. thanks for the reply anyway

This is precizely the reason i mentioned segment tree instead of prefix sums, but seeing the comments, i should have mentioned that one too.

1 Like

I think there’s error indexing. You made segtree indices 0-based, but didnt adjust queries.
Try decrementing both l and r by 1.

That’s all i could find now

2 Likes

We use segtree to find the OR of a range. At each internal node, we take the OR of children. For each query, we split query segment into logN parts, and return OR of all parts. This is a standard application of segment tree.

1 Like

I am getting WA, pls help, here is my code : https://www.codechef.com/viewsolution/26067889

I got my mistake, got AC…

I too used the same approach but got WA

can someone please look into my code and tell me why i am getting runtime error.
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t–){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long int n,q,i,j,l,r;
cin>>n>>q;
long long int v[n]={0},b[n]={0};
string str;
cin>>str;
if(n<3){
while(q–){
cin>>l>>r;
cout<<“NO”<<endl;
}
continue;
}
for(i=0;i<n-2;i++){
j=i+1;
if(str[j]==str[i]||str[j+1]==str[i]||str[j]==str[j+1]){
v[i]=1;
}
else
v[i]=0;
if(i>0)
b[i]=b[i-1]+v[i];
else
b[i]=v[i];
}
while(q–){
cin>>l>>r;
l–;
r–;
if((r-l+1)<3){
cout<<“NO”<<endl;
continue;
}
if((l-1)>=0 && (b[r-2]-b[l-1])>0){
cout<<“YES”<<endl;
}
else if(l==0 && ((b[r-2]-b[l])>0 || b [0]==1)){
cout<<“YES”<<endl;
}
else
cout<<“NO”<<endl;
}
}
return 0;
}

(If anyone is interested :smiley: )
Solution using BIT: CodeChef: Practical coding for everyone

No,its AC. Just take care about the l and l+1 elements carefully , you will get it try on copy

I still don’t understand how are range min queries or segment trees of any use here? The Setter’s solution make sense. Can you give some idea how can we solve the problem using segment trees?

1 Like