Here is my solution in java, javascript, python, C, C++, Csharp HackerRank The Blacklist Problem Solution

// C++ solution for those who stuck in DP

include

define ll long long

define ld long double

define vec vector

using namespace std; ll n, k; ll dp[20][1024]; ll fun(ll start, vec> &cost, ll avail) { if(start == n) { return 0; } if(dp[start][avail] != -1) { return dp[start][avail]; } ll ans = -1; for(ll end = start; end < n; end++) { for(ll j = 0; j < k; j++) { if((1ll << j) & avail) { ll tmp = fun(end+1, cost, avail^(1ll<= 0) { if(ans == -1) { ans = cost[j][end] - (start > 0 ? cost[j][start-1] : 0) + tmp; } else { ans = min(ans, cost[j][end] - (start > 0 ? cost[j][start-1] : 0) + tmp); } } } } } return dp[start][avail] = ans; } int main() { cin >> n >> k; vec> a(k, vec(n)); for(ll i = 0; i < k; i++) { cin >> a[i][0]; for(ll j = 1; j < n; j++) { cin >> a[i][j]; a[i][j] += a[i][j-1]; } } memset(dp, -1, sizeof(dp)); cout << fun(0, a, (1ll<

Any ideas how this test case could be 7?

3 2
4 3 4
0 4 3

Python 2 Solution

from __future__ import print_function

import os
import sys

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

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

for i in xrange(K):
    prices = map(int, raw_input().split())
    prices.reverse()
    cost.append(prices)

dp = []
for i in xrange(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 xrange(0, N):
    for mask in xrange(0, MASK):
        for hitman in xrange(0, K):
            if hitman_available(hitman, mask):
                mask_after = use_hitman(hitman, mask)
                for num_to_kill in xrange(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 xrange(MASK)))

Seems to be similar to a scheduling problem, which I have no experience with. How do you compare the weights between each mercenary while keeping in mind that you cannot alternate back to a previous mercenary?

I have a hunch that this would be vaguely similar to running a modified Dijkstra's algorthm on an singlely linked list that is absurdly interconnected with K starting nodes and K ending nodes.

So far, I've only made a basic solution that always chooses the lowest option available, but that does not take into account that a mercenary may have a better streak of low cost options latter on.