 Practice

Contest

EASY MEDIUM

Prerequisites:

Binary Search, Greedy

Problem:

N students are standing at distinct points in the X-axis. 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.

Setter

Tester

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)

2 Likes

Followed editorial approach… Can someone help me why this code gives WA Link

Can any one explan a greedy approach like,

[r,r,r,r,r]

[l,r,r,r,r]

[l,l,r,r,r]

[l,l,l,r,r]

[l,l,l,l,r]

[l,l,l,l,l]
where l is left and r is right direction assigned will not work?

1 Like

Simple solution of the editorial here

2 Likes

@admin How was the number of iterations decided? Can you please elaborate mathematically?

@gagan86nagpal

Consider there are five children. C1,C2,C3,C4,C5 placed in the following manner.

C1…C2.C3…C4.C5

The second and third child are placed very very close to one another and fourth and fifth child are placed very very close to one another. And first and second child are placed at a wide distant and third and fourth child are also placed at a wide distant. Now the first one moves left, the second one moves left. But if the third one moves left, it will meet the second child much earlier than if it would have moved right.
So the optimal allocation will be L,L,R,L,R.
Hope it helps!

3 Likes

Would this approach work?

First check the time when all the children run in the same direction (either all left, or all right)

Then after this, re-check the same case by altering the state of just one child. i.e. when all go left, one child goes right. (and similarly, when all go right, one child goes left.)

I wonder if this is right, because this approach will ideally try to find the first pair to cross, by trying to ignore all other possible pairs.

An example with 5 children would be -

[l, l, l, l, l] (All same direction)

[r, l, l, l, l] (One child has opposite state)

[l, r, l, l, l]

[l, l, r, l, l]

[l, l, l, r, l]

[l, l, l, l, r]

[r, r, r, r, r] (All same direction)

[l, r, r, r, r] (One child has opposite state)

[r, l, r, r, r]

[r, r, l, r, r]

[r, r, r, l, r]

[r, r, r, r, l]

Is there any possible test case that this approach would fail on?

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:

(https://www.codechef.com/viewsolution/18354782). (I didn't actually partake in the competition.)
3 Likes

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 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?

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 :

mem[i][state] = time(i,i+1,state) for i=0,i+1=1.

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:

mem[i][state] = max_i( min(mem[i-1][prevstate_i], time(i,i+1,state)) )

over all previousstates of corresponding state.
Now the possible states are {RR, RL, LR, LL} and for example the valid previous states are RR ->{RR, LR} and similarly for others. These combinations can be stored as integers like states = 0,1,2,3 for faster operations. Since only the maximum time is required the answer is

max_i(mem[n-2][state_i])

The complexity is O(nlogn + 8n)

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

1 Like

I suppose in first line you mean, [r,r,r,r,r]

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

thanks , edited!

LOl, This was so easy to think about.
Stupid me.
Thanks, @iam_ss for detailed explanation

1 Like

This approach will fail for the following test case:

1

16

1000 1

1001 2

2000 2

2001 1

3000 1

3001 2

4000 2

4001 1

5000 1

5001 2

6000 2

6001 1

7000 1

7001 2

8000 2

8001 1

nice solution - I was sure it can be done with DP but i was missing a case - thank you 