HackerEarth Shil and Greedy approach problem solution

In this HackerEarth Shil and Greedy approach problem solution Shil is very bad at greedy algorithms. So he decided to practice a lot of greedy problems. He came across a very good problem.Problem is as follows:

Given a linear strip of length N. Strip consists of N cells painted in either BLACK or WHITE color. At each move you can do following process:

Take any 2 or 3 contiguous cells.
Invert their colors (i.e replace BLACK cells with WHITE cells and WHITE cells with BLACK cells).

You are required to answer minimum number of moves in which you can change all the cells into same color( either WHITE or BLACK).

HackerEarth Shil and Greedy approach problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll     int
#define INF 10000
#define mp make_pair
#define f first
#define pi pair<ll,ll>
#define pb emplace_back
#define s second
vector<ll>g[100011];
bool vis[10000011];
int main(){
ll n;
cin>>n;
string s;
cin>>s;
ll start=0;
for(int i=0;i<s.length();i++){
    if(s[i]=='B'){
        start^=(1LL<<i);
    }
}
queue<pi>q;

q.push(mp(start,0));

ll stop1=0;
ll stop2=(1LL<<n)-1;
pi r;
while(q.size()){
    r=q.front();
    q.pop();
    if(r.f==stop1 or r.f==stop2){
        cout<<r.s;
     //   cout<<q.size();
        return 0;
    }
    if(vis[r.f]) continue;
    vis[r.f]=1;
    ll curmask;
    ll mask=r.f;
    for(int j=0;j<n-1;j++){
        curmask=(mask ^ (1LL<<j) ^ (1LL<<(j+1)));
       if(!vis[curmask]) q.push(mp(curmask,r.s+1));
    }
    for(int j=0;j<n-2;j++){
           curmask=(mask ^ (1LL<<j) ^ (1LL<<(j+1)) ^(1LL<<(j+2)));
       if(!vis[curmask]) q.push(mp(curmask,r.s+1));
    }

}
}

Second solution

#include<bits/stdc++.h>
#define assn(n,a,b) assert(n<=b && n>=a)
using namespace std;
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define F first
#define S second
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,b) for(i=0;i<b;i++)
#define rep1(i,b) for(i=1;i<=b;i++)
#define pdn(n) printf("%dn",n)
#define sl(n) scanf("%lld",&n)
#define sd(n) scanf("%d",&n)
#define pn printf("n")
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
#define MOD 1000000007
LL mpow(LL a, LL n) 
{LL ret=1;LL b=a;while(n) {if(n&1) 
    ret=(ret*b)%MOD;b=(b*b)%MOD;n>>=1;}
return (LL)ret;}
int dist[(1<<20)+10],n,ans=MOD;
void bfs(int cur){
    queue <int> myq;
    myq.push(cur);
    dist[cur]=1;
    while(not myq.empty()){
        int p=myq.front();
        if(p==0 or p==(1<<n)-1)ans=min(ans,dist[p]);
        myq.pop();
        for(int i=0; i<=n-2; i++){
            int nn=p^(1<<i)^(1<<(i+1));
            if(dist[nn]==0)dist[nn]=dist[p]+1,myq.push(nn);
            if(i>n-3)continue;
            nn=p^(1<<i)^(1<<(i+1))^(1<<(i+2));
            if(dist[nn]==0)dist[nn]=dist[p]+1,myq.push(nn);
        }
    }
}
int main()
{
    int cur=0;
    sd(n);
    string s;
    cin >> s;
    for(int i=0; i<n; i++)
        if(s[i]=='B')cur+=(1<<i);
    bfs(cur);
    cout << ans-1 << endl;
    return 0;
}

coding problems solutions