Secure the Servers

Author : muditk_24

Required Knowledge : Graphs, DP, Flows

Time Complexity : $\mathcal{O}((N + M)^2 \cdot (N + M + NM) + M \cdot N \cdot 5^N)$

Editorialist : muditk_24

Approach:

Phase 1: Hardware Calibration

The first phase asks us to verify if the physical network can route a target throughput of exactly:

$T = \min\left(\sum_{i=1}^n a_i, \sum_{j=1}^m b_j\right) \times 10^6$ packets per second.

This is a direct Maximum Flow problem. We construct a flow network with a source $S$, a sink $T$, $n$ server vertices, and $m$ firewall vertices:

• Source to Servers: Add directed edges from $S$ to each server $i$ with capacity $a_i \times 10^6$.
• Firewalls to Sink: Add directed edges from each firewall $j$ to $T$ with capacity $b_j \times 10^6$.
• Internal Routing: Add directed edges from each server $i$ to each firewall $j$ with capacity $c_{i,j}$.

If it passes, we move to Phase 2.

Phase 2: The Hacker Game

In the defense phase, the matrix $c_{i,j}$ represents a fixed cost to install a software license. Once a license is bought, it provides infinite capacity between that server and firewall, limited only by the firewall's global capacity $b_j$.

The Core Insight: Max-Flow Saturation

Using the Max-Flow Min-Cut theorem, the hacker's profit is $(\sum a_i) - \text{MaxFlow}$. To ensure the hacker's profit is $\le 0$, Alice must choose licenses such that the Maximum Flow in the network is exactly $\sum a_i$. This means every unit of data from every server $i$ must be able to find a path to the sink.

The Optimal Approach (Base-Encoded DP)

Since we need to track how much of each $a_i$ has been "pushed" to the firewalls, we use Dynamic Programming. Because $a_i \le 4$, we represent the "remaining flow needed" for all $n$ servers as a single integer using Base-5 encoding.

• State: $DP[j][S]$ is the minimum cost using the first $j$ firewalls to reach a flow state $S$ (where $S$ represents the remaining units needed from each server $1 \dots n$).
• Initial State: $DP[0][\text{initial } a_i] = 0$. All other states are $\infty$.
• Transitions: For each firewall $j$, we iterate through all possible flow states. For each state, we can:
  1. Skip an edge $(i, j)$: Cost is $0$, flow remains the same.
  2. Buy license $(i, j)$: Pay $c_{i,j}$, which allows us to push any amount of flow from server $i$ through firewall $j$, as long as the total flow through firewall $j$ does not exceed its capacity $b_j$.

Setter's Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = 1e18;

int n, m;
ll capacity[20][20];
vector<int> adj[20];
int a[7], b[7], c[7][7];
int powers[7];
int dp[15625]; 

ll bfs(int s, int t, vector<int>& parent, int nodes){
    fill(parent.begin(), parent.end(), -1);
    parent[s] = -2;
    queue<pair<int, ll>> q;
    q.push({s, INF});

    while(!q.empty()){
        int cur = q.front().first;
        ll flow = q.front().second;
        q.pop();

        for(int next : adj[cur]){
            if(parent[next] == -1 && capacity[cur][next] > 0){
                parent[next] = cur;
                ll newFlow = min(flow, capacity[cur][next]);
                if (next == t) return newFlow;
                q.push({next, newFlow});
            }
        }
    }
    return 0;
}

ll maxflow(int s, int t, int nodes){
    ll flow = 0;
    vector<int> parent(nodes);
    ll newFlow;
    while((newFlow = bfs(s, t, parent, nodes))){
        flow += newFlow;
        int cur = t;
        while(cur != s){
            int prev = parent[cur];
            capacity[prev][cur] -= newFlow;
            capacity[cur][prev] += newFlow;
            cur = prev;
        }
    }
    return flow;
}

void solve() {
    cin >> n >> m;
    ll suma = 0, sumb = 0;
    for(int i = 0; i < n; i++){ cin >> a[i]; suma += a[i]; }
    for(int j = 0; j < m; j++){ cin >> b[j]; sumb += b[j]; }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) cin >> c[i][j];

    int S = 0, T = n + m + 1;
    for(int i = 0; i < n; i++){
        capacity[S][i + 1] = (ll)a[i] * 1000000;
        adj[S].push_back(i + 1);
        adj[i + 1].push_back(S);
    }
    for(int j = 0; j < m; j++){
        capacity[n + j + 1][T] = (ll)b[j] * 1000000;
        adj[n + j + 1].push_back(T);
        adj[T].push_back(n + j + 1);
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            capacity[i + 1][n + j + 1] = (ll)c[i][j];
            adj[i + 1].push_back(n + j + 1);
            adj[n + j + 1].push_back(i + 1);
        }
    }

    ll target = min(suma, sumb) * 1000000;
    if(maxflow(S, T, T + 1) < target){
        cout << -1 << endl;
        return;
    }

    powers[0] = 1;
    for(int i = 1; i <= n; i++) powers[i] = powers[i - 1] * 5;

    int ini = 0;
    for(int i = 0; i < n; i++) ini += a[i] * powers[i];

    fill(dp, dp + powers[n], 1e9);
    dp[ini] = 0;

    for(int j = 0; j < m; j++){
        vector<vector<int>> temp(b[j] + 1, vector<int>(powers[n], 1e9));
        for(int s = 0; s < powers[n]; s++) temp[0][s] = dp[s];

        for(int i = 0; i < n; i++){
            for(int cap = b[j]; cap >= 0; cap--){
                for(int s = 0; s < powers[n]; s++){
                    if(temp[cap][s] >= 1e9) continue;

                    int rem = (s / powers[i]) % 5;
                    for(int f = 1; f <= min(rem, b[j] - cap); f++){
                        int nxt = s - f * powers[i];
                        temp[cap + f][nxt] = min(temp[cap + f][nxt], temp[cap][s] + c[i][j]);
                    }
                }
            }
        }
        for(int s = 0; s < powers[n]; s++){
            for(int cap = 0; cap <= b[j]; cap++){
                dp[s] = min(dp[s], temp[cap][s]);
            }
        }
    }

    if(dp[0] >= 1e9) cout << -1 << endl;
    else cout << dp[0] << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Tester's Code

import sys
from collections import deque

INF = 10**18
mul = 1000000

capacity = [[0] * 20 for _ in range(20)]
adj = [[] for _ in range(20)]
tot = 0
n = 0
m = 0
a = []
b = []
c = []
mn = INF
curra = [0] * (1 << 6)
mxb = [0] * (1 << 6)

def bfs(s, t, parent):
    for i in range(len(parent)):
        parent[i] = -1
    parent[s] = -2
    q = deque()
    q.append((s, INF))

    while q:
        cur, flow = q.popleft()

        for nxt in adj[cur]:
            if parent[nxt] == -1 and capacity[cur][nxt] > 0:
                parent[nxt] = cur
                newFlow = min(flow, capacity[cur][nxt])
                if nxt == t:
                    return newFlow
                q.append((nxt, newFlow))
    return 0

def maxflow(s, t):
    flow = 0
    parent = [0] * (tot + 1)
    while True:
        newFlow = bfs(s, t, parent)
        if newFlow == 0:
            break
        flow += newFlow
        cur = t
        while cur != s:
            prev = parent[cur]
            capacity[prev][cur] -= newFlow
            capacity[cur][prev] += newFlow
            cur = prev
    return flow

def helper(idx, curr):
    global mn
    if curr >= mn:
        return
    if idx == n:
        mn = min(mn, curr)
        return

    for mask in range(1 << m):
        cost = 0
        for j in range(m):
            if (mask >> j) & 1:
                cost += c[idx][j]

        if curr + cost >= mn:
            continue

        valid = True
        fsubset = -1
        for subset in range(1 << m):
            if (mask & subset) == mask:
                curra[subset] += a[idx]
                if curra[subset] > mxb[subset]:
                    valid = False
                    fsubset = subset
                    break

        if valid:
            helper(idx + 1, curr + cost)

        limit = (1 << m) if valid else (fsubset + 1)
        for subset in range(limit):
            if (mask & subset) == mask:
                curra[subset] -= a[idx]

def solve():
    global n, m, a, b, c, tot, mn, capacity, adj, curra, mxb
    data = sys.stdin.read().split()
    ptr = 0
    
    n = int(data[ptr])
    ptr += 1
    m = int(data[ptr])
    ptr += 1
    
    a = []
    suma = 0
    for i in range(n):
        val = int(data[ptr])
        a.append(val)
        suma += val
        ptr += 1
        
    b = []
    sumb = 0
    for i in range(m):
        val = int(data[ptr])
        b.append(val)
        sumb += val
        ptr += 1
        
    c = [[0] * m for _ in range(n)]
    
    for i in range(20):
        for j in range(20):
            capacity[i][j] = 0
        adj[i] = []
        
    tot = n + m + 2
    source = 0
    sink = n + m + 1

    for i in range(n):
        for j in range(m):
            c[i][j] = int(data[ptr])
            ptr += 1
            adj[i + 1].append(n + 1 + j)
            adj[n + 1 + j].append(i + 1)
            capacity[i + 1][n + 1 + j] = c[i][j]

    for i in range(n):
        adj[source].append(i + 1)
        adj[i + 1].append(source)
        capacity[source][i + 1] = a[i] * mul
        
    for j in range(m):
        adj[n + 1 + j].append(sink)
        adj[sink].append(n + 1 + j)
        capacity[n + 1 + j][sink] = b[j] * mul

    if maxflow(source, sink) < (min(suma, sumb) * mul):
        print("-1")
        return

    if suma > sumb:
        print("-1")
        return

    for i in range(1 << 6):
        curra[i] = 0
        
    for i in range(1 << m):
        cost = 0
        for j in range(m):
            if (i >> j) & 1:
                cost += b[j]
        mxb[i] = cost

    helper(0, 0)
    
    result = mn if mn != INF else -1
    print(result)

if __name__ == "__main__":
    sys.setrecursionlimit(2000)
    solve()