Entering edit mode

Click here to Practice

Submit Problem to OJ

Click here to Practice

Submit Problem to OJ

Entering edit mode

In the question it is mentioned that we are given friends from 1 to n standing in the line, and a baton is passed from friend 1, such that the direction of passing changes at every extreme end. Here we can see that going from 1 to n takes (n-1) seconds. e.g. if n=4, going to 2 takes 1 second, similarly for 3 we have 1 second and similarly for 4. Hence going from 1 to n takes (n-1) seconds, and similarly going from n to 1 takes (n-1) seconds. So the total time it takes to go from 1 to n and then back to 1 is 2*(n-1) seconds.

So if say we have to find out which friend has the baton at some t, such that 2*(n-1) < = t < 4*(n-1) i.e. it has completed one round but has not completed the second round, then the friend who had the baton at time t - 2*(n-1) +1, will have the baton at time t, because after the baton reaches the point 1 again after completing the first round, the second round becomes exactly the same as the first round, just that in the second round all times after shifted by 2*(n-1).

So if we have time t, we can calculate its corresponding time in the first round by using t modulo 2*(n-1). Now the new time is between 0 and 2*(n-1) (0 < = t < 2*(n-1)). Now we just need to calculate what is the position at every timestep in the first round. So if t is less than equal to n-1, the answer is simply t+1, since it takes n-1 seconds to get to n, and so at time n-1 it is at n, at time n-2 it is at n-1 ... so at time t it is at t+1. If t is greater than n-1, the answer is n - (t-(n-1)). This is because we first calculate the time elapsed in the return trip from n to 1, which is t - (n-1). For the return trip, if 1 second has passed the baton is at n-1, after 2 seconds it is at n-2.. and so on. so baton will be at n - (t - (n-1)).

Also the friend who passed the baton will be ans - 1 if 1 <= t <= n-1, otherwise ans+1. (Note the point where the ans is 1 -> the friend who passed the baton will be 2).

```
k = k % (2*(n-1));
if(k<=n-1 && k!=0)
cout < < k < < " " < < k+1 < < '\n';
else if(k==0)
cout < < 2 < < " " < < 1 < < '\n';
else
cout < < n-(k-(n-1))+1 < < " " < < n-(k-(n-1)) < < '\n';
```

Entering edit mode

**Solution to Question 2**

It's given that the `i-th`

set contains all integers from l<sub>i</sub> to r<sub>i</sub>. So the size of this set will be **r<sub>i</sub>-l<sub>i</sub>+1**. Now, we need to find the smallest set with size greater than or equal to 2.

**Pseudocode**

```
int ans=INT_MAX;
for(int i=0 ; i < n;i++){
if(r[i]-l[i]+1 >= 2){
ans=min(ans,r[i]-l[i]+1);
}
}
```

Loading Similar Posts