CKZONE - EDITORIAL

PROBLEM LINK:

Practice
Contest

Author: Pranjul Pal
Tester: Khushi Agarwal
Editorialist: Pranjul Pal

DIFFICULTY:

SIMPLE

PREREQUISITES:

Optimization, Brute Force

PROBLEM:

Find the number of valid triplets in the string built up of characters R, G, and O, of length N.
Valid triplets (i,j,k) (1 \le i \lt j \lt k \le N):

  • S_i \ne S_j, S_i \ne S_k, S_j \ne S_k.
  • j - i \ne k - j

QUICK EXPLANATION:

Remove invalid distinct-characters triplets from total numbers of invalid distinct-characters triplets.

EXPLANATION:

Let total number of R in string = r
Let total number of G in string = g
Let total number of O in string = o
There are two validations given in the problem statement.
Total number of triplets following first validation = r \times g \times o.
But this number also contains equidistant distinct characters.
To remove these types of triplets, a nested loop will work.
Consider a distance x and remove the triplets (i,j,k) such that (1 \le i \lt j \lt k \le N) and (j - i = k - j) from your answer which have distinct characters.

SOLUTION:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ln "\n"
#define pb push_back
#define pll pair<ll,ll>
#define ppll pair<ll,pll>
#define vll vector<ll>
#define vpll vector<pll>
#define vvll vector<vector<ll>>
#define sll stack<ll>
#define qll queue<ll>
#define mp make_pair
#define f first
#define s second
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define Test ll t;cin>>t; while(t--)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define init(x,n,v) for(ll i=0;i<=n;i++) x[i]=v;
#define all(x) x.begin(),x.end()
#define pi 3.14159265358979323846
ll MOD = 1e9+7 , MAX = 1e18;
int main() 
{
	fast_io;
	ll n,i,ans=0,r=0,g=0,o=0,j;
	string s;
	cin>>n>>s;
	for(auto i: s) 
	{
	    if(i=='R') r++;
	    if(i=='G') g++;
	    if(i=='O') o++;
	}
	ans=r*g*o;
	for(i=0;i<n-2;i++)
	{
	    for(j=1;i+2*j<n;j++)
	    {
	        if(s[i]!=s[i+j] && s[i]!=s[i+2*j] && s[i+j]!=s[i+2*j]) ans--;
	    }
	}
	cout<<ans;
	return 0;
}    
4 Likes