DELTA - Editorial

PROBLEM LINK:

Practice
Contest

Author and Editorialist: kishen1912000

DIFFICULTY:

MEDIUM

PREREQUISITES:

DP, Graphs, Vertex Cover, Bitmask

PROBLEM:

Given a graph on N vertices and M weighted edges and a ‘vertex cover’ of the graph of size K, find the sum of weights of vertex-disjoint triangles in the graph such that at least one of the endpoints of each chosen triangle does not belong to the given vertex cover.

EXPLANATION:

The first important observation here is that the set of command posts form a Vertex Cover of the graph. Let’s denote the vertex cover by V and the set of remaining vertices as I. Then, the set I is an independent set, i.e., there is no edge between any two vertices in I. Therefore, any triangle in the graph can have at most one vertex from I. Hence, the triangles we require have exactly two endpoints from V and one endpoint from I. Henceforth, whenever I mention triangle, it means the kind of triangles we are interested in.

This problem can be solved using Dynamic Programming. Let us define an arbitrary numbering on the vertices in I, 1 ... N-K, and V, 1 ... K. Now, lets define dp[i][mask], where 1\le i \le N-K and 0 \le mask \le 2^K-1, as the maximum value that we can obtain by choosing vertex-disjoint triangles formed by vertices 1..i in I, and vertices j from V such that 1\le j \le K and mask\: \& \:2^j = 0, where \& denotes the bitwise and operator. This means, for a given mask, we do not consider the vertices from V to form triangles whose index has a 1 (set) bit in mask. For example, if mask = 0, then we can consider all vertices from V to form triangles. If mask = 2^K-1, then we cannot consider any vertex in V to form triangles.

To compute dp[i][mask]

Case 1: If we do not consider any triangle formed by vertex i, in this case,

dp[i][mask] = dp[i-1][mask]

Case 2: Let’s consider triangles formed by vertex i. Let v_{i_1} and v_{i_{2}} be two vertices in V with indices i_1 and i_2 respectively, and assume that mask_{i_1}=mask_{i_2} = 0, and v_{i_1},v_{i_2} and vertex i form a triangle. In this case, the recursion is,

dp[i][mask] = dp[i-1][mask+2^{i_1}+2^{i_2}],

i.e., we set the i_1 and i_2 bits and recurse on the first i-1 vertices.

Therefore, dp[i][mask] is computed by taking a max over all such valid pairs i_1, i_2 and Case 1.

The correctness of this dp can be proved by Induction, which is left as an exercise for the reader :grin:.

Time Complexity:

For a given i, in worst case, there are \mathcal{O}(K^2) such pairs i_1 and i_2 and 2^K different choices of mask. However, if you notice carefully, we are interested in only those mask values that have an even number of 1's in it (Why?).

Therefore, we have \mathcal{O}(2^{K-1}) choices of mask. Hence, the final time complexity is \mathcal{O}(2^{K-1}K^2N).

Note: If we use recursion, such unwanted states of the dp are automatically omitted.

SOLUTIONS:

Setter's Solution (Python: Iterative)
import sys
input = sys.stdin.readline

def main():
    n,m,k = [int(s) for s in input().split()]
    adj = [['n' for j in range(n)] for i in range(n)] 
    for i in range(m):
        u,v,w = [int(s) for s in input().split()]
        adj[u-1][v-1] = w
        adj[v-1][u-1] = w
    vc = [int(s)-1 for s in input().split()]
    vals = [i for i in range(n) if i not in vc]
    n -= k
    dp = [[0 for j in range(1<<k)] for i in range(n+1)]
    for i in range(n):
        for mask in range(1<<k):
            dp[i][mask] = max(dp[i][mask],dp[i-1][mask])
            for i1 in range(k-1):
                for i2 in range(i1+1,k):
                    if mask&(1<<i1)==0 and mask&(1<<i2)==0 and (adj[vals[i]][vc[i1]]!='n') and (adj[vals[i]][vc[i2]]!='n') and (adj[vc[i1]][vc[i2]]!='n'):
                        dp[i][mask] = max(dp[i][mask], adj[vals[i]][vc[i1]]+adj[vals[i]][vc[i2]]+adj[vc[i1]][vc[i2]] + dp[i-1][mask+(1<<i1)+(1<<i2)])
    print(max(0,dp[n-1][0]))

if __name__== '__main__':
    main()
Setter's Solution (C++: Recursive)
#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(),x.end()
#define pb push_back
#define FOR(i,a,b) for(auto i=a;i<b;i++)
#define FORO(u,v) for (auto u: v)
#define vi vector<int>
#define vvi vector<vi>
#define nl cout << '\n'
#define M 1000000007

int solve(vvi &adj, int i, int j, vvi &dp, vi &vals, vi &vc, int k){
    if (i<0)
        return 0;
    if (dp[i][j] !=-1)
        return dp[i][j];
    dp[i][j] = solve(adj,i-1,j,dp,vals,vc,k);
    FOR(i1,0,k-1){
        FOR(j1,i1+1,k){
            if ( !(j&(1<<i1)) && !(j&(1<<j1)) && (adj[vals[i]][vc[i1]]!=M) && (adj[vals[i]][vc[j1]]!=M) && (adj[vc[i1]][vc[j1]]!=M) ){
                dp[i][j] = max(dp[i][j], adj[vals[i]][vc[i1]]+adj[vals[i]][vc[j1]]+adj[vc[i1]][vc[j1]] + solve(adj,i-1,j+(1<<i1)+(1<<j1),dp,vals,vc,k));
            }
        }
    }
    return dp[i][j];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m,k,u,v,w;
    cin >> n >> m >> k;
    vvi adj(n,vi(n,M));
    FOR(i,0,m){
        cin >> u >> v >> w;
        adj[u-1][v-1] = w;
        adj[v-1][u-1] = w;
    }
    vi vc;
    FOR(i,0,k){
        cin >> u;
        vc.pb(u-1);
    }
    sort(all(vc));
    vi vals;
    int j=0;
    FOR(i,0,n){
        if(i!=vc[j]){
            vals.pb(i);
        }
        else{
            j++;
        }
    }
    n -= k;
    vvi dp(n,vi(1<<k,-1));
    cout << max(0,solve(adj,n-1,0,dp,vals,vc,k));nl;
    return 0;
}