HackerRank Demanding Money problem solution

In this HackerRank Demanding Money problem solution Killgrave wants to use his mind control powers to get money from the Justice League superheroes living in N houses in Happy Harbor that are numbered sequentially from 1 to N. There are M roads, and each road connects two different houses, Aj and Bj. Each superhero house i (where 1 <= i <= N) has Ci dollars stashed away for a rainy day.

As long as a superhero is home at house , Killgrave knows they will hand over all of their saved money, Ci. Once he gets money from them, he moves on to the next house. However, the superheroes are cunning; when Killgrave comes to house X, every neighbor immediately connected to house X by a single road skips town for a couple of days (making it impossible for Killgrave to get money from them). In other words, after Killgrave visits all the superheroes he wants, there will be no road in which he was able to get money from both houses on either end of the road.

What is the maximum amount of money Killgrave can collect from the superheroes, and how many different ways can Killgrave get that amount of money? Two ways are considered to be different if the sets of visited houses are different.

HackerRank Demanding Money problem solution in Python.

#!/bin/python3

import os
import sys

def solve(C,G) :
    minLost = {}
    def getMinLost(housesToVisit) :
#        print("getMinLost %s :" % str(housesToVisit))
        if not housesToVisit :
            return 0,1
        
        key = frozenset(housesToVisit)
        if key in minLost :
            return minLost[key]
        
        a = housesToVisit.pop()
        # Do not visit house a
        lost, nb = getMinLost(housesToVisit)
        lost += C[a]
        # Visit house a
        lostHouses = set(b for b in G[a] if b in housesToVisit)
        lostMoney = sum(C[b] for b in lostHouses)
        losta, nba = getMinLost(housesToVisit - lostHouses)
        losta += lostMoney
        housesToVisit.add(a)
        
        if losta < lost :
            lost, nb = losta, nba
        elif losta == lost :
            nb += nba
        
        minLost[key] = (lost,nb)
        return minLost[key]
    
    amount, number = getMinLost(set(range(len(C))))
    return sum(C)-amount, number
    
    
N,M = map(int,input().split())
C = tuple(map(int,input().split()))
G = {a : set() for a in range(len(C))}
for _ in range(M) :
    a,b = map(int,input().split())
    G[a-1].add(b-1)
    G[b-1].add(a-1)
print(" ".join(map(str,solve(C,G))))

Demanding Money problem solution in Java.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

    /*
     * Complete the demandingMoney function below.
     */
    private static long maxMoney = Integer.MIN_VALUE;
    private static Map<Long, Long> solutions;
    private static Set<Integer>[] graph;
    private static int[] moneys;
    
    static long[] demandingMoney(int[] inputMoneys, int[][] roads) 
    {
        if (inputMoneys == null || inputMoneys.length == 0)
        {
            return new long[] {0, 0};
        }
        
        int n = inputMoneys.length;
        moneys = inputMoneys;
        graph = new Set[n+1];
        solutions = new HashMap<>();
    
        for (int i = 1; i <= n; i++)
        {
            graph[i] = new HashSet<>();
        }
        
        for (int[] road : roads)
        {
            int max = road[0] > road[1] ? road[0] : road[1];
            int min = road[0] > road[1] ? road[1] : road[0];
            graph[min].add(max);
            
            graph[min].add(min);
            graph[max].add(max);
        }
        
        Set<Integer> visited = new HashSet<>();
        int soloMoney = 0;
        int zeroCount = 0;
        
        for (int i = 1; i <= n; i++)
        {
            if (graph[i].size() == 0)
            {
                visited.add(i);
                soloMoney += moneys[i-1];
                zeroCount += moneys[i-1] == 0 ? 1 : 0;
            }
        }
        
        solutions.put(0L, 1L);
        for (int start = 1; start <= n; start++)
        {
            if (!visited.contains(start))
            {
                search(start, visited, 0L);
            }
        }
        
        long result = soloMoney;
        long count = 1;
        
        for (int i = 0; i < zeroCount; i++)
        {
            count *= 2L;
        }
        
        if (maxMoney != Integer.MIN_VALUE)
        {
            count *= solutions.get(maxMoney);
            result += maxMoney;
        }
        
        return new long[] { result, count };
    }
    
    private static void search(int start, Set<Integer> visited, long totalMoney)
    {
        totalMoney += moneys[start-1];
        solutions.put(totalMoney, solutions.getOrDefault(totalMoney, 0L) + 1L);
        maxMoney = Math.max(maxMoney, totalMoney);
        
        Set<Integer> removed = new HashSet<>();
        for (int neighbor : graph[start])
        {
            if (!visited.contains(neighbor))
            {
                visited.add(neighbor);
                removed.add(neighbor);
            }
        }
        
        for (int next = start+1; next <= moneys.length; next++)
        {
            if (visited.contains(next))
            {
                continue;
            }
            
            search(next, visited, totalMoney);
        }
        
        visited.removeAll(removed);
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] nm = scanner.nextLine().split(" ");
        scanner.skip("(rn|[nru2028u2029u0085])*");

        int n = Integer.parseInt(nm[0]);

        int m = Integer.parseInt(nm[1]);

        int[] money = new int[n];

        String[] moneyItems = scanner.nextLine().split(" ");
        scanner.skip("(rn|[nru2028u2029u0085])*");

        for (int moneyItr = 0; moneyItr < n; moneyItr++) {
            int moneyItem = Integer.parseInt(moneyItems[moneyItr]);
            money[moneyItr] = moneyItem;
        }

        int[][] roads = new int[m][2];

        for (int roadsRowItr = 0; roadsRowItr < m; roadsRowItr++) {
            String[] roadsRowItems = scanner.nextLine().split(" ");
            scanner.skip("(rn|[nru2028u2029u0085])*");

            for (int roadsColumnItr = 0; roadsColumnItr < 2; roadsColumnItr++) {
                int roadsItem = Integer.parseInt(roadsRowItems[roadsColumnItr]);
                roads[roadsRowItr][roadsColumnItr] = roadsItem;
            }
        }

        long[] result = demandingMoney(money, roads);

        for (int resultItr = 0; resultItr < result.length; resultItr++) {
            bufferedWriter.write(String.valueOf(result[resultItr]));

            if (resultItr != result.length - 1) {
                bufferedWriter.write(" ");
            }
        }

        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}

Problem solution in C++.

#include <bits/stdc++.h>

using namespace std;

using tint=int;
#define int long long
vector<int> c;
int n;
class E;
vector<list<E>> e;
using T=array<int,2>;

class E {
    list<E>::iterator it;
    int v;
    public:
    static void insert(int a, int b) {
        E x; x.v=b; e[a].push_front(x); x.it=e[a].begin();
        x.v=a; e[b].push_front(x); x.it->it=e[b].begin();
    };
    list<E>::iterator erase() {
        auto tmp=*it;
        e[v].erase(it);
        return e[tmp.v].erase(tmp.it);
    };
    operator int() const {return v;}
};

T dfs(int i, vector<bool>&v) { //random node selection
    T r={i,1};
    v[i]=1;
    for(int x : e[i]) {
        if(!v[x]) {
            T tmp=dfs(x,v); r[1]+=tmp[1];
            if(rand()%r[1]<tmp[1]) r[0]=tmp[0];
        }
    }
    return r;
}

void reduce(T& a, const T& b) {
    a[0]+=b[0];
    a[1]*=b[1];
}

T dop(int i) {
    if(e[i].empty())return {c[i],c[i]?1:2};
    vector<int> p;
#define edo(p,x) for(auto it=x.begin();it!=x.end();it=it->erase())p.push_back(*it)
    edo(p,e[i]);
    vector<bool> v(n);
    T r={0,1};for(auto x : p)if(!v[x])reduce(r,dop(dfs(x,v)[0]));
    vector<vector<int>> p2(p.size());
    for(int i=0;i<p.size();i++)edo(p2[i],e[p[i]]);
#undef edo
    v.assign(n,0);for(auto x:p)v[x]=1;T r2={c[i],1};for(auto&x:p2)for(auto y:x)if(!v[y])reduce(r2,dop(dfs(y,v)[0]));
    for(int i=0;i<p2.size();i++)for(auto x : p2[i])E::insert(p[i],x);
    for(auto x : p)E::insert(i,x);
    return r[0]==r2[0]?T{r[0],r[1]+r2[1]}:r[0]>r2[0]?r:r2;
}

tint main() {
    int m;cin>>n>>m;
    c.resize(n);e.resize(n);for(auto&x:c)cin>>x;
    for(int i=0;i<m;i++) { int x,y; cin>>x>>y; E::insert(x-1,y-1); }
    T r={0,1};vector<bool> v(n);for(int i=0;i<n;i++)if(!v[i])reduce(r,dop(dfs(i,v)[0]));
    cout<<r[0]<<" "<<r[1]<<endl;
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include<stdbool.h>
int max=0,count=0;
void aa(int curr,int n,bool hash1[],int cost[],int a[35][35],int total){
 if(curr>n){
     if(total>max){
         max=total;
         count=1;
     }
     else if(total==max){
         count++;
     }
     return;
 }
   
    bool hash2[35];int i,j,pp=0;
    for(i=1;i<=n;i++){
        hash2[i]=hash1[i];
    }
    
    aa(curr+1,n,hash1,cost,a,total);
    
    if(hash2[curr]==1)
        return;
    //hash2[curr]=1;
    for(i=1;i<=n;i++){
        hash2[i]=a[curr][i]|hash1[i];
       
    }
    aa(curr+1,n,hash2,cost,a,total+cost[curr]);
}
void dfs(int curr,bool vis[],bool o[],int a[35][35],int n){
    vis[curr]=1;
    o[curr]=0;
    int i;
    for(i=1;i<=n;i++){
        if(a[curr][i]==1 && vis[i]==0)
            dfs(i,vis,o,a,n);
    }
}
int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    int n,m,i,j,k,l;
    static int a[35][35],cost[35];bool hash1[35]={0};
    scanf("%d %d",&n,&m);

    for(i=1;i<=n;i++){
        scanf("%d",&cost[i]);
    }
    
    for(i=1;i<=m;i++){
        scanf("%d %d",&k,&l);
        a[k][l]=1;
        a[l][k]=1;
    }
    long long int ans=0,ans1=1;
    bool vis[35]={0};
     bool o[35];
    for(i=1;i<=n;i++){
        if(vis[i]==1)
            continue;
       
        for(j=1;j<=n;j++)
            o[j]=1;
        
        dfs(i,vis,o,a,n);
        max=0;
        count=0;
        aa(1,n,o,cost,a,0);
            ans+=max;
            ans1*=count;
    }
    //aa(1,n,hash1,cost,a,0);
    printf("%lld %lldn",ans,ans1);
    return 0;
}