Entering edit mode

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

Loading Similar Posts

6

-1000000000 1000000000

1000000000 -1000000000

-1000000000 -1000000000

200 -100

-1000000000 1000000000

100 200

-1000000000 1000000000

1000000000 -1000000000

Output: 6000000600