CDUTSV01 Heist Editorial

editorial
1

PROBLEM LINK: Bank Cooperation

AUTHOR: sohit_1212

DIFFICULTY: Medium

PREREQUISITES: Bitmasking , Recursion.

We make use of simple bitmasking to mark for each bank its co-operating banks.
Using recursion, we either sum or do not sum the gold from that bank and keep track of the banks that have been selected or are not to be selected(because its co-operating bank has already been) using bitmasking.

#include <iostream>
#include <math.h>

#define N 8

using namespace std;

void foo(int c[N], int num, int i, long sum, int a[], long &max) {
    
    //cout<<num<<" "<<i<<endl;
    
    if(num == pow(2,N)-1){
        max = max < sum ? sum : max;
        return;
    }
    
    num = num | 1<<i;
    int n = num | c[i] ;
    
    
    foo(c,n,log2(~n&-(~n)),sum+a[i],a,max);     //log2(~n&-(~n)) to get the rightmost unset bit.
    foo(c,num,log2(~num&-(~num)),sum,a,max);
}

int main() {
    int a[N];
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    
    int p;
    scanf("%d",&p);
    
    int c[N];
    for(int i=0;i<N;i++) c[i] = 0;
    
    for(int i=0;i<p;i++) {
        int s,t;
        scanf("%d%d",&s,&t);
        c[s-1] = c[s-1] | (1<<(t-1));
        c[t-1] = c[t-1] | (1<<(s-1));
    }
    //for(int i=0;i<N;i++) cout<<c[i]<<" ";
    long max = 0;
    foo(c,0,0,0,a,max);
    cout<<max<<endl;
    return 0;
}

`