PROBLEM LINKS :
Contest : Division 1
Contest : Division 2
Setter : Aviroop Pal
Tester : Alipasha Montaseri / Kasra Mazaheri
Editorialist : Anand Jaisingh
DIFFICULTY :
Medium
PREREQUISITES :
Network Flows,Min Cost max flow, graph theory.
PROBLEM :
S snakes can move in a grid of dimension N \cdot M , which consists of empty and blocked cells. In a single second, a snake can either stay on it’s current cell or move to an adjacent cell. There are Z trees that grow on particular cells in the grid, the i^{th} of them exists between moments P_i and Q_i, and gives happiness H_i when eaten by a snake.
In a single minute, only one snake should exist on one cell. We need to find the maximum possible total happiness achievable by the snakes.
Quick Explanation :
Based on the given input, we can build a special network where each edge has a cost and capacity associated with it.
The answer is then the negation of the minimum cost to get maximum flow through this network.
EXPLANATION :
First of all in this problem we need to understand that most greedy approaches are incorrect. Since all snakes can move and eat apples simultaneously, we cannot consider their contribution independently.
The movement of a snake in a particular direction can definitely affect the movement of other snakes and how they contribute. So, we need to device an approach that respects this mutual dependence.
Subtask 1 :
Here , S \le 2 . Looking at the other constraints, we can construct the following dynamic programming :
Let dp[x1][y1][x2][y2][t] be the maximum possible happiness we can achieve if the first snake is at cell (x1,y1) and the second snake is at cell (x2,y2) at time t.
The transitions are then straight forward, just like in dfs, based on the input grid and the relative positioning of the snakes, the future states we can move to are calculated, and we try and move to all of those states, and memoize the maximum among them.
The complexity of such a solution is O((N \cdot M)^2 \cdot T )
Full Score :
At the heart of the given problem statement is an approach based on the Min cost max flow technique. The input data can be modeled as a graph as follows :
We need to create a directed acyclic graph, where snakes move from one cell to another in time. For each unblocked cell (i,j) present in the grid , for each time moment k , \hspace{0.2cm} k=0,1,2,....T create 2 nodes. ( Why we create 2 and not 1 node is explained a little later ) . Let’s call the first of these for a cell (i,j) at time k as in(i,j,k) and the second of these as out(i,j,k) .
Now, edges are added between these nodes as follows, each of them with an exact capacity of 1 (Remember, the edges in a network have a capacity, and may also have a cost attached to them too)
For each cell (i,j) at time k we add an edge between out(i,j,k) and all possible cells (x,y) reachable from (i,j) in a single move to in(x,y,k+1). Also, add an edge between in(i,j,k) and out(i,j,k) for all possible (i,j,k).
Now, we create a dummy source and sink done. We add an edge between the source and all cells nodes in(x,y,0) where (x,y) is the starting position of a snake. Additionally, for all nodes out(i,j,T) we add an edge between them and the sink.
Now, if a snake can stay in a particular cell (x,y) at time k and earn a maximum happiness of z, then we assign a cost of -z to the edge between out(x,y,k) and in(x,y,k+1). All other edges shall have a cost of 0.
A flow of 1 in this graph between 2 adjacent nodes now represents the movement(staying in the same position) of a snake, for the cells these nodes represent respectively ( as we move ahead in time).
The reason for a cell (i,j) at time k we create 2 nodes in(i,j,k) and out(i,j,k) is because consider the following situation :
A snake moves from cell (x+dx,y+dy) at time k to cell (x,y) and another snake remains at cell (x,y) at time k. If we have only 1 node for this cell in the graph, then this would mean one of the snakes crosses a cell (x,y) while another snake is still at the cell. We cannot allow such a situation to occur. A capacity of 1 on the edge between in(i,j,k) and out(i,j,k) ensures that only 1 snake remains on any cell (x,y) at any time k.
Consider the following graph we create for the test case :
1 2 2 1
S.
1 1 0 1 3
1 2 0 1 5
All edges in the graph are assumed to have a capacity of 1. Here, we can get a flow of 1 with a cost of -3 using the Path : Source -> In(0,0,0)->Out(0,0,0)->In(0,0,1)->Out(0,0,1)->Sink or a flow of 1 with a cost of 0 using the path Source->In(0,0,0)->Out(0,0,0)->In(0,1,1)->Out(0,1,1)->Sink
The negation of the min cost flow in this network represents the maximum possible total happiness. So, we choose the path with lower cost, i.e -3, so the maximum possible happiness we can achieve is 3.
Note that since this graph is directed, and we can only move ahead in time, this graph is strictly acyclic. There exist algorithms for finding the min cost flow in a graph consisting of negative edges, but not negative cycles. For example, you can use the bellman form algorithm in such a case. You can read more about the min cost flow technique using the links below :
The Time complexity of such a solution can be calculated as :
The flow increases by at least 1 in each step, so there can be a maximum of S steps. Each step then costs us O( N \cdot M \cdot T \cdot \log(NM)) ( the number of nodes and edges both are of the order (O(N \cdot M \cdot T)), so the overall complexity is O( S \cdot (N \cdot M \cdot \log(NM)))
Your comments are welcome !
COMPLEXITY ANALYSIS :
Time Complexity : O(N \cdot M \cdot T \cdot log(NM) \cdot S)
Space Complexity : O( N \cdot M \cdot T )
SOLUTION LINKS :
Setter
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
// #define int long long
#define pb push_back
#define fi first
#define se second
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()
#define IO ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define sz(x) (int)x.size()
// const int mod = 1e9 + 7;
// const int mod1 = 998244353;
typedef long double f80;
#ifndef LOCAL
#pragma GCC optimize ("O2")
#define endl '\n'
#endif
template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r){
uniform_int_distribution<int> uid(l, r);
return uid(rng);
}
ll pwr(ll a,ll b, ll mod){
a %= mod;
int ans = 1;
while(b){
if(b & 1) ans = (ans * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ans;
}
string to_string(string s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
const int INF = INT_MAX;
struct MinimumCostMaximumFlow {
typedef int Index; typedef int Flow; typedef int Cost;
static const Flow InfCapacity = INF;
struct Edge {
Index to; Index rev;
Flow capacity; Cost cost;
};
vector<vector<Edge> > g;
void init(Index n) { g.assign(n, vector<Edge>()); }
void add(Index i, Index j, Flow capacity = InfCapacity, Cost cost = Cost()) {
// debug(i, j, capacity, cost);
Edge e, f; e.to = j, f.to = i; e.capacity = capacity, f.capacity = 0; e.cost = cost, f.cost = -cost;
g[i].push_back(e); g[j].push_back(f);
g[i].back().rev = (Index)g[j].size() - 1; g[j].back().rev = (Index)g[i].size() - 1;
}
void addB(Index i, Index j, Flow capacity = InfCapacity, Cost cost = Cost()) {
add(i, j, capacity, cost);
add(j, i, capacity, cost);
}
pair<Cost, Flow> minimumCostMaximumFlow(Index s, Index t, Flow f = InfCapacity, bool useSPFA = true) {
int n = g.size();
vector<Cost> dist(n); vector<Index> prev(n); vector<Index> prevEdge(n);
pair<Cost, Flow> total = make_pair(0, 0);
vector<Cost> potential(n);
while(f > 0) {
fill(dist.begin(), dist.end(), INF);
if(useSPFA || total.second == 0) {
deque<Index> q;
q.push_back(s); dist[s] = 0; vector<bool> inqueue(n);
while(!q.empty()) {
Index i = q.front(); q.pop_front(); inqueue[i] = false;
for(Index ei = 0; ei < (Index)g[i].size(); ei ++) {
const Edge &e = g[i][ei]; Index j = e.to; Cost d = dist[i] + e.cost;
if(e.capacity > 0 && d < dist[j]) {
if(!inqueue[j]) {
inqueue[j] = true;
q.push_back(j);
}
dist[j] = d; prev[j] = i; prevEdge[j] = ei;
}
}
}
} else {
vector<bool> vis(n);
priority_queue<pair<Cost, Index> > q;
q.push(make_pair(-0, s)); dist[s] = 0;
while(!q.empty()) {
Index i = q.top().second; q.pop();
if(vis[i]) continue;
vis[i] = true;
for(Index ei = 0; ei < (Index)g[i].size(); ei ++) {
const Edge &e = g[i][ei];
if(e.capacity <= 0) continue;
Index j = e.to; Cost d = dist[i] + e.cost + potential[i] - potential[j];
if(dist[j] > d) {
dist[j] = d; prev[j] = i; prevEdge[j] = ei;
q.push(make_pair(-d, j));
}
}
}
}
if(dist[t] == INF) break;
if(!useSPFA) for(Index i = 0; i < n; i ++) potential[i] += dist[i];
Flow d = f; Cost distt = 0;
for(Index v = t; v != s; ) {
Index u = prev[v]; const Edge &e = g[u][prevEdge[v]];
d = min(d, e.capacity); distt += e.cost; v = u;
}
f -= d; total.first += d * distt; total.second += d;
for(Index v = t; v != s; v = prev[v]) {
Edge &e = g[prev[v]][prevEdge[v]];
e.capacity -= d; g[e.to][e.rev].capacity += d;
}
}
return total;
}
};
const int N = 270;
const int NN = 5005;
int A[N], B[N], X[NN], Y[NN], P[NN], Q[NN], H[NN];
char G[N][N];
int Z[N][N];
bool taken[N][N];
int pts[N][85];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int n, m, k, t, T, unblocked, tot;
int getnode(int u, int t, bool b){
int val = (t * unblocked + u) * 2 + b;
assert(val < tot);
return val;
}
void solve(){
// k -> number of snakes
// t -> number of trees
// T -> Total playing time
cin >> n >> m >> t >> T;
assert(n * m >= 1 && n * m <= 256);
assert(T <= 80);
assert(t >= 0 && t <= 5000);
// Grid information
fr(i, 1, n){
fr(j, 1, m){
cin >> G[i][j];
if(G[i][j] == '.' || G[i][j] == 'S') Z[i][j] = ++unblocked;
if(G[i][j] == 'S') {
k++;
A[k] = i, B[k] = j;
}
}
}
MinimumCostMaximumFlow mcmf;
tot = 2 * unblocked * (T + 1) + 5;
mcmf.init(tot);
int st = 0, en = tot - 1;
assert(k >= 1 && k <= unblocked);
// Snake information
fr(i, 1, k){
assert(A[i] >= 1 && A[i] <= n);
assert(B[i] >= 1 && B[i] <= m);
taken[A[i]][B[i]] = 1;
mcmf.add(st, getnode(Z[A[i]][B[i]], 0, 0), 1, 0);
}
fr(i, 1, unblocked){
mcmf.add(getnode(i, T, 1), en, 1, 0);
fr(j, 0, T){
mcmf.add(getnode(i, j, 0), getnode(i, j, 1), 1, 0);
}
}
// Tree information
fr(i, 1, t){
cin >> X[i] >> Y[i] >> P[i] >> Q[i] >> H[i];
assert(P[i] < Q[i] && P[i] >= 0 && Q[i] <= T);
assert(H[i] >= 0 && H[i] <= 1e6);
assert(X[i] >= 1 && X[i] <= n);
assert(Y[i] >= 1 && Y[i] <= m);
fr(j, P[i], Q[i] - 1){
pts[Z[X[i]][Y[i]]][j] = max(pts[Z[X[i]][Y[i]]][j], H[i]);
}
}
fr(i, 1, n){
fr(j, 1, m){
if(!Z[i][j]) continue;
fr(c, 0, 3){
int x = i + dx[c], y = j + dy[c];
if(x < 1 || x > n) continue;
if(y < 1 || y > m) continue;
if(!Z[x][y]) continue;
fr(k, 0, T - 1){
mcmf.add(getnode(Z[i][j], k, 1), getnode(Z[x][y], k + 1, 0), 1, 0);
}
}
}
}
fr(i, 1, unblocked){
fr(j, 0, T - 1){
mcmf.add(getnode(i, j, 1), getnode(i, j + 1, 0), 1, -pts[i][j]);
}
}
cout << -mcmf.minimumCostMaximumFlow(st, en).fi;
}
signed main(){
IO;
#ifdef LOCAL
freopen("inp.txt","r", stdin);
freopen("out.txt", "w", stdout);
#endif
cout << setprecision(10) << fixed;
int t = 1;
// cin >> t;
fr(tt, 1, t){
solve();
}
return 0;
}
Tester
/*
Take me to church
I'll worship like a dog at the shrine of your lies
I'll tell you my sins and you can sharpen your knife
Offer me that deathless death
Good God, let me give you my life
*/
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
struct Edge {int to, flow, cost;};
template < int MXN , int MXM >
struct MinCostMaxFlow
{
int s, t, P[MXN];
int ts, head[MXN], nxt[MXM], to[MXM], flow[MXM], cost[MXM];
bool M[MXN];
ll D[MXN];
inline void Init()
{
ts = 0;
memset(head, -1, sizeof(head));
memset(nxt, -1, sizeof(nxt));
}
inline void Add(int v, int u, int w, int c)
{
to[ts] = u; flow[ts] = w; cost[ts] = c;
nxt[ts] = head[v]; head[v] = ts ++;
to[ts] = v; flow[ts] = 0; cost[ts] = -c;
nxt[ts] = head[u]; head[u] = ts ++;
}
inline bool SPFA()
{
queue < int > qu;
memset(M, 0, sizeof(M));
memset(P, -1, sizeof(P));
memset(D, 63, sizeof(D));
D[s] = 0; qu.push(s);
while (qu.size())
{
int v = qu.front();
qu.pop(); M[v] = 0;
for (int id = head[v]; ~ id; id = nxt[id])
if (flow[id] && D[to[id]] > D[v] + cost[id])
{
P[to[id]] = id;
D[to[id]] = D[v] + cost[id];
if (!M[to[id]])
qu.push(to[id]), M[to[id]] = 1;
}
}
return (P[t] != -1);
}
inline pair < int , ll > MaxFlow()
{
int Flow = 0;
ll Cost = 0;
while (SPFA())
{
int v = t, _flow = INT_MAX;
while (v != s)
_flow = min(_flow, flow[P[v]]), v = to[P[v]^1];
Flow += _flow; Cost += _flow * D[t]; v = t;
while (v != s)
{
flow[P[v]] -= _flow;
flow[P[v]^1] += _flow;
v = to[P[v]^1];
}
}
return make_pair(Flow, Cost);
}
};
const int N = 313;
int n, m, k, q, t, MX[N * 83];
int gx[] = {-1, 1, 0, 0};
int gy[] = {0, 0, -1, 1};
bool Mark[N][N];
char S[N][N];
inline int Get(int a, int b, int c, int d)
{
return ((a + b * n + c * n * m) * 2 + d);
}
int32_t main()
{
MinCostMaxFlow < N * 83 * 2 , N * 83 * 16 > G;
G.Init(); G.s = N * 83 * 2 - 2; G.t = G.s + 1;
scanf("%d%d%d%d", &n, &m, &q, &t);
assert(1 <= n * m && n * m <= 256);
assert(1 <= q && q <= 5000);
assert(1 <= t && t <= 80);
for (int i = 0; i < n; i ++)
scanf("%s", &S[i]);
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
if (S[i][j] == 'S')
G.Add(G.s, Get(i, j, 0, 0), 1, 0), S[i][j] = '.', k ++;
assert(1 <= k && k <= 32);
for (int i = 0; i < q; i ++)
{
int a, b, l, r, c;
scanf("%d%d%d%d%d", &a, &b, &l, &r, &c);
assert(1 <= a && a <= n);
assert(1 <= b && b <= m);
assert(0 <= l && l < r && r <= t);
assert(0 <= c && c <= (int)(1e9));
a --; b --;
if (S[a][b] == '#')
continue;
for (int j = l; j < r; j ++)
MX[Get(a, b, j, 0) >> 1] = max(MX[Get(a, b, j, 0) >> 1], c);
}
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
{
assert(S[i][j] == '.' || S[i][j] == '#');
if (S[i][j] == '#')
continue;
G.Add(Get(i, j, t, 1), G.t, 1, 0);
for (int h = 0; h <= t; h ++)
G.Add(Get(i, j, h, 0), Get(i, j, h, 1), 1, 0);
for (int h = 0; h < t; h ++)
{
G.Add(Get(i, j, h, 1), Get(i, j, h + 1, 0), 1, -MX[Get(i, j, h, 0) >> 1]);
for (int l = 0; l < 4; l ++)
{
int a = i + gx[l], b = j + gy[l];
if (a < 0 || b < 0 || a >= n || b >= m || S[a][b] == '#')
continue;
G.Add(Get(i, j, h, 1), Get(a, b, h + 1, 0), 1, 0);
}
}
}
return !printf("%lld\n", -G.MaxFlow().second);
}
Editorialist
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
// Anand Jaisingh
#include<bits/stdc++.h>
using namespace std;
typedef complex<double> base;
typedef long double ld;
typedef long long ll;
#define pb push_back
#define pii pair<int,int>
#define pll pair< ll , ll >
#define vi vector<int>
#define vvi vector< vi >
const int maxn=(int)(260);
char mat[maxn][maxn];
vector< pair< int, pii > > inv;
int indexes[260][260][81],cost[260][260][81];
vector< pii > lest;
int ctr;
int xm[5]={1,-1,0,0},ym[5]={0,0,1,-1};
int n,m;
bool check(int i,int j)
{
return (i>=0 && i<n && j>=0 && j<m && mat[i][j]!='#');
}
struct edge
{
int to, flow, cap, cost, rev;
};
struct MinCostMaxFlow
{
int nodes;
vector<int> prio, curflow, prevedge, prevnode, q, pot;
vector<bool> inqueue;
vector<vector<edge> > graph;
MinCostMaxFlow() {}
MinCostMaxFlow(int n): nodes(n), prio(n, 0), curflow(n, 0),
prevedge(n, 0), prevnode(n, 0), q(n, 0), pot(n, 0), inqueue(n, 0), graph(n) {}
void addEdge(int source, int to, int capacity, int cost)
{
edge a = {to, 0, capacity, cost, (int)graph[to].size()};
edge b = {source, 0, 0, -cost, (int)graph[source].size()};
graph[source].push_back(a);
graph[to].push_back(b);
}
void bellman_ford(int source, vector<int> &dist)
{
fill(dist.begin(), dist.end(), INT_MAX);
dist[source] = 0;
int qt=0;
q[qt++] = source;
for(int qh=0;(qh-qt)%nodes!=0;qh++)
{
int u = q[qh%nodes];
inqueue[u] = false;
for(auto &e : graph[u])
{
if(e.flow >= e.cap)
continue;
int v = e.to;
int newDist = dist[u] + e.cost;
if(dist[v] > newDist)
{
dist[v] = newDist;
if(!inqueue[v])
{
inqueue[v] = true;
q[qt++ % nodes] = v;
}
}
}
}
}
pair<int, int> minCostFlow(int source, int dest, int maxflow)
{
bellman_ford(source, pot);
int flow = 0;
int flow_cost = 0;
while(flow < maxflow)
{
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
q.push({0, source});
fill(prio.begin(), prio.end(), INT_MAX);
prio[source] = 0;
curflow[source] = INT_MAX;
while(!q.empty())
{
int d = q.top().first;
int u = q.top().second;
q.pop();
if(d != prio[u])
continue;
for(int i=0;i<graph[u].size();i++)
{
edge &e=graph[u][i];
int v = e.to;
if(e.flow >= e.cap)
continue;
int newPrio = prio[u] + e.cost + pot[u] - pot[v];
if(prio[v] > newPrio)
{
prio[v] = newPrio;
q.push({newPrio, v});
prevnode[v] = u;
prevedge[v] = i;
curflow[v] = min(curflow[u], e.cap - e.flow);
}
}
}
if(prio[dest] == INT_MAX)
break;
for(int i=0;i<nodes;i++)
pot[i]+=prio[i];
int df = min(curflow[dest], maxflow - flow);
flow += df;
for(int v=dest;v!=source;v=prevnode[v])
{
edge &e = graph[prevnode[v]][prevedge[v]];
e.flow += df;
graph[v][e.rev].flow -= df;
flow_cost += df * e.cost;
}
}
return {flow, flow_cost};
}
};
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
int z,t;
cin>>n>>m>>z>>t;
for(int i=0;i<n;i++)
{
string s;cin>>s;
for(int j=0;j<m;j++)
{
mat[i][j]=s[j];
if(mat[i][j]=='S')
{
lest.pb({i,j});
}
}
}
ctr=0;inv.pb({-1,{-1,-1}});
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
vector<int> curr;
if(mat[i][j]!='#')
{
for(int k=0;k<=t;k++)
{
ctr+=2;
indexes[i][j][k]=ctr;
inv.pb({i,{j,k}});
}
}
}
}
int last=++ctr;ctr++;
while(z>0)
{
int xi,yi,pi,qi,hi;
cin>>xi>>yi>>pi>>qi>>hi;
xi--;yi--;
for(int time=pi;time<qi;time++)
{
cost[xi][yi][time]=min(cost[xi][yi][time],-hi);
}
z--;
}
MinCostMaxFlow mcmf(ctr);
for(int x=0;x<n;x++)
{
for(int y=0;y<m;y++)
{
if(mat[x][y]!='#')
{
for(int j=0;j<4;j++)
{
if(check(x+xm[j],y+ym[j]))
{
//ccout<<x<<" "<<y<<" "<<(x+xm[j])<<" "<<(y+ym[j])<<endl;
for(int k=0;k<t;k++)
{
int idx1=indexes[x][y][k],idx2=indexes[x+xm[j]][y+ym[j]][k+1]-1;
mcmf.addEdge(idx1,idx2,1,0);
}
}
}
for(int k=0;k<t;k++)
{
int idx1=indexes[x][y][k],idx2=indexes[x][y][k+1]-1;
mcmf.addEdge(idx1,idx2,1,cost[x][y][k]);
}
}
}
}
for(int i=1;i<last;i+=2)
{
mcmf.addEdge(i,i+1,1,0);
}
for(int i=1;i<inv.size();i++)
{
if(inv[i].second.second==t)
{
mcmf.addEdge(2*i,last,1,0);
}
}
for(pii x:lest)
{
int idx=indexes[x.first][x.second][0]-1;
mcmf.addEdge(0,idx,1,0);
}
// cout<<"hello"<<endl;
pll res=mcmf.minCostFlow(0,last,lest.size());
cout<<-(res.second)<<endl;
return 0;
}