MKGPLNKS - Editorial

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;
}

Solution: 54336175 | CodeChef
Why is this WA ?

Please Try
5
BWBWB
This example the answer should be 2 but your code is generating answer as 3

Thanks. Got it.

https://www.codechef.com/viewsolution/57414308
Why my solution is wrong help!!!