ALIENIN - Editorial

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. :smile:

6 Likes

I did apply binary search in this question.

https://www.codechef.com/viewsolution/37366146

You needed a bit higher higher bound, here is your AC code :
the worst case input we can assume is

N = 2
C = 1, 1e9
D = 1e9

output should be 2e9, but you took higher bound as 1e9.
https://www.codechef.com/viewsolution/37367498

1 Like

same here : refer

thank bro

1 Like

thanks bro

1 Like

I am new to this application of binary search. Can someone please tell me why we take 100 iterations? Also what will happen if we take fewer or more iterations.

More iteration means more precision. So for 100 iteration you can do normal binary search on integers or array of size 2^{100}. But when you are doing binary search on real number then you are dividing range into parts. so you are basically dividing range of length 2*10^9(in this question) into 2^{100} segments of length (\frac{2*10^9}{2^{100}}) and applying binary search on them so more the iteration smaller will be the length of each segment hence more precise will be the answer.

4 Likes

infact in this question instead of 100, 60 iterations will give accuaracy upto 109

U can also do this -

while ((r-l)>=0.00000000001)
{
      ld mid = (l+r)/2;
      if(valid())
          l = mid+1;
      else
          r = mid-1;
}
1 Like

But, isn’t the time complexity of sorting the array O(nlogn)?

Right. It should be O(n * logn +n * 100)

why 100 ?

at most 100 iterations , so 100

thanks alot for the answer guys @psychik @ssrivastava990 @abhaypatil2000

1 Like

that 100 is log n factor :face_with_head_bandage:

I want to know why solving N equations won’t work.
Suppose Cool-Down time is ‘t’ and we want to maximise it.
Wouldn’t these N equations solve for max values of ‘t’.

Here Ci is sorted in Ascending order and first alien has been killed at time ‘S’ since canon was already cool. So,

S + t <= C2 + d;
S + 2t <= C3 + d;
… and so on

I’ve used hash map.
Can anyone explain me what is wrong with my approach,please?[https://www.codechef.com/submit/ALIENIN]

import java.util.*;
import java.math.*;

 class A {
	public static void main(String[] args) {
		A ob = new A();
		ob.solve();
	}

	static Scanner sc = new Scanner(System.in);
	static long n, d;
	static ArrayList<Long> al = new ArrayList<>();

	static boolean can(double cool_down) { // check if the passed cool_down is applicable to all the situations
		double time_stamp = 0;
		for (int i = 0; i < n; i++) {
			if (time_stamp < al.get(i))
				time_stamp = (cool_down + al.get(i));
			else if (time_stamp <= (al.get(i) + d))
				time_stamp += cool_down;
			else
				return false;
		}
		return true;
	}

	void solve() {
		try {
			int t = sc.nextInt();
			for (int j = 0; j < t; j++) {
				al.clear();
				n = sc.nextInt();
				d = sc.nextInt();

				for (int i = 0; i < n; i++)
					al.add(sc.nextLong());

				Collections.sort(al);

				double low = 0, mid = 0, high = 1e10;
				while ((high - low) > 10e-6) { // apply binary search to all the possible values of cool_down
					mid = (low + high) / 2.0;
					if (can(mid))
						low = mid;
					else
						high = mid;
				}
				System.out.println(String.format("%.10f", low));
			}
		} catch (Exception e) {
			return;
		}
	}

}

I tried submitting this code, it is passing just 2 of the 4 test cases, please help me out on where I am going wrong

Take high = 2e10 , “Help in Alien Invasion [Lunchtime Aug 2020 , Solved ,(Binary Search)]