Problem Link:Setter: Alei ReyesTester: Triveni MahathaEditorialist: Triveni MahathaDifficulty:EASY MEDIUM Prerequisites:Binary Search, Greedy Problem:N students are standing at distinct points in the Xaxis. Every students will start running at t = 0. assign direction (left/right) to each of them such that the first time when any two students cross each other is as large as possible. Speed of every students is given. Quick Explanation:Do binary search on the time. Suppose at any step in the binary search, we are are trying to find whether it is possible to assign direction such that no students will cross before some time say t. To check, whether it is possible to assign direction. We fix the direction of leftmost students towards left (without loss of generality). For every other student from left to right, we try to fix the direction to left itself if it crosses non of the students before time t. And move to next student. If it is not possible, we try to fix the direction as right. If it is possible then move to next student. If we are able to assign direction to each students in that manner then the answer is yes, otherwise it is not possible. SOLUTION:Time Complexity:For required precision, iterating 100 steps in the binary search is enough. Let's say the number of steps be S. $O(S N)$ per test case. Space Complexity:$O(N)$
This question is marked "community wiki".
asked 23 Apr '18, 00:10

I just applied dynamic programming directly and had no need for a binary search. I first sorted the students based on their starting positions. Asymptotically that is the most expensive part of my algorithm, taking $\mathcal O(N\log(N))$ operations. The trick is to note if child $j$ starts between children $i$ and $k$ then child $i$ cannot pass child $j$ before child $k$ passes one of them. That means that the moment when the first child will be passed will also be the moment when two children who started next to each other pass each other. That is convenient for dynamic programming. We will work from left to right and only need to keep track of two possibilities: either the most recent child went left or he went right. Associated with each state we also keep track of the latest possible first passing time for the students that have been considered so far. Initially we begin with the child who starts farthest to the left. For both states, left and right, the latest passing time is $\infty$ since passing is not possible with just a single child. Each time we update the state we will need to find the best solution assuming that the next child goes left and also the best solution assuming that he goes right. In both cases we need to consider the two possible moves of the previous child and compare their crossing times, if they cross, with the previous first crossing times for the associated states. This part of the algorithm requires only $\mathcal O(n)$ operations. Here is my code: code. (I didn't actually partake in the competition.) answered 26 Apr '18, 03:48
nice solution  I was sure it can be done with DP but i was missing a case  thank you :)
(17 May '18, 02:14)

I came up with a pretty simple DP solution. The trick is sorting according to position and then checking the 4 combinations of the first pair of students that is :
Then for the next pair of elements(overlapped) i=1,i+1=2 , mem[i][state] is the maximum out of all possible combinations of time which can be made into a equation like:
over all previousstates of corresponding state.
Now the possible states are
The complexity is $O(nlogn + 8n)$ answered 16 Jun '18, 14:59

@gagan86nagpal answered 25 Apr '18, 03:20
1
LOl, This was so easy to think about. Stupid me. Thanks, @iam_ss for detailed explanation
(25 Apr '18, 09:03)

Followed editorial approach... Can someone help me why this code gives WA Link answered 24 Apr '18, 00:04

@admin How was the number of iterations decided? Can you please elaborate mathematically? answered 25 Apr '18, 02:41
Maximum no of iteration to reach an integer no for high=10^20 is log2(10^20) = 66 and for getting a accuracy of 6 decimals we need 6 more iterations, that means intotal 72 iterations ate sufficient and hence 100 iterations are not bad
(25 Apr '18, 08:39)
1
Cool! I got it. But I think that the way you accommodated the number of iterations for the decimal portion is not correct. Since we need to get the answer correct upto 6 decimal places, we need to go 6 places to the left of the decimal to get the answer, just like we needed to go to 20 places to the right of the decimal to reach upto 10^20. Hence, just add 6 more to 20, and the number of iterations will come out to be log(10^26) which is close to 87. I tried running your solution each with 72, 75, 80, 85 and 87 iterations. And the solution got accepted for 87 iterations and failed even for 85!
(09 May '18, 14:42)

Can anybody explain how the bounds are chosen? I don't quite understand the two points. why is high 10^20, and why is mid checked for greater than 10^15 to print 1. Any insight that I am missing? Thanks :) answered 30 Apr '18, 13:43

i spent / wasted several hours on this question. the following are two of my many submissions : the only difference between the 2 codes is that at line no.72 i used "double" in '1' and "long double" in '2'. there is absolutely no other difference between either submissions. the first submission gives me AC where as the second gives me WA. what could be the reason for this? long double is as precise as double is if not better. then why the WA? answered 22 May '18, 21:31

@triveni @vijju123 Isn't the time complexity O(S*(N^2)) because you are looping for every j from the start i.e. from i=0 to i=j1 ?