RGB String#12320

RGB String (Editorial)

Problem Author:	Andriy Kholod (Connect)
Prepared by:	Andriy Kholod (Connect)
Analysis:	Andriy Kholod (Connect)

Solution

Consider a segment of length $6$ . Let's place the element $R$ in the first position, $G$ in the second, and $B$ in the third. Then we consider the elements that are already in the triplet that ends at position $4$ , where position $2$ has $G$ and position $3$ has $B$ . Thus, the only element we can place in position $4$ is $R$ . We will arrange the elements in positions $5$ and $6$ using the same principle. The condition of beauty will also be maintained in the triplets that start at positions $5$ and $6$ .

Then, by the same principle, we can prove that a solution does not exist for all $n$ that are not divisible by $3$ .

Thus, the solution to the problem will be to try all possible arrangements of the elements $R$ , $G$ , and $B$ without repetitions and choose the most advantageous option.

The asymptotic complexity of the solution is $O (n)$ .

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl '\n'
#define pb push_back

const ll clasik = 2e5+17;
const ll INF = 1e17;
ll w[clasik] , pref[clasik] , poslid[clasik];

void solve() {

    ll n;

    cin>>n;

    string line;

    cin>>line;

    if (n%3 != 0) {
        cout<<-1<<endl;
        return;
    }

    ll res = INF;

    //R G B


    ll curr = 0;

    for (int i = 0 ; i < n ; i+=3) {
        curr += (line[i]!='R');
        curr += (line[i+1]!='G');
        curr += (line[i+2]!='B');
    }

    res = min(res , curr);

    // R B G

    curr = 0;

    for (int i = 0 ; i < n ; i+=3) {
        curr += (line[i]!='R');
        curr += (line[i+1]!='B');
        curr += (line[i+2]!='G');
    }

    res = min(res , curr);

    // B R G

    curr = 0;

    for (int i = 0 ; i < n ; i+=3) {
        curr += (line[i]!='B');
        curr += (line[i+1]!='R');
        curr += (line[i+2]!='G');
    }

    res = min(res , curr);

    // B G R

    curr = 0;

    for (int i = 0 ; i < n ; i+=3) {
        curr += (line[i]!='B');
        curr += (line[i+1]!='G');
        curr += (line[i+2]!='R');
    }

    res = min(res , curr);

    // G R B

    curr = 0;

    for (int i = 0 ; i < n ; i+=3) {
        curr += (line[i]!='G');
        curr += (line[i+1]!='R');
        curr += (line[i+2]!='B');
    }

    res = min(res , curr);

    // G B R

    curr = 0;

    for (int i = 0 ; i < n ; i+=3) {
        curr += (line[i]!='G');
        curr += (line[i+1]!='B');
        curr += (line[i+2]!='R');
    }

    res = min(res , curr);

    cout<<res<<endl;

}  

signed main() {
    speed;
    int test;
    test = 1;
    //cin>>test;
    while (test--) solve();
    return 0;
}

C++