SNKAPT-Editorial

PROBLEM LINKS :

Contest : Division 1

Contest : Division 2

Practice

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

graph%20(6)

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 :

One Two Three Four

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;
}
3 Likes

Unrelated to this editorial but , @anand20 Can you share the solution sketches of the author for Minimum and Maximum(last problem of Division-1 ) ? (if the editorial is not ready…)

The editorial is ready, it’s in the verification phase before going public

1 Like

The editorial is ready, it’s in the verification phase before being public

1 Like

Maybe this can help : July19 Problem Discussion - #4 by megatron10 till then. I’m also keenly waiting to know the official solution.

1 Like

I’m sorry but the way I read that is, its not ready :neutral_face:

released :slight_smile:

2 Likes

Tysm. Hey, you said no pre-requisites…but editorial has so many advanced concepts I haven’t heard of!!like binarization,etc…:sweat_smile:

When did I mention this ? I think its quite unlikely that your every going to find a long challenge last problem without any pre-requisites.

That reply wasn’t meant for you :slight_smile: @anand20

I didn’t say no pre-requisites. I said very little pre-requisites. Did you open my submission.

This is the first line :
Pre-reqs:

  • Great understanding of DSU, graphs
  • BIT (Binary Indexed trees)

I consider that very little pre-requisites for the last problem of DIV1, is that fine ?

I don’t know about the editorial and its pre-requisites. There can be multiple ways of solving a problem so I really don’t know about the editorial. Also I have stated that the time complexity I have achieved is O(n*(log n)^3), I hope the editorial has done better.
Basically my solution is not the editorial, these are two different things you are mixing up.

I just considered it to be a good idea to point you to some solution/approach to solve the problem, until the editorial arrived. I definitely didn’t claim to be the best approach/intended approach for that matter.

2 Likes