# HackerRank The Blacklist problem solution

In this HackerRank The Blacklist problem solution A new gangster is trying to take control of the city. He makes a list of his N adversaries (e.g. gangster 1, gangster 2, ... gangster N - 1, gangster N) and plans to get rid of them.

K mercenaries are willing to do the job. The gangster can use any number of these mercenaries. But he has to honor one condition set by them: they have to be assigned in such a way that they eliminate a consecutive group of gangsters in the list, e.g. gangster i, gangster i + 1, ..., gangster j - 1, gangster j, where the following is true: 1 <= i <= j <= N.

While our new gangster wants to kill all of them, he also wants to pay the least amount of money. All mercenaries charge a different amount to kill different people. So he asks you to help him minimize his expenses.

## Problem solution in Python.

```#!/bin/python3

import os
import sys

N, K = map(int, input().split())
cost = []

INF = 10**8-1

for i in range(K):
prices = list (map(int, input().split()))
prices.reverse()
cost.append(prices)

dp = []
dp.append([INF] * (N + 1))

dp[0][0] = 0

return not (2 << hitman) & mask

return mask | (2 << hitman)

for hitman in range(K):
for num_to_kill in range(1, N - already_killed+1):

print (min(dp[i][N] for i in range(MASK)))```

## Problem solution in Java.

```import java.io.*;
import java.util.*;

public class Solution {

static final int INF = Integer.MAX_VALUE / 10;

static boolean hitmanAvailable(int hitman, int mask) {
return (((2 << hitman)) & mask) == 0;
}

static int useHitman(int hitman, int mask) {
return mask | (2 << hitman);
}

static int sum(int[][] amounts, int hitman, int alreadyKilled, int numToKill) {
int s = 0;
for (int i = alreadyKilled; i < alreadyKilled + numToKill; i++) {
s += amounts[hitman][i];
}
return s;
}

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

int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());

int[][] amounts = new int[k][n];

for (int i = 0; i < k; i++) {

for (int j = 0; j < n; j++) {
int item = Integer.parseInt(st.nextToken());
amounts[i][j] = item;
}
}

int maskMax = 2 << k;

int[][] dp = new int[maskMax][n + 1];
for (int i = 0; i < maskMax; i++) {
for (int j = 0; j < n + 1; j++) {
dp[i][j] = INF;
}
}
dp[0][0] = 0;

for (int hitman = 0; hitman < k; hitman++) {
for (int numToKill = 1; numToKill < n - alreadyKilled + 1; numToKill++) {
Math.min(
}
}
}
}
}

int result = Integer.MAX_VALUE;
for (int i = 0; i < maskMax; i++) {
result = Math.min(result, dp[i][n]);
}

bw.write(String.valueOf(result));
bw.newLine();

bw.close();
br.close();
}
}```

## Problem solution in C++.

```#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define For(i,a,b) for(i=a;i<b;i++)
#define loop(i,b) for(i=0;i<b;i++)
#define Loop(i,b) for(i=1;i<=b;i++)
#define pi(n) printf("%d ",n)
#define si(n) scanf("%d",&n)
const int MOD=1e9+7;
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef long long LL;
#define F first
#define S second
#define sz size
#define pLL(x) cout<<x<<' '
#define fill(x,c) memset(x,c,sizeof(x))
#define DB(x)              cout<<__LINE__<<" :: "<<#x<< ": "<<x<<endl;
#define DB2(x, y)          cout<<__LINE__<<" :: "<<#x<< ": "<<x<<" | "<<#y<< ": "<<y<<endl;
#define DB3(x, y, z)       cout<<__LINE__<<" :: "<<#x<< ": "<<x<<" | "<<#y<< ": "<<y<<" | "<<#z<<": "<<z<<endl
int a[30][30];
int dp[30][30][1<<12];

int N,K;
LL solve(int curr,int prev,int done)
{
int i;

if(curr == N)
return 0;

LL val;
if(prev != 12)
{
val=(LL)a[prev][curr];
val+=solve(curr+1,prev,done);
}

else val=1e15;

if(dp[curr][prev][done]!=-1)
return dp[curr][prev][done];

for(i=0;i<K;++i)
{
if(((done>>i)&1) == 0)
val=min(val,a[i][curr]+solve(curr+1,i,done|(1<<i)));
}

return (dp[curr][prev][done]=val);
}

int main()
{
int n,t,m,l,k,ans,i,j,res=0,fl;
t=1;
while(t--)
{
si(n);
si(m);
N=n;K=m;

loop(i,m)
{
loop(j,n)
si(a[i][j]);
}

memset(dp,-1,sizeof(dp));

cout<<solve(0,12,0)<<endl;

}
return 0;
}```

## Problem solution in C.

```#include <stdio.h>
#include <stdlib.h>
#define INF 300000
int mine(int x,int y);
int table[10][20],dp[10][1024][20];

int main(){
int N,K,i,j,k,l,min=-1;
scanf("%d%d",&N,&K);
for(i=0;i<K;i++)
for(j=0;j<N;j++)
scanf("%d",&table[i][j]);
for(k=0;k<N;k++)
for(j=0;j<(1<<K);j++)
for(i=0;i<K;i++){
if(!(j&(1<<i)))
dp[i][j][k]=INF;
else if(!k)
if(j!=(1<<i))
dp[i][j][k]=INF;
else
dp[i][j][k]=table[i][k];
else{
dp[i][j][k]=dp[i][j][k-1];
for(l=0;l<K;l++)
if(l!=i && (1<<l)&j)
dp[i][j][k]=mine(dp[i][j][k],dp[l][j^(1<<i)][k-1]);
dp[i][j][k]+=table[i][k];
}
}
for(i=0;i<K;i++)
for(j=0;j<(1<<K);j++)
if(min==-1 || dp[i][j][N-1]<min)
min=dp[i][j][N-1];
printf("%d",min);
return 0;
}
int mine(int x,int y){
return (x<y)?x:y;
}```