HackerRank A Super Hero Problem Solution Yashwant Parihar, August 4, 2023August 1, 2024 In this Post, we will solve HackerRank A Super Hero Problem Solution. Mastermind is crazy about Action Games. He just bought a new one and got down to play it. Mastermind 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, Mastermind has to cross N levels. At each level of the game, Mastermind has to face M enemies. Each enemy has its associated power P and some number of bullets B. To knock down an enemy, Mastermind needs to shoot him with one or multiple bullets whose collective count is equal to the power of the enemy. If Mastermind manages to knock down any one enemy at a level, the rest of them run away and the level is cleared.Here comes the challenging part of the game.Mastermind acquires all the bullets of an enemy once he has knocked him down. Mastermind can use the bullets acquired after killing an enemy at ith level only till the(i+1)th level.However, the bullets Mastermind carried before the start of the game can be taken forward and can be used to kill more enemies.Now, Mastermind has to guess the minimum number of bullets he must have before the start of the game so that he clears all the N levels successfully.NOTE Bullets carried before the start of the game can be used to kill an enemy at any level. One bullet decreases the power of an enemy by 1 Unit. For better understanding of the problem look at the sample testcases. Input FormatFirst line of input contains a single integer T denoting the number of test cases.First line of each test case contains two space separated integers N and M denoting the number of levels and number of enemies at each level respectively.Each of next N lines of a test case contain M space separated integers, where jth integer in the jth line denotes the power P of jth enemy on the jth level.Each of the next N lines of a test case contains M space separated integers, where jth integer in the jth line denotes the number of bullets Bjth enemy of jth level has. Output Format For each test case, print the required answer. Sample Input 2 3 3 3 2 1 1 2 3 3 2 1 1 2 3 3 2 1 1 2 3 3 3 3 2 5 8 9 1 4 7 6 1 1 1 1 1 1 1 1 1 Sample Output 1 5 ExplanationFor the First test case, Mastermind kills the enemy in the following order: Mastermind kills the 3rd enemy at the 1st level, takes all his bullets and moves to the next level. Mastermind kills the 1st enemy at the 2nd level, takes all his bullets and moves to the next level. Mastermind kills the 1st enemy at the 3rd level, takes all his bullets and moves to the next level.So this way Mastermind can successfully finish this game with only 1 bullet in hand before the start of the game.For the second test case, Mastermind kills the enemy in the following order: Mastermind kills the 2nd enemy at the 1st level, takes all his bullets and moves to the next level. Mastermind kills the 3rd enemy at the 2nd level, takes all his bullets and moves to the next level. Mastermind kills the 1st enemy at the 3rd level, takes all his bullets and moves to the next level. So this way Mastermind can successfully finish this game with only 5 bullet in hand before the start of the game.NOTE:There can be more than one way of getting the optimal answer but that does not matter in our case, because we need to answer the minimum number of bullets required. HackerRank A Super Hero Problem Solution A Super Hero C Solution #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; } A Super Hero C++ Solution #include<bits/stdc++.h> #define lf double #define ll long long #define ull unsigned ll #define ii pair<int,int> #define il pair<int,ll> #define iii pair<int,ii> #define iiii pair<ii,ii> #define pll pair<ll,ll> #define ld long int #define heap priority_queue #define mp make_pair #define st first #define nd second #define pb push_back #define pp pop_back #define all(x) x.begin(),x.end() #define len(x) strlen(x) #define sz(x) (int) x.size() #define orta ((bas+son)/2) #define min3(x,y,z) min(min(x,y),z) #define max3(x,y,z) max(max(x,y),z) #define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" " #define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar() #define MOD 1000000007 #define inf 1000000009 #define N 105 #define LOG 18 #define K 1005 #define M 1005 #define EPS 0.0000001 using namespace std; int t,n,m,x,ans; int dp[2][M]; vector<int> b[N],p[N]; void solve() { fill(dp[0],dp[0]+M,inf); fill(dp[1],dp[1]+M,inf); dp[0][0]=0; for(int i=0;i<n;i++) { for(int j=0;j<M;j++) { if(dp[0][j]==inf) continue ; for(int k=0;k<m;k++) { dp[1][b[i+1][k]]=min(dp[1][b[i+1][k]],dp[0][j]+max(p[i+1][k]-j,0)); } } for(int j=0;j<M;j++) { dp[0][j]=dp[1][j]; dp[1][j]=inf; } } for(int i=0;i<M;i++) { ans=min(ans,dp[0][i]); } printf("%d\n",ans); } int main() { scanf("%d",&t); while(t--) { ans=inf; scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) { p[i].clear(); for(int j=1;j<=m;j++) { scanf("%d",&x); p[i].pb(x); } } for(int i=1;i<=n;i++) { b[i].clear(); for(int j=1;j<=m;j++) { scanf("%d",&x); b[i].pb(x); } } solve(); } } A Super Hero C Sharp Solution using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { private class Fenwick { private const int CHUNK_SIZE = 32; private class Node { public readonly int Min; public readonly int Max; public Node(int min, int max) { Min = min; Max = max; } public Node Left; public Node Right; public bool IsLeaf => Left == null && Right == null; public int Delta; public int Value; } private readonly Node _root; public readonly int[] Raw; public Fenwick(int min, int max, int[] input) { _root = new Node(min, max); Raw = input; Build(_root); } private void Build(Node node) { int chunk = node.Max - node.Min + 1; int chunksCount = Convert.ToInt32(Math.Ceiling((double)chunk / CHUNK_SIZE)); if (chunksCount <= 1) { checked { int minDelta = int.MaxValue; int minValue = int.MaxValue; for (int i = node.Min; i <= node.Max; i++) { minDelta = Math.Min(minDelta, Raw[i] - i); minValue = Math.Min(minValue, Raw[i]); } node.Value = minValue; node.Delta = minDelta; } return; } int leftChunksCount = chunksCount / 2; node.Left = new Node(node.Min, node.Min + leftChunksCount * CHUNK_SIZE - 1); node.Right = new Node(node.Min + leftChunksCount * CHUNK_SIZE, node.Max); Build(node.Left); Build(node.Right); node.Delta = Math.Min(node.Left.Delta, node.Right.Delta); node.Value = Math.Min(node.Left.Value, node.Right.Value); } private void Update(Node node, int i, int val) { if (node == null || i < node.Min || i > node.Max) { return; } if (!node.IsLeaf) { Update(node.Left, i, val); Update(node.Right, i, val); node.Delta = Math.Min(node.Left.Delta, node.Right.Delta); node.Value = Math.Min(node.Left.Value, node.Right.Value); } else { int minDelta = int.MaxValue; int minValue = int.MaxValue; Raw[i] = val; for (int j = node.Min; j <= node.Max; j++) { minDelta = Math.Min(minDelta, Raw[j] - j); minValue = Math.Min(minValue, Raw[j]); } node.Value = minValue; node.Delta = minDelta; } } public void Update(int i, int val) { Update(_root, i, val); } private void Query(Node node, int from, int to, out int delta, out int val) { if (node == null || from > node.Max || to < node.Min) { delta = int.MaxValue; val = int.MaxValue; return; } if (node.Min == from && node.Max == to) { delta = node.Delta; val = node.Value; return; } if (node.IsLeaf) { int start = Math.Max(node.Min, from); int end = Math.Min(node.Max, to); delta = int.MaxValue; val = int.MaxValue; for (int j = start; j <= end; j++) { delta = Math.Min(delta, Raw[j] - j); val = Math.Min(val, Raw[j]); } return; } Query(node.Left, Math.Max(node.Left.Min, from), Math.Min(node.Left.Max, to), out var d1, out var v1); Query(node.Right, Math.Max(node.Right.Min, from), Math.Min(node.Right.Max, to), out var d2, out var v2); delta = Math.Min(d1, d2); val = Math.Min(v1, v2); } public void Query(int from, int to, out int delta, out int val) { Query(_root, from, to, out delta, out val); } } static int superHero(int[][] power, int[][] bullets) { checked { int n = power.Length; int m = power[0].Length; Fenwick back = new Fenwick(0, 1000, Enumerable.Repeat(int.MaxValue, 1001).ToArray()); Fenwick front = new Fenwick(0, 1000, Enumerable.Repeat(int.MaxValue, 1001).ToArray()); for (int i = 0; i < m; i++) { back.Update(power[n - 1][i],power[n - 1][i]); } for (int i = n - 2; i >= 0; i--) { for (int j = 0; j <= 1000; j++) { front.Update(j, int.MaxValue); } for (int j = 0; j < m; j++) { var p = power[i][j]; var b = bullets[i][j]; var min = int.MaxValue; back.Query(0, b, out var d, out _); long cand1 = (long)p + Math.Max(0, d); if (cand1 <= int.MaxValue) { min = Math.Min(min, (int)cand1); } if (b != 1000) { back.Query(b + 1, 1000, out _, out var next); long cand2 = (long) p + Math.Max(0, next - b); if (cand2 <= int.MaxValue) { min = Math.Min(min, (int)cand2); } } front.Update(p, Math.Min(min, front.Raw[p])); } var tmp = front; front = back; back = tmp; } back.Query(0, 1000, out _, out var res); return res; } } static void Main(string[] args) { TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true); int t = Convert.ToInt32(Console.ReadLine()); for (int tItr = 0; tItr < t; tItr++) { string[] nm = Console.ReadLine().Split(' '); int n = Convert.ToInt32(nm[0]); int m = Convert.ToInt32(nm[1]); int[][] power = new int[n][]; for (int powerRowItr = 0; powerRowItr < n; powerRowItr++) { power[powerRowItr] = Array.ConvertAll(Console.ReadLine().Split(' '), powerTemp => Convert.ToInt32(powerTemp)); } int[][] bullets = new int[n][]; for (int bulletsRowItr = 0; bulletsRowItr < n; bulletsRowItr++) { bullets[bulletsRowItr] = Array.ConvertAll(Console.ReadLine().Split(' '), bulletsTemp => Convert.ToInt32(bulletsTemp)); } int result = superHero(power, bullets); textWriter.WriteLine(result); } textWriter.Flush(); textWriter.Close(); } } A Super Hero Java Solution 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(); } } A Super Hero Python Solution #!/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() c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython