In this HackerRank A Super Hero problem solution Ma5termind is crazy about Action Games. He just bought a new one and got down to play it. Ma5termind usually finishes all the levels of a game very fast. But, This time however he got stuck at the very first level of this new game. Can you help him play this game?
To finish the game, Ma5termind has to cross N levels. At each level of the game, Ma5termind has to face M enemies. Each enemy has its associated power P and some number of bullets B. To knock down an enemy, Ma5termind needs to shoot him with one or multiple bullets whose collective count is equal to the power of the enemy. If Ma5termind manages to knock down anyone enemy at a level, the rest of them run away and the level is cleared.
Problem solution in Python.
#!/bin/python3
import os
import sys
#
# Complete the superHero function below.
#
def superHero(power, bullets):
paths_so_far = {0: (0, 0)}
for power_level, bullets_level in (zip(reversed(power), reversed(bullets))):
min_bullets = None
min_enemy = None
new_paths = {}
for enemy_pwr, enemy_blts in zip(power_level, bullets_level):
for total_bullets_next_lvl, carry_bullets_next_lvl in paths_so_far.values():
extra_bullets_to_carry = 0
bullets_required = enemy_pwr + carry_bullets_next_lvl
if (total_bullets_next_lvl - carry_bullets_next_lvl) > enemy_blts:
extra_bullets_to_carry = (total_bullets_next_lvl - carry_bullets_next_lvl) - enemy_blts
bullets_required += extra_bullets_to_carry
new_carry_bullets = carry_bullets_next_lvl + extra_bullets_to_carry
new_path = [bullets_required, new_carry_bullets]
if new_carry_bullets not in new_paths:
new_paths[new_carry_bullets] = new_path
else:
if bullets_required < new_paths[new_carry_bullets][0]:
new_paths[new_carry_bullets] = new_path
new_paths2 = {}
for idx, key in enumerate(sorted(new_paths.keys())):
if idx == 0:
new_paths2[key] = new_paths[key]
else:
min_total = min(total for total, _ in new_paths2.values())
if new_paths[key][0] < min_total:
new_paths2[key] = new_paths[key]
paths_so_far = new_paths2
return min(total_bullets for total_bullets, _ in paths_so_far.values())
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
t = int(input())
for t_itr in range(t):
nm = input().split()
n = int(nm[0])
m = int(nm[1])
power = []
for _ in range(n):
power.append(list(map(int, input().rstrip().split())))
bullets = []
for _ in range(n):
bullets.append(list(map(int, input().rstrip().split())))
result = superHero(power, bullets)
fptr.write(str(result) + '\n')
fptr.close()
Problem solution in Java.
import java.io.*;
import java.util.*;
public class Solution {
// TODO A Super Hero
static final int INF = Integer.MAX_VALUE/3;
static int[] dp0 = new int[1001];
static int[] dp1 = new int[1001];
static int minElement(int[] arr) {
int result = arr[0];
for (int x: arr) {
result = Math.min(result, x);
}
return result;
}
static int superHero(int[][] power, int[][] bullets) {
Arrays.fill(dp0, INF);
dp0[0] = 0;
for (int i = 0; i < power.length; i++) {
Arrays.fill(dp1, INF);
for (int j = 0; j < power[0].length; j++) {
for (int k = 0; k <= 1000; k++) {
if (dp0[k] >= INF) {
continue;
}
int nevoie = Math.max(0, power[i][j] - k);
if (dp1[bullets[i][j]] > dp0[k] + nevoie) {
dp1[bullets[i][j]] = dp0[k] + nevoie;
}
}
}
int[] tmp = dp0;
dp0 = dp1;
dp1 = tmp;
}
return minElement(dp0);
}
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 t = Integer.parseInt(st.nextToken());
for (int tItr = 0; tItr < t; tItr++) {
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[][] power = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
int item = Integer.parseInt(st.nextToken());
power[i][j] = item;
}
}
int[][] bullets = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
int item = Integer.parseInt(st.nextToken());
bullets[i][j] = item;
}
}
int result = superHero(power, bullets);
bw.write(String.valueOf(result));
bw.newLine();
}
bw.close();
br.close();
}
}
Problem solution in C++.
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <ctime>
using namespace std;
int bullets[101][1001];
int need[101][1001];
int n,m;
int main()
{
int t;
cin >> t;
for(int tst=0;tst<t;tst++)
{
cin >> n >> m;
memset(bullets, 228, sizeof(bullets));
memset(need, 228/2, sizeof(need));
vector<vector<int> > p(n);
for(int i=0;i<n;i++)
{
p[i].resize(m);
for(int j=0;j<m;j++)
{
cin >> p[i][j];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
int b;
cin >> b;
if (bullets[i][p[i][j]] < b)
{
bullets[i][p[i][j]] = b;
}
}
}
for(int j=0;j<=1000;j++)
{
if(bullets[0][j] >= 0)
need[0][j] = j;
}
for(int i=1;i<n;i++)
{
for(int j=0;j<=1000;j++)
{
if (bullets[i][j] >= 0)
{
for(int prev = 0; prev <= 1000; prev++)
{
if(bullets[i-1][prev] >= 0)
{
need[i][j] = min(need[i][j], need[i-1][prev] + max(0, j - bullets[i-1][prev]));
}
}
}
}
}
int ans = 1000000000;
for(int j=0;j<=1000;j++)
{
ans = min(ans, need[n-1][j]);
}
cout << ans << "\n";
}
return 0;
}
Problem solution in C.
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define N_MAX 100
#define M_MAX 500000
typedef struct enem {
int P;
int B;
} Enem;
typedef struct StateInfoArray {
int next_level_ammu[1000 * N_MAX];
int hash_table[1000 * N_MAX];
int index_array[1000 * N_MAX];
long idx_arr_size;
} StateInfoArray;
Enem enem[N_MAX][M_MAX];
void do_heapyfy_enem(int lvl, int idx, int size) {
int left_child = 2 * idx + 1;
int right_child = 2 * idx + 2;
int max_idx = idx;
if(left_child < size && enem[lvl][left_child].P > enem[lvl][max_idx].P)
max_idx = left_child;
if(right_child < size && enem[lvl][right_child].P > enem[lvl][max_idx].P)
max_idx = right_child;
if(max_idx != idx) {
Enem e = enem[lvl][max_idx];
enem[lvl][max_idx] = enem[lvl][idx];
enem[lvl][idx] = e;
do_heapyfy_enem(lvl, max_idx, size);
}
}
void make_heap_enem(int lvl, int size) {
int i;
for(i = size/2 - 1; i >= 0; --i) {
do_heapyfy_enem(lvl, i, size);
}
}
void heap_sort_enem(int lvl, int size) {
make_heap_enem(lvl, size);
int i;
for(i = size-1; i >= 0; --i) {
Enem e = enem[lvl][0];
enem[lvl][0] = enem[lvl][i];
enem[lvl][i] = e;
do_heapyfy_enem(lvl, 0, i);
}
}
void do_heapyfy_index(int *array, int idx, int size) {
int left_child = 2 * idx + 1;
int right_child = 2 * idx + 2;
int max_idx = idx;
if(left_child < size && array[left_child] > array[max_idx])
max_idx = left_child;
if(right_child < size && array[right_child] > array[max_idx])
max_idx = right_child;
if(max_idx != idx) {
int index = array[max_idx];
array[max_idx] = array[idx];
array[idx] = index;
do_heapyfy_index(array, max_idx, size);
}
}
void make_heap_index(int *array, int size) {
int i;
for(i = size/2 - 1; i >= 0; --i) {
do_heapyfy_index(array, i, size);
}
}
void heap_sort_index(int *array, int size) {
make_heap_index(array, size);
int i;
for(i = size-1; i >= 0; --i) {
int index = array[0];
array[0] = array[i];
array[i] = index;
do_heapyfy_index(array, 0, i);
}
}
long solve(int N, int M) {
StateInfoArray sia1, sia2;
int i;
for(i = 0; i < 1000 * N_MAX; ++i) {
sia1.hash_table[i] = 0;
sia2.hash_table[i] = 0;
}
sia1.idx_arr_size = 0;
sia2.idx_arr_size = 0;
StateInfoArray *prev_states;
StateInfoArray *curr_states;
int n,m;
int max_b = 0;
curr_states = &sia1;
for(m = 0; m < M; ++m) {
int P = enem[0][m].P;
int B = enem[0][m].B;
if(max_b < B)
max_b = B;
else
continue;
if(curr_states->hash_table[P] == 0) {
curr_states->hash_table[P] = 1;
curr_states->next_level_ammu[P] = B;
curr_states->index_array[curr_states->idx_arr_size++] = P;
}
else {
if(curr_states->next_level_ammu[P] < B) {
curr_states->next_level_ammu[P] = B;
}
}
}
for(n = 1; n < N; ++n) {
prev_states = curr_states;
curr_states = &sia1;
if(prev_states == curr_states)
curr_states = &sia2;
int j;
for(j = 0; j < 1000 * N_MAX; ++j) {
curr_states->hash_table[j] = 0;
}
curr_states->idx_arr_size = 0;
heap_sort_index(prev_states->index_array, prev_states->idx_arr_size);
int max_next_level_ammu = 0;
int i;
for(i = 0; i < prev_states->idx_arr_size; ++i) {
if(max_next_level_ammu < prev_states->next_level_ammu[prev_states->index_array[i]])
max_next_level_ammu = prev_states->next_level_ammu[prev_states->index_array[i]];
else
continue;
int max_b = 0;
for(m = 0; m < M; ++m) {
int next_level_ammu = enem[n][m].B;
if(max_b < next_level_ammu)
max_b = next_level_ammu;
else
continue;
int new_ammu = enem[n][m].P-prev_states->next_level_ammu[prev_states->index_array[i]];
if(new_ammu < 0)
new_ammu = 0;
int total_ammu = prev_states->index_array[i] + new_ammu;
if(curr_states->hash_table[total_ammu] == 0) {
curr_states->hash_table[total_ammu] = 1;
curr_states->next_level_ammu[total_ammu] = next_level_ammu;
curr_states->index_array[curr_states->idx_arr_size++] = total_ammu;
}
else {
if(curr_states->next_level_ammu[total_ammu] < next_level_ammu)
curr_states->next_level_ammu[total_ammu] = next_level_ammu;
}
}
}
}
long min = curr_states->index_array[0];
for(i = 1; i < curr_states->idx_arr_size; ++i) {
if(curr_states->index_array[i] < min)
min = curr_states->index_array[i];
}
return min;
}
int main() {
int T;
scanf("%d", &T);
int test_case;
for(test_case = 0; test_case < T; ++test_case) {
int N, M;
scanf("%d", &N);
scanf("%d", &M);
int m, n;
for(n = 0; n < N; ++n) {
for(m = 0; m < M; ++m) {
scanf("%d", &enem[n][m].P);
}
}
for(n = 0; n < N; ++n) {
for(m = 0; m < M; ++m) {
scanf("%d", &enem[n][m].B);
}
}
for(n = 0; n < N; ++n) {
heap_sort_enem(n, M);
}
long result = solve(N,M);
printf("%ld\n", result);
}
return 0;
}
0 Comments