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.
#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("%d\n",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;
}
0 Comments