INFERNO Editorial

editorial
, ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Jeevan Jyot Singh
Tester: Jakub Safin, Satyam
Editorialist: Pratiyush Mishra

DIFFICULTY:

1162

PREREQUISITES:

None

PROBLEM:

Ved started playing a new mobile game called Fighting Clans. An army of N enemies is approaching his base. The i^{th} enemy has H_i health points. An enemy gets killed if his health points become 0.
Ved defends his base using a weapon named Inferno. He can set the Inferno to one of the following two modes:

  • Single-Target Mode: In one second, the Inferno can target exactly one living enemy and cause damage of at most X health points.
  • Multi-Target Mode: In one second, the Inferno can target all living enemies and cause damage of 1 health point to each of them.

Find the minimum time required to kill all the enemies.

Note: Ved is not allowed to change the mode of the weapon once it is set initially.

EXPLANATION:

Let us calculate answer for both modes:

  • Single Target Mode: Here we would loop through each enemy and calculate the time required to kill him. Let us assume a function f(i) that tells the time taken to kill the i_{th} enemy then,
f(i) = \lceil \frac{H_i}{X} \rceil
single\_mode\_answer = \sum_{i=1}^{i=n} f(i)
  • Multi Target Mode: Here the answer would be the maximum H_i among all the enemies since each second it is reducing the health of all enemies by 1. Thus,
multi\_mode\_answer = max(H_i), 1 \leq i \leq n

Once we calculate these two, our final answer would be:

answer = min(single\_mode\_answer, multi\_mode\_answer)

TIME COMPLEXITY:

O(N), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

2

Full clashing baazi

3

Could someone point out what is incorrect in my solution. It passed nearly 5 testcases.

void solve()
{
	int t;
	cin >> t;
	while(t--) {
		int n, x;
		read(n, x);
		int h[n];
		int multi = INT_MIN;
		rep(0, n) {
			cin >> h[i];
			multi = max(multi, h[i]);
		}

		int single = 0;
		rep(0, n) {
			if(h[i] > x) {
				single += 1 + h[i]/x;
			} 
			else
				single++;
		}

		cout << min(single, multi) << "\n";
	}
}
4

You have done mistake in loop for calculating single_shot value, if the h[i] is completely divisible
by x then you don’t need to add 1, it’s simply h[i]/x, else you can add one if it is not divisible.
Here you can refer my code to understand better :

void solve(){
    int n,x;
    cin>>n>>x;
    int a[n],multi_mode=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        multi_mode=max(multi_mode,a[i]);
    }
    int one_mode=0;
    for(int i=0;i<n;i++){
        if(a[i]<=x)
            one_mode++;
        else{
            if(a[i]%x==0)
                one_mode+=a[i]/x;
            else
                one_mode+=(a[i]/x)+1;
        }
    }
    cout<<min(multi_mode,one_mode)<<"\n";
}
5

Hey @abhi5heklal
Thanks for asking your doubt.
Your implementation of a single shot is wrong. here is a clean implementation.

for(int i=0;i<n;i++){
    if(h[i]%x==0){
        single+=h[i]/x;
    }
    else{
        single+=h[i]/x+1;
    }
}
6

Thank you I got my mistake.:slightly_smiling_face:

8

:grinning: :+1:

9

Can someone tell me why my code getting wrong and where?
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int n,x,ans=0,sum=0;
cin>>n>>x;
int h[n];
for(int i=0;i<n;i++)
{
cin>>h[i];
ans=max(ans,h[i]);
sum+=ceil(h[i]/x);
}
cout<<min(sum,ans)<<endl;
}
return 0;
}