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 = []

MASK = 2<<K
INF = 10**8-1

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

dp = []
for i in range(MASK):
    dp.append([INF] * (N + 1))

dp[0][0] = 0

def hitman_available(hitman, mask):
    return not (2 << hitman) & mask

def use_hitman(hitman, mask):
    return mask | (2 << hitman)

for already_killed in range(N):
    for mask in range(MASK):
        for hitman in range(K):
            if hitman_available(hitman, mask):
                mask_after = use_hitman(hitman, mask)
                for num_to_kill in range(1, N - already_killed+1):
                    dp[mask_after][num_to_kill + already_killed] = min(
                        dp[mask_after][num_to_kill + already_killed],
                        dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed+num_to_kill]))

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 {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    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++) {
      st = new StringTokenizer(br.readLine());

      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 alreadyKilled = 0; alreadyKilled < n; alreadyKilled++) {
      for (int mask = 0; mask < maskMax; mask++) {
        for (int hitman = 0; hitman < k; hitman++) {
          if (hitmanAvailable(hitman, mask)) {
            int maskAfter = useHitman(hitman, mask);
            for (int numToKill = 1; numToKill < n - alreadyKilled + 1; numToKill++) {
              dp[maskAfter][numToKill + alreadyKilled] =
                  Math.min(
                      dp[maskAfter][numToKill + alreadyKilled],
                      dp[mask][alreadyKilled] + sum(amounts, hitman, alreadyKilled, numToKill));
            }
          }
        }
      }
    }

    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;
}