RUNDIR - Editorial

general
, , , ,
1

Problem Link:

Practice

Contest

Setter: Alei Reyes

Tester: Triveni Mahatha

Editorialist: Triveni Mahatha

Difficulty:

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.

SOLUTION:

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)

1 Like
2

Followed editorial approachā€¦ Can someone help me why this code gives WA Link

3

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
4

Simple solution of the editorial here

2 Likes
5

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

6

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

7

@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
8

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

9

thanks , edited!

10

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

1 Like
11

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?

12

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

Answer by your approach: 1

Correct Answer = 249.75

1 Like
13

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.)
1 Like
14

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 :slight_smile:

15

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!

1 Like
16

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

17

i spent / wasted several hours on this question.
the following are two of my many submissions :

  1. https://www.codechef.com/viewsolution/18630732

  2. https://www.codechef.com/viewsolution/18628847

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?

18

replied you at your queā€¦

19

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
20

@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=j-1 ?