Question: Atlassian | 10th October | Online Assessments | Pass the Baton | Smallest Set Covering Intervals | Paint the ceiling
1
Entering edit mode
0
Entering edit mode

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&lt;=n-1 &amp;&amp; k!=0)
    cout &lt; &lt; k &lt; &lt; " " &lt; &lt; k+1 &lt; &lt; '\n';
else if(k==0)
    cout &lt; &lt; 2 &lt; &lt; " " &lt; &lt; 1 &lt; &lt; '\n';
else
    cout &lt; &lt; n-(k-(n-1))+1 &lt; &lt; " " &lt; &lt; n-(k-(n-1)) &lt; &lt; '\n';
ADD COMMENTlink 2.0 years ago Yash Sahijwani 910
0
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 &lt; n;i++){
        if(r[i]-l[i]+1 &gt;= 2){
            ans=min(ans,r[i]-l[i]+1);
        }
    }
ADD COMMENTlink 2.0 years ago Ayush Kumar Shaw 110

Login before adding your answer.

Similar Posts
Loading Similar Posts