Help in CodeKombat Wild Roundproblem

problem link

I couldn’t think of any other approach other than bruteforce.
So I just want a hint on how to approach this problem.I have seen other’s accepted solutions but couldn’t understand anything.So I’ve come here for help.

1 Like

For each index precompute the index of next different number both to left and right of that index and then for any query l,r we can check that if a[l]==a[r] and next[l] =previous[r] then its yes else no. Think of edge cases and tell me if there is anything which is not clear.

CODE
#include<bits/stdc++.h>
using namespace std ;
void solve(){
  int n,q ;cin >>n >> q ;
  vector<int>a(n),nx(n),pr(n);
  for(int &x:a) 
    cin >> x; 
  int ls =n-1 ;nx[ls]=-1 ;
  for(int i=n-2;~i;--i){
    if(a[i]^a[i+1])
      nx[i]=i+1,ls=i ;
    else
      nx[i]=nx[ls] ;
  }
  ls=0,pr[ls]=-1 ;
  for(int i=1;i<n;i++){
    if(a[i-1]^a[i])
      pr[i]=i-1,ls=i ;
    else
      pr[i]=pr[ls] ;
  }
  while(q--){
    int l,r ;cin >> l >> r ;
    --l;--r ;
    if(a[l]==a[r])
      cout << (nx[l]==pr[r]?"YES":"NO") << '\n';
    else
      cout << ((l==pr[r] || nx[l]==r)?"YES":"NO") <<'\n';
  }
}
signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t ;
  cin >> t ;
  while(t--)
    solve() ;
}

PS: What’s up with this codechef discuss formatting lately someone please fix it.

Ill try. Thanks

1 Like

Can be also solved using binary search

nice bro i didn’t think thought of binary search thanks for this…
i solved it using pbds…