9 weeks ago

John 910

Hyderabad

Question1

Question 2

Question 3

21 months ago

Yash Sahijwani 940

Solution for Problem 1

Analysis

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).

Implementation

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';

18 months ago

Ayush Kumar Shaw 110

Solution to Question 2

It's given that the i-th set contains all integers from l_i to r_i. So the size of this set will be r_i-l_i+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);
        }
    }