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