In this HackerRank Demanding Money problem solution 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.
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))))
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;
}