Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerEarth Grids Everywhere problem solution

YASH PAL, 31 July 2024
In this HackerEarth Grids Everywhere problem solution A n x m grid consists of ‘n’ rows and ‘m’ columns. You are given ‘n’ elements, where each ni denotes the sum of elements of the ith row of the grid. You are also given ‘m’ elements, where each mi denotes the sum of elements of the ith column of the grid. You need to construct the grid by filling the desired cells with values in the range [1, 5] inclusive such that when elements arranged row-wise (a11, a12, a21, a22) represent the lexicographically shortest solution of the grid. Here aij represents the element at ith row and jth column.
HackerEarth Grids Everywhere problem solution

HackerEarth Grids Everywhere problem solution.

#include <iostream>
#include <cstring>
#include <cmath>
#include <climits>
using namespace std;
#define ND 250
#define ED 23456
int n,m,eg_no,st,en;
int to[ED],last[ND],nx[ED],cap[ED],hlf[ND],ds[ND],Q[ND];
void init()
{
eg_no=0;
memset(last,-1,sizeof(last));
memset(nx,-1,sizeof(nx));
}
void add_edge(int u,int v,int cp,int r_cp)
{
to[eg_no]=v;cap[eg_no]=cp;nx[eg_no]=last[u];last[u]=eg_no++;
to[eg_no]=u;cap[eg_no]=r_cp;nx[eg_no]=last[v];last[v]=eg_no++;
}
bool bfs()
{
memset(ds,-1,sizeof(ds));
ds[st]=0;int p=1,q=0;Q[0]=st;
while(q<p)
{
int u=Q[q];
for(int i=last[u];i>=0;i=nx[i])
{
int v=to[i];
if(cap[i]>0 && ds[v]==-1)
{
ds[v]=ds[u]+1;
Q[p++]=v;
}
}
q++;
}
return (ds[en]!=-1);
}
int dfs(int in,int cp)
{
if(in==en) return cp;
for(int &i=hlf[in];i>=0;i=nx[i])
{
if(cap[i]>0 && ds[in]+1==ds[to[i]])
{
int tmp=dfs(to[i],min(cp,cap[i]));
if(tmp>0)
{
cap[i]-=tmp;
cap[i^1]+=tmp;
return tmp;
}
}
}
return 0;
}
int dinitz()
{
int res=0;
while(bfs())
{
for(int i=0;i<=en;i++) hlf[i]=last[i];
while(1)
{
int ans=dfs(st,INT_MAX);
res+=ans;
if(ans<=0) break;
}
}
return res;
}
int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
int tt;
cin>>tt;
for(int ii=1;ii<=tt;ii++)
{
init();
int sm=0;
cin>>n>>m;
int A[n],B[m],x[n],y[m],p[n][m];
for(int i=0;i<n;i++)
{
cin>>A[i];
A[i]-=m;
sm+=A[i];
}
for(int i=0;i<m;i++)
{
cin>>B[i];
B[i]-=n;
}
st=n+m,en=n+m+1;
for(int i=0;i<n;i++)
{
x[i]=eg_no;
add_edge(st,i,A[i],0);
}
for(int i=0;i<m;i++)
{
y[i]=eg_no;
add_edge(n+i,en,B[i],0);
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
p[i][j]=eg_no;
add_edge(i,n+j,4,0);
}
}
int tmp=dinitz();
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
int in=p[i][j];
int mv=4-cap[in];
cap[in]=0,cap[in+1]=0;
if(mv>0)
{
cap[x[i]]+=mv,cap[y[j]]+=mv;
int tm=dinitz();
int left=mv-tm;
cap[x[i]]-=left,cap[y[j]]-=left;
cout<<1+left<<" ";
}
else cout<<"1 ";
}
cout<<"n";
}
}
return 0;
}

Second solution

#include <cstdio>
#include <cmath>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define S(x) scanf("%d",&x)
#define P(x) printf("%dn",x)

typedef long long int LL;

int R[55], C[55];
int ans[555][555];
vector<int > g[155];

const int INF = 100000000;

int dist[2505];
int ptr[2505];
int source = -1, sink = -1;

struct edge {
int a,b,cap,flow;
};
vector<edge > e;

void addEdge(int a, int b, int c, int flag) {

edge e1 = {a,b,c,0};
if(flag) g[a].push_back((int)e.size());
e.push_back(e1);

edge e2 = {b,a,0,0};
if(flag) g[b].push_back((int)e.size());
e.push_back(e2);

}

bool bfs() {

memset(dist, -1, sizeof(dist));
dist[source] = 0;
queue<int > q;
q.push(source);

while(!q.empty() && dist[sink] == -1) {
int u = q.front();
q.pop();
rep(i,0,g[u].size()) {
int id = g[u][i];
int to = e[id].b;
if(dist[to] != -1 || e[id].flow >= e[id].cap) continue;
q.push(to);
dist[to] = dist[u] + 1;
}
}

// P(dist[sink]);
return dist[sink] != -1;

}

int dfs(int u, int flow) {

if(u == sink) return flow;
if(!flow) return 0;

for(; ptr[u] < g[u].size(); ptr[u]++) {
int id = g[u][ptr[u]];
int to = e[id].b;

if(dist[to] != dist[u]+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;
while(bfs()) {

memset(ptr, 0, sizeof(ptr));

int pushed;
while((pushed = dfs(source, INF))) {
flow += pushed;
}
// break;

}

return flow;
}


int main() {
int t;
S(t);
while(t--) {

int n,m;
scanf("%d%d",&n,&m);
assert(n > 0 && n <= 50);
assert(m > 0 && m <= 50);

e.clear();
rep(i,0,105) g[i].clear();
source = 0;
sink = n+m+1;
rep(i,1,n+1) {
S(R[i]);
R[i] -= m;
assert(R[i] >= 0 && R[i] <= 4*m);
addEdge(source, i, R[i], 1);
}
rep(i,1,m+1) {
S(C[i]);
C[i] -= n;
assert(C[i] >= 0 && C[i] <= 4*n);
addEdge(i+n, sink, C[i], 1);
}

int sz = e.size();

for(int i = n; i; i--) {
for(int j = m; j; j--) {
addEdge(i, j+n, 4, 1);
}
}

int f = dinic();

rep(i,0,e.size()) if(e[i].a <= n && e[i].b-n >= 0) {
ans[e[i].a][e[i].b-n] = e[i].flow;
}

rep(a,1,n+1) rep(b,1,m+1) {
e.clear();
rep(i,1,n+1) {
addEdge(source, i, R[i], 0);
}
rep(i,1,m+1) {
addEdge(i+n, sink, C[i], 0);
}
for(int i = n; i; i--) {
for(int j = m; j; j--) {
int val;
if(a == i && b == j) val = 0;
else if(i < a || (i == a && j < b)) val = ans[i][j];
else val = 4;
addEdge(i, j+n, val, 0);
}
}
int x = dinic();
// P(x);
ans[a][b] = f - x;
}

rep(i,1,n+1) {
int sm = 0;
rep(j,1,m+1) {
assert(ans[i][j] >= 0 && ans[i][j] <= 4);
sm += ans[i][j];
}
assert(sm == R[i]);
}

rep(i,1,m+1) {
int sm = 0;
rep(j,1,n+1) {
sm += ans[j][i];
}
assert(sm == C[i]);
}

rep(i,1,n+1) {
rep(j,1,m+1) {
printf("%d",ans[i][j]+1);
if(j < m) printf(" ");
}
printf("n");
}
}
return 0;
}
coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes