In this HackerEarth Shubham and Grid problem solution You are given a grid of n rows and m columns consisting of lowercase English letters a, b, c, and d.

We say 4 cells form a "nice-quadruple" if and only if
  1. The letters on these cells form a permutation of the set {a,b,c,d}.
  2. The cell marked b is directly reachable from cell marked a.
  3. The cell marked c is directly reachable from the cell marked b.
  4. The cell marked d is directly reachable from the cell marked c.
A cell (x2,y2) is said to be directly reachable from cell (x1,y1) if and only if (x2,y2) is one of these 4 cells { (x1 -1,y1), (x1+1,y1), (x1,y1-1) and (x1,y1+1)}).

Given the constraint that each cell can be part of at most 1 "nice-quadruple", what's the maximum number of "nice-quadruples" you can select?


HackerEarth Shubham and Grid problem solution


HackerEarth Shubham and Grid problem solution.

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define inf 1000000000000
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define S second
#define F first
#define boost1 ios::sync_with_stdio(false);
#define boost2 cin.tie(0);
#define mem(a,val) memset(a,val,sizeof a)
#define endl "\n"
#define maxn 100001

struct Edge
{
ll from, to, cap, flow, index;
Edge(ll from, ll to, ll cap, ll flow, ll index) :
from(from), to(to), cap(cap), flow(flow), index(index) {}
};

struct PushRelabel
{
ll N;
vector<vector<Edge> > G;
vector<ll> excess;
vector<ll> dist, active, count;
queue<int> Q;

PushRelabel(ll N) : N(N), G(N), excess(N), dist(N), active(N), count(2*N) {}

void AddEdge(ll from, ll to, ll cap) {
G[from].push_back(Edge(from, to, cap, 0, G[to].size()));
if (from == to) G[from].back().index++;
G[to].push_back(Edge(to, from, 0, 0, G[from].size() - 1));
}

void Enqueue(ll v) {
if (!active[v] && excess[v] > 0) { active[v] = true; Q.push(v); }
}

void Push(Edge &e) {
ll amt=min(excess[e.from], e.cap - e.flow);
if (dist[e.from] <= dist[e.to] || amt == 0) return;
e.flow += amt;
G[e.to][e.index].flow -= amt;
excess[e.to] += amt;
excess[e.from] -= amt;
Enqueue(e.to);
}

void Gap(ll k) {
for (ll v = 0; v < N; v++) {
if (dist[v] < k) continue;
count[dist[v]]--;
dist[v] = max(dist[v], N+1);
count[dist[v]]++;
Enqueue(v);
}
}

void Relabel(ll v) {
count[dist[v]]--;
dist[v] = 2*N;
for (ll i = 0; i < G[v].size(); i++)
if (G[v][i].cap - G[v][i].flow > 0)
dist[v] = min(dist[v], dist[G[v][i].to] + 1);
count[dist[v]]++;
Enqueue(v);
}

void Discharge(ll v) {
for (ll i = 0; excess[v] > 0 && i < G[v].size(); i++) Push(G[v][i]);
if (excess[v] > 0) {
if (count[dist[v]] == 1)
Gap(dist[v]);
else
Relabel(v);
}
}

ll GetMaxFlow(ll s, ll t) {
count[0] = N-1;
count[N] = 1;
dist[s] = N;
active[s] = active[t] = true;
for (ll i = 0; i < G[s].size(); i++) {
excess[s] += G[s][i].cap;
Push(G[s][i]);
}

while (!Q.empty()) {
int v = Q.front();
Q.pop();
active[v] = false;
Discharge(v);
}

ll totflow = 0;
for (ll i = 0; i < G[s].size(); i++) totflow += G[s][i].flow;
return totflow;
}
vector<vector<Edge> > build(){
return G;
}
};
int id[25][25],n,m;
char arr[25][25];
int di[]={1,-1,0,0};
int dj[]={0,0,1,-1};

int valid(int x,int y)
{
return (x>=1 && x<=n && y>=1 && y<=m);
}
int main()
{
boost1;boost2;
int i,j,x,y,ctr=0,src,sink,ni,nj,k;
cin>>n>>m;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
cin>>arr[i][j];
}
ctr=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
ctr++;
id[i][j]=ctr;
}
}
PushRelabel network(2+2*n*m);
src=0;
sink=1+2*n*m;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(arr[i][j]=='a')
{
network.AddEdge(src,id[i][j],1);
for(k=0;k<4;k++)
{
ni=i+di[k];
nj=j+dj[k];
if(!valid(ni,nj) || arr[ni][nj]!='b')
continue;
network.AddEdge(id[i][j],id[ni][nj],1);
}
}
else if(arr[i][j]=='b')
{
network.AddEdge(id[i][j],n*m+id[i][j],1);
for(k=0;k<4;k++)
{
ni=i+di[k];
nj=j+dj[k];
if(!valid(ni,nj) || arr[ni][nj]!='c')
continue;
network.AddEdge(n*m+id[i][j],id[ni][nj],1);
}
}
else if(arr[i][j]=='c')
{
network.AddEdge(id[i][j],n*m+id[i][j],1);
for(k=0;k<4;k++)
{
ni=i+di[k];
nj=j+dj[k];
if(!valid(ni,nj) || arr[ni][nj]!='d')
continue;
network.AddEdge(n*m+id[i][j],id[ni][nj],1);
}
}
else
network.AddEdge(id[i][j],sink,1);
}
}
cout<<network.GetMaxFlow(src,sink);
return 0;
}

Second solution

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 20;

const int MAXNODE = MAXN * MAXN * 2 + 2;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int n, m, source, sink;
char a[MAXN][MAXN];
int mark[256], x[4], y[4];

vector<int> vtx, capacity, nextEdge;
int head[MAXNODE];

void addEdge(int a, int b)
{
vtx.push_back(b);
nextEdge.push_back(head[a]);
head[a] = capacity.size();
capacity.push_back(1);

vtx.push_back(a);
nextEdge.push_back(head[b]);
head[b] = capacity.size();
capacity.push_back(0);
}

void generate(int i)
{
if (i == 4) {
addEdge(source, mark['a']);
addEdge(mark['a'] + n * m, mark['b']);
addEdge(mark['b'] + n * m, mark['c']);
addEdge(mark['c'] + n * m, mark['d']);
addEdge(mark['d'] + n * m, sink);
return;
}
for (int j = i - 1; j < i; ++ j) {
for (int k = 0; k < 4; ++ k) {
int tx = x[j] + dx[k], ty = y[j] + dy[k];
if (tx >= 0 && ty >= 0 && tx < n && ty < m &&
a[tx][ty] == 'a' + i) {
mark[a[tx][ty]] = tx * m + ty;
x[i] = tx;
y[i] = ty;
generate(i + 1);
mark[a[tx][ty]] = -1;
}
}
}
}

bool bfs()
{
queue<int> q;
vector<int> pre(sink + 1, -1);
q.push(source);
pre[source] = -2;
while (q.size() && pre[sink] == -1) {
int u = q.front();
q.pop();
for (int p = head[u]; p != -1; p = nextEdge[p]) {
if (capacity[p]) {
int v = vtx[p];
if (pre[v] == -1) {
pre[v] = p;
q.push(v);
}
}
}
}
if (pre[sink] == -1) {
return false;
}
for (int u = sink, p; u != source; u = vtx[p]) {
p = pre[u];
-- capacity[p];
++ capacity[p ^= 1];
}
return true;
}

int main()
{
assert(scanf("%d%d", &n, &m) == 2 && 1 <= n && n <= MAXN && 1 <= m && m <= MAXN);
source = 2 * n * m;
sink = source + 1;
memset(head, -1, sizeof(head));
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < m; ++ j) {
char s[10];
assert(scanf("%s", s) == 1);
assert(strlen(s) == 1);
a[i][j] = s[0];
assert('a' <= a[i][j] && a[i][j] <= 'd');
if (a[i][j] <= 'd') {
addEdge(i * m + j, i * m + j + n * m);
}
}
}
cerr << "I/O: " << capacity.size() << endl;

memset(mark, -1, sizeof(mark));
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < m; ++ j) {
if (a[i][j] == 'a') {
x[0] = i;
y[0] = j;
mark['a'] = i * m + j;
generate(1);
}
}
}
cerr << "Generation done: " << capacity.size() << endl;

int flow = 0;
while (bfs()) {
++ flow;
}
printf("%d\n", flow);

return 0;
}