# HackerRank Superman Celebrates Diwali Solution

In this post, we will solve HackerRank Superman Celebrates Diwali Problem Solution.

Superman has been invited to India to celebrate Diwali. Unfortunately, on his arrival he learns that he has been invited mainly to help rescue people from a fire accident that has happened in a posh residential locale of New Delhi, where rescue is proving to be especially difficult. As he reaches the place of the fire, before him there are N buildings, each of the same height H, which are on fire. Since it is Diwali, some floors of the buildings are empty as the occupants have gone elsewhere for celebrations. In his hurry to start the rescue Superman reaches the top of the building, but realizes that his jumping power is depleted and restricted due to change in his geographical setting. He soon understands the restrictions of his jumping power, and they are as follows:

- He can use the jumping power any number of times until he reaches the bottom floor, which means he can use the jumping power only until before he reaches the bottom (Ground floor), which means, once he reaches the bottom floor, he cannot move to the top floor again and try to save people. (In one single drop from the top to bottom)
- While switching buildings, he loses height I while jumping.

The second restriction is explained below with an example.

Assume I = 2. Now Superman is in the 2nd building 5th floor (B = 2, F = 5). If he wants to switch to the fifth building (B5), he will lose height (I = 2), which means he will be at floor 3 at building 5 (B = 5. F = 3). He can jump freely from the current floor to the floor below on the same building. That is, suppose if he is at (B = 5, F = 4), he can go to (B 5, F = 3) without any restrictions. He cannot skip a floor while jumping in the same building. He can go to the floor below the current floor of the same building or use his jumping power, switch building, and lose height I.

Given the information about the occupied floors in each of the N buildings, help Superman to determine the maximum number of people he can save in one single drop from the top to the bottom floor with the given restrictions.**Input Format**

Input starts with three values: the number of buildings N. the height of the buildings H. and the height Superman will lose when he switches buildings I.

These are followed by N lines. Each th line starts with a non negative integer u indicating how many people are in the ith building. Each of the following u integers indicates that a person is at height u in the ith buiding. Each of the following u integers are given and repetitions are allowed which means there can be more than one person in a floor. * Indicates building number and j indicates floor number. Building number will not be given; since N lines follow the first line, you can assume that the ith line indicates the ¿th building’s specifications.

**Output Format**

Output the maximum number of people Superman can save.

**Sample Input**

```
4 15 2
5 1 1 1 4 10
8 9 5 7 7 3 9 8 8
5 9 5 6 4 3
0
```

**Sample Output**

`12`

**Explanation**

Input starts with N = 4 H = 15. I = 2.

N lines follow. Each line describes building i.

Each line begins with u, which denotes the number of persons in a particular building. followed by floor number, where each person resides. Floor number can repeat as any

number of people can reside on a particular floor.

I’ve attached a figure here to explain the sample test case.

You can verify the first building’s specifications with the figure.

u = 5 (Total number of persons in the first building), followed by 1 11 4 10(Floor numbers).

1st floor = 3 persons.

4th floor = 1 person.

10th floor = 1 person.

Similarly, the specifications for the other three buildings follow.

The connected line shows the path which Superman can use to save the maximum number of people. In this case, that number is 12.

You can also note in the figure that when he switches from Building 2 to Building 3, he loses height I (I = 2). Similarly, when he switches from Building 3 to Building 1,the same height loss happens as mentioned in the problem statement

## Superman Celebrates Diwali C Solution

```
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
static int n,h,i,a[2400][2400],j,k,x,y,z;
scanf("%d%d%d",&n,&h,&z);
for(i=1;i<=n;i++)
{
scanf("%d",&x);
for(j=0;j<x;j++)
{
scanf("%d",&y);
a[y][i]++;
}
}
for(i=h;i>=1;i--)
{
for(j=1;j<=n;j++)
{
if(a[i+1][j]>a[i+z][0])
{
a[i][j]+=a[i+1][j];
}
else
a[i][j]+=a[i+z][0];
if(a[i][j]>a[i][0])
a[i][0]=a[i][j];
}
}
printf("%d",a[1][0]);
return 0;
}
```

## Superman Celebrates Diwali C++ Solution

```
#include<iostream>
using namespace std;
const int MAXN = 1900, MAXH = 1900;
int f[MAXN][MAXH + 1], cnt[MAXN][MAXH + 1], g[MAXH + 1];
int main()
{
int n, h, hl;
cin >> n >> h >> hl;
for (int i = 0; i < n; i++)
{
int num;
cin >> num;
for (int j = 0; j < num; j++)
{
int tmp;
cin >> tmp;
cnt[i][tmp]++;
}
}
for (int i = 0; i < n; i++)
{
f[i][h] = cnt[i][h];
if (f[i][h] > g[h])
g[h] = f[i][h];
}
for (int j = h - 1; j >= 0; j--)
{
for (int i = 0; i < n; i++)
{
int tmp = 0;
if (j + hl <= h)
{
if (g[j + hl] > tmp) tmp = g[j + hl];
}
if (f[i][j + 1] > tmp) tmp = f[i][j + 1];
f[i][j] = tmp + cnt[i][j];
if (f[i][j] > g[j])
g[j] = f[i][j];
}
}
int ans = 0;
for (int i = 0; i < n; i++)
if (f[i][0] > ans)
ans = f[i][0];
cout << ans << endl;
return 0;
}
```

## Superman Celebrates Diwali C Sharp Solution

```
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
class Solution {
static void FillSaved(int[] thisFloor, int[] savedBelow, int[] canSave, int changeBuilding)
{
for (int i = 0; i < thisFloor.Length; i++)
{
canSave[i] = Math.Max(savedBelow[i], changeBuilding) + thisFloor[i];
}
canSave[thisFloor.Length] = canSave.Max();
}
static void Main(String[] args) {
string[] line = Console.ReadLine().Trim().Split(' ');
int[] a = Array.ConvertAll(line, int.Parse);
int N = a[0];
int H = a[1];
int I = a[2];
int[][] building = new int[H][];
for (int h = 0; h < H; h++)
{
building[h] = new int[N];
}
// Fill building with people
for (int n = 0; n < N; n++)
{
line = Console.ReadLine().Trim().Split(' ');
a = Array.ConvertAll(line, int.Parse);
for (int x = 1; x < a.Length; x++)
{
building[a[x] - 1][n]++;
}
}
// count the number of people that can be saved starting from the first floor
int[][] saved = new int[H][];
for (int h = 0; h < H; h++)
{
saved[h] = new int[N + 1];
}
// First floor
for (int n = 0; n < N; n++)
{
saved[0][n] = building[0][n];
}
saved[0][N] = building[0].Max();
// subsequent floors
for(int h = 1; h < H; h++)
{
FillSaved(building[h], saved[h - 1], saved[h], (h - I >= 0) ? saved[h - I][N]: 0);
}
Console.WriteLine(saved[H - 1][N]);
}
}
```

## Superman Celebrates Diwali Java Solution

```
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class SupermanCelebratesDiwali {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
int n = ni(), H = ni(), dr = ni();
int[][] al = new int[H+1][n];
for(int i = 0;i < n;i++){
int K = ni();
for(int j = 0;j < K;j++){
al[ni()][i]++;
}
}
int[][] dp = new int[H+2][n];
for(int h = H+1;h >= 1;h--){
int rowmax = 0;
for(int i = 0;i < n;i++){
dp[h-1][i] = Math.max(dp[h-1][i], dp[h][i] + al[h-1][i]);
rowmax = Math.max(rowmax, dp[h][i]);
}
if(h-dr >= 0){
for(int i = 0;i < n;i++){
dp[h-dr][i] = Math.max(dp[h-dr][i], rowmax + al[h-dr][i]);
}
}
}
int ret = 0;
for(int i = 0;i < n;i++){
ret = Math.max(ret, dp[0][i]);
}
out.println(ret);
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
```

## Superman Celebrates Diwali JavaScript Solution

```
/* Woot! First crude draft of program earned 70.24 points (21 out of 23).
* Cases 16 and 18 report getting the wrong answer, which feels like I've
* overlooked some edge case. Unless maybe the program is actually running
* out of time or memory, and it's being reported wrong. There's little bits
* of weirdness that make me wonder if this is an old challenge. The language
* selection is smaller than usual, most templates have a comment and no code,
* and console.debug gets mixed with the answer on console.log.
*
* Okay I checked the discussions, tuning out the code people posted, and
* looking for references to specific test cases. One person mentions that
* the same program on C++14 can pass 16 and 18, while on C++ it can't. So
* that suggests the problem is time or memory.
*
* OH! I've just thought of a problem in my program! The maximum number of
* people that can be rescued would be 1900*1900! For example if all 1900
* people in building X are on floor X, and if I=1, then Superman can get
* the full load of people from all 1900 buildings. And 3_610_000 requires
* 22 bits to represent. Sooooo that won't fit in Uint16! I think it'll
* just silently overflow. Which would very cleanly explain why we got a
* "wrong answer" instead of time or memory errors. Premature optimization
* fail! (Also forgetting to consider this when I mentially switched from
* using building_floor_people to represent just the input, to also using
* it as the memoization record.) Okay, I'm going to change that 16 to a 32,
* and try submitting this again!
*/
var DEBUG = false;
function processData(input) {
//Enter your code here
//let input_line_1 = /^(\d)+ (\d)+ (\d)+$/;
//let lines = [""]; // faux type hinting?
let lines = input.split("\n");
let split_line = lines.shift().split(" ");
let theN = parseInt(split_line[0]);
let theH = parseInt(split_line[1]);
let theI = parseInt(split_line[2]);
let building_floor_people = new Array(theN);
for (let b = 0; b < theN; b++) {
let this_building = new Uint32Array(theH);
building_floor_people[b] = this_building;
split_line = lines[b].split(" ");
let people_count = parseInt(split_line.shift());
for (let p = 0; p < people_count; p++) {
let where = parseInt(split_line[p]);
this_building[where-1]++;
}
}
if (DEBUG) {
console.debug(building_floor_people);
for (let f = 0; f < theH; f++) {
console.debug(`${f} -> ${getBestsForFloor(building_floor_people, f)}`);
}
}
for (let f = 1; f < theH; f++) {
let bests = getBestsForFloor(building_floor_people, f-theI);
for (let b = 0; b < theN; b++) {
let here = bests[0];
if (b === bests[1]) {
here = bests[2];
}
here = Math.max(here, building_floor_people[b][f-1]);
building_floor_people[b][f] += here;
}
}
if (DEBUG) {
console.debug(building_floor_people);
}
let the_very_best = getBestsForFloor(building_floor_people, theH-1)[0];
console.log(the_very_best);
}
/* Takes the 2D building_floor_people data, and an integer floor number. (0 index)
* Returns an array of three values:
* - The highest people count on that floor.
* - The building number of where the highest was found.
* - The second-highest people count on that floor.
*
* Notes:
* - If the floor number is negative, return [0, 0, 0]. No-one to rescue underground.
* - If there is only a single building, the second-highest will just be zero.
* - If multiple buildings are tied for highest, then second-highest will equal highest.
*/
function getBestsForFloor(bfp, floor) {
let output = [0, 0, 0];
if (floor < 0) {
return output;
} else if (bfp[0].length <= floor) {
console.error("Not a valid floor number!");
}
for (let b = 0; b < bfp.length; b++) {
let people_here = bfp[b][floor];
if (people_here >= output[0]) {
output[2] = output[0];
output[1] = b;
output[0] = people_here;
} else if (people_here >= output[2]) {
output[2] = people_here;
}
}
return output;
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
var _input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});
```

## Superman Celebrates Diwali Python Solution

```
l=input().split(' ')
buildings=int(l[0])
floors=int(l[1])
jump=int(l[2])
data=[]
for i in range(buildings):
data.append(input().split(' ')[1:])
mat=[[0 for f in range(floors+1)] for b in range(buildings)]
for l in range(len(data)):
d={}
for it in data[l]:
if not it in d.keys():
d[it]=1
else:
d[it]+=1
for k in d.keys():
mat[l][int(k)]=d[k]
max_per_floor=[0 for i in range(len(mat[0]))]
for f in range(1,len(mat[0])):
for b in range(len(mat)):
if f<jump:
mat[b][f]=mat[b][f]+mat[b][f-1]
else:
mat[b][f]=max(mat[b][f]+mat[b][f-1],mat[b][f]+max_per_floor[f-jump])
list_floors=[]
for b in range(len(mat)):
list_floors.append(mat[b][f])
max_per_floor[f]=max(list_floors)
print(max_per_floor[-1])
```