21 months ago

Vijay • 10

Summer Internship

Question 1:

8 months ago

Shikhar Mehrotra 480

Chennai

• Assuming number of apples to be at most 1000

Q1) Hint : Observe this line Also you need to help them catch the apples in the sequence they fall

Solution:
Representing max(alice_pos,bob_pos) as P
Let F(alice_pos,bob_pos) represent minimum distance that need to be travelled to end if till now start to max(alice_pos,bob_pos) apples have been picked and alice is currently at alice_pos and bob is currently at bob_pos. Then from here as it is given in the question that they need to catch apples in sequence (i.e they cannot catch second apple before the first one) ,some of them will go to next apple. Since currently they have covered start to P then then they need to pick P+1 apple after that(P+2,P+3...and so on). Hence we have two options over here that is either take alice to P+1 or take bob to P+1 and check which gives the minimum distance.
Pseudo Code

Consider positions as the array of apples {pos[0],pos[1]....pos[n-1]} 
and push alice and bob positions into it also. positions{alice_initial,bob_initial,pos[0],pos[1],pos[2].....,pos[n-1]} 
and let F(alice_pos,bob_pos) represent as stated above in the Solution section.
int F(int alice,int bob)
{  
if(max(alice,bob)==(n+1))//consider 0 based indexing
    return 0; //we have covered all the apples hence distance travelled to end from here would be 0.
int P=max(alice,bob);
    //dist(A,B) represent manhattan distance between points A and B.
int choice1=F(P+1,bob)+dist(positions[alice],positions[P+1]); //take Alice to P+1
int choice2=F(alice,P+1)+dist(positions[bob],positions[P+1]); //take Bob to P+1
return min(choice1,choice2);
}

And we could optimize it by memoizing the above recursion over state{alice_pos,bob_pos} to O(n^2)

22 months ago

Red • 0

May i have the fourth test case please?