In this

**HackerEarth Pink and Blue problem solution**Xenny was a teacher and he had N students. The N children were sitting in a room. Each child was wearing a white T-shirt, with a unique number from the range 1 to N written on it. T-Shirts of pink and blue color were to be distributed among the students by Xenny. This made the students very happy.Xenny felt that a random distribution of T-Shirts would be very uninteresting. So, he decided to keep an interesting condition:

Every student would get a T-Shirt that is of a different color than his/her friends. That is, if X and Y are friends and X has a Pink T-Shirt, then Y should compulsorily have a Blue T-Shirt, and vice-versa.

Also, Xenny had a belief that Boys should wear blue T-Shirts and Girls should wear pink T-Shirts. If a boy was given a pink T-Shirt or a girl was given a Blue T-Shirt, he called it an inversion.

So, Xenny wanted to distribute T-Shirts in the above-mentioned interesting manner and also wanted to minimize "inversions". Help him solve the task.

Note: There are no disjoint groups of friends in the room. That is, 2 distinct groups with finite number of students do not exist, but exactly 1 group of students exists in the given situation.

## HackerEarth Pink and Blue problem solution.

`#include <iostream>`

#include <vector>

#include <string.h>

#define ll long long

#define pb push_back

using namespace std;

vector<int> g[100007];

char gender[100007];

char color[100007];

int visited[100007];

int vert;

bool ok;

void dfs(int node, char cur_color)

{

if(visited[node]) return;

color[node] = cur_color;

visited[node] = 1;

for(int i=0;i<g[node].size();i++)

{

vert = g[node][i];

if(vert == node) continue;

if(visited[vert])

{

if(cur_color == color[vert])

{

ok=false;

return;

}

}

else

{

char new_color;

if(cur_color == 'P') new_color = 'B';

else if(cur_color == 'B') new_color = 'P';

color[vert] = new_color;

dfs(vert, new_color);

}

}

}

int main()

{

memset(gender,0,sizeof(gender));

memset(color,0,sizeof(color));

memset(visited,0,sizeof(visited));

ios_base::sync_with_stdio(false);

int n,m;

cin>>n>>m;

for(int i=1;i<=n;i++) cin>>gender[i];

int u,v;

for(int i=0;i<m;i++)

{

cin>>u>>v;

g[u].pb(v);

g[v].pb(u);

}

int ans=0;

ok=true;

dfs(1,'P');

if(ok)

{

for(int i=1;i<=n;i++)

{

if(gender[i] == 'B' && color[i] == 'P') ans++;

else if(gender[i] == 'G' && color[i] == 'B') ans++;

}

int tmp=0;

memset(visited,0,sizeof(visited));

memset(color,0,sizeof(color));

dfs(1,'B');

for(int i=1;i<=n;i++)

{

if(gender[i] == 'B' && color[i] == 'P') tmp++;

else if(gender[i] == 'G' && color[i] == 'B') tmp++;

}

cout << "1p = " << ans << ", 1b = " << tmp << "\n";

ans = min(ans,tmp);

cout << ans << "\n";

}

else

{

cout << "Not possible\n";

}

}

## 0 Comments