PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author:
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
There’s a wall with N segments, each of which is painted either red, blue, or green.
The wall is said to be white if for each consecutive set of segments whose length is divisible by 3, the number of red, blue, and green painted-segments is equal.
Find the minimum number of changes needed to make the wall white.
EXPLANATION:
First, note that in a white wall, certainly among any three consecutive segments (i.e. considering length exactly equal to 3), each of the colors red, blue, and green must appear exactly once.
Let’s see what that tells us about S.
Looking at the substring S[1, 3], the first three colors S_1, S_2, S_3 must be pairwise distinct from.
Looking at substring S[2, 4], the colors S_2, S_3, S_4 must be pairwise distinct. However, there are only three colors; so the only possible way this can happen is if S_1 = S_4.
Similarly, looking at S[3, 5] we see that S_2 = S_5 must hold, then S_3 = S_6, and so on.
In general, for any i \gt 3, S_i = S_{i-3} must hold for the wall to be white.
In other words, the string will just look like the first three characters repeated over and over again, i.e. something like
It’s not hard to see that this condition is not just necessary, it’s also sufficient - i.e. if S is of this form, all substrings whose length is a multiple of 3, will have an equal number of each color.
This is easy to prove: any such substring can be broken up into blocks of length three; and since we know each such block has one of each color, the overall substring has an equal number of each color too.
So, we only need to find the minimum number of moves needed to turn S into this form.
Since there are three colors, there are 6 possible ways to arrange them to be the first three characters:
Try each one of them, and compute the minimum number of changes needed to turn S into the pattern repeated.
The answer is the minimum across all 6 cases.
To make implementation simple, you can use inbuilt library functions that allow for going through all permutations: for example next_permutation
in C++ and itertools.permutations
in Python.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
vector<string> comb = {"RGB", "RBG", "BGR", "BRG", "GBR", "GRB"};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t; cin >> t;
while (t--){
int n; cin >> n;
string s; cin >> s;
int ans = n;
for(int c=0; c<6; c++){
int res = 0;
for(int i=0; i<n; i++){
if (s[i] != comb[c][i%3]) res++;
}
ans = min(res, ans);
}
cout << ans << "\n";
}
}
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
void solve(int test_case){
ll n; cin >> n;
string s; cin >> s;
string p = "RGB";
sort(all(p));
ll ans = inf2;
do{
ll cost = 0;
rep(i,n){
cost += s[i]!=p[i%3];
}
amin(ans,cost);
} while(next_permutation(all(p)));
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
s = input()
import itertools
ans = n
for pattern in itertools.permutations('BGR'):
req = 0
for i in range(n):
req += s[i] != pattern[i%3]
ans = min(ans, req)
print(ans)