PROBLEM LINK:
Practice
Contest
Video Editorial
Setter: Hasan Jaddouh
Tester: Yash Chandnani
Editorialist: Ishmeet Singh Saggu
DIFFICULTY:
Easy
PREREQUISITES:
Binary Search on Real Numbers(Link1, Link2) and Greedy.
PROBLEM:
You are on earth and you have to shoot down aliens with a cannon(one-shot kill) before it reaches the earth and shoots you. There are N aliens. You can only shoot alien when it appears on the radar. The ith alien appears at the time C_i and requires time D to reach the earth. Now your cannon has a cool-down time before it can shoot another shot. You have to tell the maximum cool-down time you can have such that you can protect the earth.
EXPLANATION:
Suppose if you can protect the earth with a cannon with cool-down time Cd then you can obviously protect the earth with a cannon with cool-down time < Cd. This observation gives us a hint to apply binary search on the cooldown time and compute the answer.
Now let us try to make a function that will tell us the best way to use our cannon and tell us that is it possible to protect the earth with cooldown value Cd.
- It is optimal to shoot the alien which will reach the earth earlier so the shooting order of aliens will be in increasing order of C_i (as D is the same for all aliens so sorting C_i is equivalent to sorting C_i+D).
- We will maintain a time variable time_ stamp and initially its value will be 0.
- We will shoot the aliens in increasing order of their C_i.
- Suppose we have shot all the aliens till i-1 and we are trying to shoot alien i then there will be one of the 3 possible condition.
- Condition 1 = time_ stamp < C_i. In this case alien has not appeared yet and we have to wait for the ith alien to wait till time = C_i and then we will shoot it and then our cannon will cooldown so the final time_ stamp will be equal to C_i+Cd.
if(time_stamp < appear_time[i]) { // appear_time[i] = C[i]
time_stamp = appear_time[i]; // shooted the alien.
time_stamp += cool_down; // now cannon is cooling down.
}
- Condition 2 = C_i \leq time_ stamp \leq C_i+D. In this case, alien has appeared and has not reached the earth yet. We simply shoot it and then wait for our cannon to cooldown. So the final time_ stamp will be equal to time_ stamp+Cd.
if((time_stamp >= appear_time[i]) && (time_stamp <= appear_time[i]+D)) {
time_stamp += cool_down; // Simply shoot and wait for cannon to cooldown to make next shot
}
- Condition 3 = time_ stamp > C_i+D. ith alien has already reached the earth and kills everyone. So, in this case, shows that you cannot kill N aliens with cannon of cooldown value Cd(and returns false) and you have to try a cannon with smaller cooldown value.
- If you are able to kill all N aliens then the function returns true.
So if for a cooldown value Cd if the above function returns true you will try cannon with a higher cooldown value in binary search else you will try a cannon with a lower value. Also, the higher bound on cooldown value will be 2*10^9(C_i+D) as no alien will reach earth after that and lower bound on cooldown value will be 0.
TIME COMPLEXITY:
- The function described above requires O(N). And doing 100 iterations of the binary search will give us answer precise enough. So total time complexity per test case is O(100*N).
SOLUTIONS:
Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int T;
int n;
long long d;
long long A[100100];
int sm_n=0;
int main(){
//freopen("03.txt","r",stdin);
//freopen("03o.txt","w",stdout);
T=readIntLn(1,1000);
cout<<fixed;
cout.precision(10);
while(T--){
n=readIntSp(2,100000);
d=readIntLn(1,1000000000);
sm_n+=n;
assert(sm_n<=1000000);
for(int i=0;i<n;i++){
if(i==n-1){
A[i]=readIntLn(1,1000000000);
} else{
A[i]=readIntSp(1,1000000000);
}
}
sort(A,A+n);
long double l = 0 ,r = 2000000010;
for(int j=0;j<120;j++){
long double rdy= 0;
long double mid =(r+l)/2;
bool can=true;
for(int i=0;i<n;i++){
if(rdy <= A[i]){
rdy = A[i] + mid;
} else if(rdy <= A[i] + d) {
rdy += mid;
} else {
can=false;
}
}
if(can){
l=mid;
} else {
r=mid;
}
}
cout<<r<<endl;
}
assert(getchar()==-1);
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repA(i, a, n) for(int i = a; i <= (n); ++i)
#define repD(i, a, n) for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a) memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
void pre(){
}
ll sum = 0;
int c[100009];
void solve(){
int n=readIntSp(2,100000);
int d=readIntLn(1,1e9);
rep(i,n-1) c[i]=readIntSp(1,1e9);
c[n-1]=readIntLn(1,1e9);
sort(c,c+n);
sum+=n;
ld lo = 0,hi = 2e9;
rep(i,100){
ld md = (lo+hi)/2;
ld lst = 0;
bool fg=0;
rep(j,n){
if(lst>c[j]+d) {
fg=1;
break;
}
lst = max(lst,ld(c[j]))+md;
}
if(fg) hi = md;
else lo = md;
}
cout<<setprecision(20)<<lo<<endl;
}
int main() {
cin.sync_with_stdio(0); cin.tie(0);
cin.exceptions(cin.failbit);
pre();
int n=readIntLn(1,1000);
rep(i,n) solve();
assert(getchar()==EOF);
assert(sum<=1000000);
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
long long N, D;
vector<long long> appear_time;
bool can(long double cool_down) {
long double time_stamp = 0.0;
for(int i = 0; i < N; i ++) {
if(time_stamp < appear_time[i]) {
time_stamp = appear_time[i];
time_stamp += cool_down;
}
else if(time_stamp <= appear_time[i]+D) {
time_stamp += cool_down;
}
else return false;
}
return true;
}
void solveTestCase() {
cin >> N >> D;
appear_time.clear();
appear_time.resize(N);
for(int i = 0; i < N; i ++) {
cin >> appear_time[i];
}
sort(appear_time.begin(), appear_time.end());
long double low = 0, mid, high = 1e18;
for(int i = 0; i < 100; i ++) {
mid = (low + high) / 2.0;
if(can(mid)) {
low = mid;
}
else high = mid;
}
cout << fixed << setprecision(10) << low << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int testCase;
cin >> testCase;
for(int i = 1; i <= testCase; i ++) {
solveTestCase();
}
return 0;
}
Video Editorial
Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed.