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


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