ALIENIN - Editorial

editorial
, , , , , ,
3

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
4

same here : refer

5

thank bro

1 Like
6

thanks bro

1 Like
7

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.

8

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
9

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

10

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
11

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

12

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

13

why 100 ?

14

at most 100 iterations , so 100

15

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

1 Like
16

that 100 is log n factor :face_with_head_bandage:

17

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

18

I’ve used hash map.
Can anyone explain me what is wrong with my approach,please?[CodeChef: Practical coding for everyone]

19 
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

20

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

21

Tried doing that, still didn’t work. Please help.

22

I think ,equations should be, ci <= s+(i-1)*t <= ci + d;