In this HackerEarth Beautiful Badges Assignment problem solution Lucy has got the task to create badges for all students of the school. A badge is created by superimposing two squares. The bottom square should be of blue colour and top square should be of yellow colour. The squares must be rotated in such a way that the projection of the badge displays 8 distinguishable vertices.

Please help Lucy find out the maximum number of badges she can make with available n squares.


HackerEarth Beautiful Badges problem solution


HackerEarth Beautiful Badges problem solution.

#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define FF first
#define SS second
#define s(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define sf(n) scanf("%lf",&n)
#define ss(n) scanf("%s",n)
#define sc(n) {char temp[4]; ss(temp); n=temp[0];}
#define LINF (long long)1e18
#define EPS 1e-9
#define maX(a,b) ((a)>(b)?(a):(b))
#define miN(a,b) ((a)<(b)?(a):(b))
#define abS(x) ((x)<0?-(x):(x))

typedef long long ll;
typedef unsigned long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<int,PII> TRI;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<ll> vl;
typedef vector<PII> VII;
typedef vector<TRI> VT;

int N, m;
PII a[100005];
const int MAXN = 2005;
int cnt[MAXN], one_st;


const int INF = 1000000000;


struct edge {
int a, b, cap, flow;
};

int n, s, t, d[MAXN], ptr[MAXN], q[MAXN];
vector<edge> e;
vector<int> g[MAXN];

void add_edge (int a, int b, int cap) {
edge e1 = { a, b, cap, 0 };
edge e2 = { b, a, 0, 0 };
g[a].push_back ((int) e.size());
e.push_back (e1);
g[b].push_back ((int) e.size());
e.push_back (e2);
}

bool bfs() {
int qh=0, qt=0;
q[qt++] = s;
memset (d, -1, n * sizeof d[0]);
d[s] = 0;
while (qh < qt && d[t] == -1) {
int v = q[qh++];
for (size_t i=0; i<g[v].size(); ++i) {
int id = g[v][i],
to = e[id].b;
if (d[to] == -1 && e[id].flow < e[id].cap) {
q[qt++] = to;
d[to] = d[v] + 1;
}
}
}
return d[t] != -1;
}

int dfs (int v, int flow) {
if (!flow) return 0;
if (v == t) return flow;
for (; ptr[v]<(int)g[v].size(); ++ptr[v]) {
int id = g[v][ptr[v]],
to = e[id].b;
if (d[to] != d[v] + 1) continue;
int pushed = dfs (to, min (flow, e[id].cap - e[id].flow));
if (pushed) {
e[id].flow += pushed;
e[id^1].flow -= pushed;
return pushed;
}
}
return 0;
}

int dinic() {
int flow = 0;
for (;;) {
if (!bfs()) break;
memset (ptr, 0, n * sizeof ptr[0]);
while (int pushed = dfs (s, INF))
flow += pushed;
}
return flow;
}

void precompute() {
}
void read() {
s(N);
for (int i = 0; i < N; ++i) {
int c_i, d_i;
s(c_i), s(d_i);
a[i] = make_pair(c_i, d_i);
}
}
void preprocess() {
sort(a, a + N);
int cur = -1;
one_st = -1;
for (int i = 0; i < N; ++i) {
if(i == 0 or (a[i] != a[i - 1])) {
++cur;
cnt[cur] = 1;
}
else cnt[cur]++;
if(one_st == -1 and a[i].FF == 2) one_st = cur;
}
N = unique(a, a + N) - a;
}

void solve() {
n = N + 2;;
s = 0, t = N + 1;
for (int i = 0; i < N; ++i) {
if(i < one_st) add_edge(s, i + 1, cnt[i]);
else add_edge(i + 1, t, cnt[i]);
}
for (int i = 0; i < one_st; ++i) {
int mind = ceil(a[i].SS / sqrt(2.0));
int maxd = floor(a[i].SS * sqrt(2.0));
for (int j = one_st; j < N; ++j) {
assert(a[j].FF != a[i].FF);
if(a[j].SS <= maxd and a[j].SS >= mind)
add_edge(i + 1, j + 1, min(cnt[i], cnt[j]));
}
}
cout << dinic();
}
int main() {
precompute();
read();
preprocess();
solve();
return 0;
}