Contest Div1 : Here
Contest Div2 : Here
Contest Div3 : Here
Setter : Ronels Macwan
Tester : Manan Grover , Samarth Gupta, Harsh Rajani
DIFFICULTY
Cake Walk
Pre Requisites
None
Quick Explanation :
If all planks are of the same color, then just output 0.
Otherwise, count the number of continuous groups of color B and W.
Paint the plank whose color has the minimum groups.
Explanation :
Let’s make continuous groups of same color, because when we paint a plank, all
neighboring planks of same color are also colored. Let’s call them grps_b , and
grps_w, denoting the number of groups of color black and white respectively.Then
the answer is min(grps_b,grps_w).
The proof is as follows:
A group can have at most 2 neighbouring groups (they will be of same color). When
we color a plank of a group to the color of it’s neighbor, then it will merge with them
and they will form a single group after that. If we repeat this process , we will
eventually end up with all planks colored the same. If we start with a Black plank , it
will take grps_b moves, and grps_w moves if we start with a white plank.Hence the
ans is min(grps_b,grps_w) moves.
Time Complexity
O(N)
Solutions
Setter’s Code:
#include <bits/stdc++.h> using namespace std; void solve(){ int grps_w=0,grps_b=0; int n,i; string s; cin >> n >> s; for(i=0;i<n;i++){ assert(s[i]=='B' || s[i]=='W'); int j=i+1; if(s[i]=='W'){ grps_w++; while(j<n && s[j]==s[i]){ j++; } } else { grps_b++; while(j<n && s[j]==s[i]){ j++; } } i=j-1; } cout << min(grps_b,grps_w) << "\n"; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //A soln #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); freopen("error.txt","w",stderr); #endif int tests; cin >> tests; while(tests--){ solve(); } }
Tester’s Code:
#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; #define asc(i,a,n) for(I i=a;i<n;i++) #define dsc(i,a,n) for(I i=n-1;i>=a;i--) #define forw(it,x) for(A it=(x).begin();it!=(x).end();it++) #define bacw(it,x) for(A it=(x).rbegin();it!=(x).rend();it++) #define pb push_back #define mp make_pair #define fi first #define se second #define lb(x) lower_bound(x) #define ub(x) upper_bound(x) #define fbo(x) find_by_order(x) #define ook(x) order_of_key(x) #define all(x) (x).begin(),(x).end() #define sz(x) (I)((x).size()) #define clr(x) (x).clear() #define U unsigned #define I long long int #define S string #define C char #define D long double #define A auto #define B bool #define CM(x) complex<x> #define V(x) vector<x> #define P(x,y) pair<x,y> #define OS(x) set<x> #define US(x) unordered_set<x> #define OMS(x) multiset<x> #define UMS(x) unordered_multiset<x> #define OM(x,y) map<x,y> #define UM(x,y) unordered_map<x,y> #define OMM(x,y) multimap<x,y> #define UMM(x,y) unordered_multimap<x,y> #define BS(x) bitset<x> #define L(x) list<x> #define Q(x) queue<x> #define PBS(x) tree<x,null_type,less<I>,rb_tree_tag,tree_order_statistics_node_update> #define PBM(x,y) tree<x,y,less<I>,rb_tree_tag,tree_order_statistics_node_update> #define pi (D)acos(-1) #define md 1000000007 #define rnd randGen(rng) long long readInt(long long l, long long r, char endd) { long long x=0; int cnt=0; int fi=-1; bool is_neg=false; while(true) { char g=getchar(); if(g=='-') { assert(fi==-1); is_neg=true; continue; } if('0'<=g&&g<='9') { x*=10; x+=g-'0'; if(cnt==0) { fi=g-'0'; } cnt++; assert(fi!=0 || cnt==1); assert(fi!=0 || is_neg==false); assert(!(cnt>19 || ( cnt==19 && fi>1) )); } else if(g==endd) { if(is_neg) { x=-x; } assert(l<=x&&x<=r); return x; } else { assert(false); } } } string readString(int l, int r, char endd) { string ret=""; int cnt=0; while(true) { char g=getchar(); assert(g!=-1); if(g==endd) { break; } cnt++; ret+=g; } assert(l<=cnt&&cnt<=r); return ret; } int main(){ mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<I> randGen; ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif I t; t=readInt(1,100000,'\n'); I nn=0; while(t--){ I n; n=readInt(1,100000,'\n'); nn+=n; S s; s=readString(n,n,'\n'); asc(i,0,n){ assert(s[i]=='W' || s[i]=='B'); } I x=0,y=0; asc(i,0,n-1){ if(s[i]=='W' && s[i+1]=='B'){ x++; } if(s[i]=='B' && s[i+1]=='W'){ y++; } } cout<<max(x,y)<<"\n"; } assert(nn<=100000); return 0; }