Help in Alien Invasion [Lunchtime Aug 2020 , Solved ,(Binary Search)]

Question : “https://www.codechef.com/LTIME87A/problems/ALIENIN
My solution [WA in contest ] : “https://www.codechef.com/viewsolution/37278364
My solution [ AC in practice] : “https://www.codechef.com/viewsolution/37286140

Please help where I m wrong ? @udayan14 @galencolin

1 Like

Try to run the binary search specific number of times like 100

It showing WA not tle :roll_eyes: and I think my valid function is wrong , but where I don’t know :frowning_face:

1 Like

I just changed upper bound to 10^10 and it worked

rather multiply everything by 10^7
and then divide answer by 10^7
i went through same

Really ?

not to loose precision other way was to handle using numerator and denominator only!

Try it

I knew the idea was binary search but I didn’t knew how to check for particular “time”.

always start as early as possible to shoot was the general idea.

and I Implement it but for each TC only one file is passed :sob:

I made constant EPS too precise and tle! I submitted it in last 30 seconds!

Consider this case :
1
2 1000000000
1 1000000000

In this case answer will be 2*10^9 but upper bound in your solution is 10^9.
Same happened to me also.

Final AC solution : “https://www.codechef.com/viewsolution/37286140

Thanks @krunal9220

Take upper bound to 2*109 and it will pass :sob:

I was kindoff thinking to iterate over intervals in ascending order of C and keep the variable when was the last time canon was shot. Then for each next interval check if the canon can be shot in this interval or not?
Am I going in right direction?

Experience++ For next binary search problem. :sweat_smile:

1 Like

Here’s my submission. We are doing pretty much the same thing. Your starting value of right is not right(You can get an upper bound for it). I can’t find the bug in your code. Its mostly to do with the end of your binary search

Thanks, @udayan14 . I corrected , upper bound is wrong

Ya much close!

Just solved it, bro :slight_smile: I was so dumb not to implement it :frowning_face:
AC
Thank You for your time.
Have a good day!

1 Like