HackerRank The Blacklist Problem Solution

In this post, we will solve 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.
Input Format
The first line contains two space-separated integers, N and K. Then K lines follow, each containing N integers as follows:
The jth number on the ith line is the amount charged by the ith mercenary for killing the 7th gangster on the list.

Output Format

Just one line, the minimum cost for killing the N gangsters on the list.

Sample Input

3 2
1 4 1
2 2 2

Sample Output

Explanation

The new gangster can assign mercenary 1 to kill gangster 1, and mercenary 2 to kill gangster 2 and gangster 3.

HackerRank The Blacklist Problem Solution

Table of Contents

The Blacklist C Solution

#include <stdio.h>
#include <limits.h>
#define MIN(x, y) x < y ? x : y
int res, n, k, a[15][25] = {0};
void find(int curr, int d[], int i, int sumsofar)
{
    
    
    if (sumsofar >= res)
    return;
    if (curr > n)
    {
        res = sumsofar;
        return;
    }
    int p[25], x = 0;
    
    
    int j, l;
    for (j = 1; j <= k; j++)
    if (d[j] == 0)
    p[x++] = j;
    for (l = curr; l <= n; l++)
    {
        for (j = 0; j < x; j++)
        if (sumsofar + a[p[j]][l] < sumsofar + a[i][l] && sumsofar + a[p[j]][l] < res)
        {
            
            d[p[j]] = 1;
            find(l + 1, d, p[j], sumsofar + a[p[j]][l]);
            d[p[j]] = 0;
        }
        sumsofar += a[i][l];
        if (sumsofar >= res)
        return;
    }
    res = sumsofar;
}

int main()
{
    int i, j;
    scanf("%d%d", &n, &k);
    for (i = 1; i <= k; i++)
    for (j = 1; j <= n; j++)
    scanf("%d", &a[i][j]);
    
    
    res = INT_MAX;
    int d[25] = {0};
    for (i = 1; i <= k; i++)
    {
        d[i] = 1;
        find(1, d, i, 0);
        d[i] = 0;
    }
    printf("%d\n", res);
    return 0;
}

The Blacklist C++ Solution

#include <bits/stdc++.h>

using namespace std;
vector<string> split_string(string);

struct Segment {
  Segment(int price, int mask, int leftEnd, int rightEnd)
      : price(price), mask(mask), leftEnd(leftEnd), rightEnd(rightEnd) {}

  bool operator<(const Segment &other) const { return price < other.price; }

  int price;
  int mask;
  int leftEnd;
  int rightEnd;
};

vector<Segment> combine(const vector<Segment> &vec1,
                        const vector<Segment> &vec2) {
  vector<Segment> result;
  for_each(begin(vec1), end(vec1), [&result, &vec2](const Segment &seg1) {
    for_each(begin(vec2), end(vec2), [&result, &seg1](const Segment &seg2) {
      int mask = seg1.mask & seg2.mask;
      if (mask == 0 ||
          ((1 << seg1.rightEnd) == mask && seg1.rightEnd == seg2.leftEnd)) {
        result.emplace(result.end(), seg1.price + seg2.price,
                       seg1.mask | seg2.mask, seg1.leftEnd, seg2.rightEnd);
      }
    });
  });
  std::sort(begin(result), end(result));
  const int max_depth = 10000;
  if (result.size() > max_depth) {
    result.erase(begin(result) + max_depth, end(result));
  }
  cout << ">>>" << result.size() << endl;
  return result;
}

vector<vector<Segment>>
combineAll(const vector<vector<Segment>> &segmentAmounts) {
  vector<vector<Segment>> result;
  for (int i = 0; i < segmentAmounts.size(); i += 2) {
    if (i + 1 < segmentAmounts.size()) {
      auto combination = combine(segmentAmounts[i], segmentAmounts[i + 1]);
      result.emplace(result.end(), combination);
    } else {
      result.emplace(result.end(), segmentAmounts[i]);
    }
  }
  return result;
}

/*
 * Complete the blacklist function below.
 */
int blacklist(vector<vector<int>> amounts) {
  /*
   * Write your code here.
   */
  vector<vector<Segment>> segmentAmounts;

  for (int i = 0; i < amounts[0].size(); ++i) {
    vector<Segment> segments;
    for (int j = 0; j < amounts.size(); ++j) {
      segments.emplace(segments.end(), amounts[j][i], 1 << j, j, j);
    }
    std::sort(std::begin(segments), std::end(segments));
    // std::for_each(std::begin(segments), std::end(segments), [](const Segment
    // &s) { cout << s.mask << " " << s.price << endl; });
    segmentAmounts.emplace(segmentAmounts.end(), std::move(segments));
  }

  while (segmentAmounts.size() > 1) {
    segmentAmounts = combineAll(segmentAmounts);
    cout << segmentAmounts.size() << endl;
  }

  return segmentAmounts[0][0].price;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string nk_temp;
    getline(cin, nk_temp);

    vector<string> nk = split_string(nk_temp);

    int n = stoi(nk[0]);

    int k = stoi(nk[1]);

    vector<vector<int>> amounts(k);
    for (int amounts_row_itr = 0; amounts_row_itr < k; amounts_row_itr++) {
        amounts[amounts_row_itr].resize(n);

        for (int amounts_column_itr = 0; amounts_column_itr < n; amounts_column_itr++) {
            cin >> amounts[amounts_row_itr][amounts_column_itr];
        }

        cin.ignore(numeric_limits<streamsize>::max(), '\n');
    }

    int result = blacklist(amounts);

    fout << result << "\n";

    fout.close();

    return 0;
}

vector<string> split_string(string input_string) {
    string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
        return x == y and x == ' ';
    });

    input_string.erase(new_end, input_string.end());

    while (input_string[input_string.length() - 1] == ' ') {
        input_string.pop_back();
    }

    vector<string> splits;
    char delimiter = ' ';

    size_t i = 0;
    size_t pos = input_string.find(delimiter);

    while (pos != string::npos) {
        splits.push_back(input_string.substr(i, pos - i));

        i = pos + 1;
        pos = input_string.find(delimiter, i);
    }

    splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

    return splits;
}

The Blacklist C Sharp Solution

using System;
using System.Linq;

class Solution
{
    static void Main(String[] args)
    {
        var line = Array.ConvertAll(Console.ReadLine().Trim().Split(), Int32.Parse);
        int N = line[0];
        int K = line[1];

        int[][] cost = new int[K][];

        for (int i = 0; i < K; i++)
        {
            cost[i] = Array.ConvertAll(Console.ReadLine().Trim().Split(), Int32.Parse);
        }

        bool[] used = new bool[K];

        int combinations = (1 << K) * K + K;

        int[] costCache = new int[combinations];

        for (int i = 0; i < combinations; i++)
        {
            costCache[i] = Int32.MaxValue;
        }

        for (int i = 0; i < K; i++)
        {
            int c = (1 << i) * K + i;
            costCache[c] = cost[i][0];
        }

        for (int i = 1; i < N; i++)
        {
            int[] nextCostCache = new int[combinations];

            for (int j = 0; j < combinations; j++)
            {
                nextCostCache[j] = Int32.MaxValue;
            }

            for (int combination = 0; combination < combinations; combination++)
            {
                if (costCache[combination] == Int32.MaxValue) continue;

                int lastMercenery = combination % K;

                nextCostCache[combination] = Math.Min(nextCostCache[combination], costCache[combination] + cost[lastMercenery][i]);

                int usedMerceneries = combination / K;
                for (int m = 0; m < K; m++)
                {
                    if ((usedMerceneries >> m) % 2 == 1) continue;
                    int merceneryOffset = 1 << m;
                    int nextCombination = combination + merceneryOffset * K - lastMercenery + m;

                    nextCostCache[nextCombination] = Math.Min(nextCostCache[nextCombination], costCache[combination] + cost[m][i]);
                }
            }

            costCache = nextCostCache;
        }

        int minCost = costCache.Min();

        Console.WriteLine(minCost);
    }
}

The Blacklist Java Solution

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

The Blacklist JavaScript Solution

Array.matrix = function(numrows, numcols, initial){
    var arr = [];
    for (var i = 0; i < numrows; ++i){
        var columns = [];
        for (var j = 0; j < numcols; ++j){
            columns[j] = initial;
        }
        arr[i] = columns;
    }
    return arr;
};


function processData(input) {
    //Enter your code here
    var inputArray = input.split("\n");
    var params = inputArray[0].split(" ").map(Number);
    var N = params[0];
    var K = params[1];
    var mat = [];
    for (var i = 1; i <= K; i++ ) {
        mat[i-1] = inputArray[i].split(" ").map(Number);
    }
    //console.log(mat);
    var DP = Array.matrix(N,1<<K,-1);
    var cost = Array.matrix(K,N,0);
    for (var i = 0; i < K; i++) {
        cost[i][0] = mat[i][0];
        for (var j = 1; j < N; j++) {
            cost[i][j] = cost[i][j-1] + mat[i][j];
        }
    }
    //console.log();
    
    console.log(solve(cost, DP, 0, 0, K, N));
} 

function solve (mat, DP, pos, mask, K, N) {
    if (pos >= N) {
        return 0;
    }
    if (DP[pos][mask]!=-1) {
        return DP[pos][mask];
    }
    var min = 1e9;
    for (var i = 0; i < K; i++) {
        if ((mask & (1<<i))==0) {
            for (var j = pos; j < N; j++) {
                min = Math.min(min, mat[i][j]- (pos>0?mat[i][pos-1]:0)+solve(mat , DP, j+1, mask | (1<<i), K, N));
            }
        }
    }
    return (DP[pos][mask] = min);
    
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

The Blacklist Python Solution

#!/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)))