The Blacklist
The Blacklist
+ 0 comments Here is The blacklist problem solution in Python Java C++ and C programming - https://programs.programmingoneonone.com/2021/07/hackerrank-the-blacklist-problem-solution.html
+ 0 comments // 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<
+ 0 comments Any ideas how this test case could be 7?
3 2
4 3 4
0 4 3
+ 0 comments 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)))
+ 0 comments 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.
Sort 16 Discussions, By:
Please Login in order to post a comment