HackerRank A Super Hero problem solution

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("%ldn", result);
        
    }
    

    return 0;
}