This is the question from a recent online assessment by a company. Need your help in solving it, thank you for your time!

**Problem Statement**

Alice and Bob are playing a game in a town with houses arranged in a straight line. Houses are numbered from 1 to N.

Alice is standing at house x, and Bob is standing at house y . Each minute, Alice and Bob can decide individually to either move to the next house on the left (if they are not already at the first house), move to the next house on the right (if they are not already at the last house), or stay at their current house.

The goal of the game is for Alice and Bob to ensure that every house in the town is visited by at least one of them. Your task is to determine the minimum number of minutes required for Alice and Bob to achieve this goal in several games.

**Input forma**t

The first line of input contains one integer t, the number of games.

The next t lines describe each game and contain three integers n, x and y, the number of houses in the town, Alice's starting position, and Bob's starting position, respectively.

The combined length of all arrays (10^6 (∑n ≤ 10^6)) does not exceed 10^6.

**Constraints**

1 <= t <= 2.10^4

2 ≤ n ≤ 10^6; 1 ≤ x, y ≤n; x≠y

**Output format:**

- For each game, print one integer the minimum number of minutes required for Alice and Bob to visit every house in the town.

**Example 1**

1

993

**Output**

4

**Explanation**

Total number of houses are 9

Alice is at 9th house and Bob is at 3rd house

1st min -> Alice moves to left 8th position, Bob moves to right 4th position

2nd min -> Alice moves to left 7th position, Bob moves to 3rd position

3rd min -> Alice moves to 6th position, Bob to 2nd

4th min -> Alice moves to 5th position, Bob to 1st

**My code(Not sure if it is correct, but it passed most of test case i took)**

**Edit**: The above solution is wrong.

**Edit 2**:

Correct solution (as of now) by mrxaid

**Spoiler**

Also thanks to xQConqueror and Sahu_1402 for their explaination.

how did you arrive at x-y-2?

After taking so many test cases, i found that pattern.

I would be glad if anyone provide the proof of his solution too.

take x=9 y=5 n=9. Here your approach doesn't seem to work. The ans required is 4 whereas your solution returns 2.

Yeah, you are correct, thanks!

Maybe Greedy will not work for this problem, i tried hours implementing different greedy approaches but none of them worked, and now this too.

If you get a correct solution/approach fell free to comment. Thanks!

Using binary search can be a possible soln.

My CodeTest case: 11 2 7

Ans: 7

Your code: 6

Yeah. Got it. I got it completely wrong.

consider this simulation first number is left pointer position and second number is the right pointer's position 2 7 -> 0 mins 1 8 -> 1 mins 2 9 -> 2 mins 3 10 -> 3 mins 4 11 -> 4 mins 5 10 -> 5 mins 6 9 -> 6 mins this covers all houses in 6 mins. i hope i have not got the question wrong though

Yeah, you are correct, this is discussed in below comment, and the answer 6 is correct.

let a be the number of houses left to the left person,

b be the number of houses right to the right person,

and c be the number of houses in between those 2

if(a+c+c>b) return b

if(b+c+c>a) return a

return min( ceil((a+b+c+c)/2) , ceil((4b+2c+a)/3) , ceil((b+2c+4a)/3) , ceil((2a+2b+c)/2) )

each expression is related to some scenario

It is wrong.

SpoilerTry this.

codeNo, didn't worked.

Test cases you can try:

Input:8

9 9 3

11 7 3

11 6 3

11 3 6

11 2 7

11 3 7

17 5 11

9 9 5

Output:4

6

6

6

7

6

10

4

(These are generated by me, so cross check the expected answer)

Bro i have corrected my solution, here below it is, according to me this is correct, the test case, 11 3 7, will have 6 as output, you can see (make both alice and bob reach index 5 (0 based), by repeating minimum number of moves, try dry running my code on paper), this is correct according to me.

codeyes 11 3 7 will have 6(and it is written there) but 11 2 7 will have 7 and your new code returns 6 to it. But you are almost there, improve for 11 2 7.

it will also have 6 as answer, consider this array 0 based 0, A, 2, 3, 4, 5, B, 7, 8, 9, 10, here alice at 1st index and bob at 6th, now try splitting at the 5 index, bob will repeat min move 2 time and do max move 1 time, similar for alice also, and result will be 6

11 2 7

A path : 1 2 3 4 5 6

B path: 6 7 8 9 10 11

So answer is 6

Oh yes, sorry , my bad!

so can we say this problem is closed and solved for now, maybe try to add my code in the problem statement as a snippet as a possible solution

Binary search the minimum number of minutes.

— — — — A — — — — — — — B — — — — -

Lets say you are B, you have 2 options:

Fill right then switch to the left

Go to the left and then fill the right

Check both to see wich one covers more houses, do the same with A and check if you covered all the houses

The other 2 cases are more trivial(also included in the binary search aproach)

A — — — — — — — — B

— — — — A B — — — —

Let's assume that

x<y, then the image of the scenario can be drawn like this,---(Left)---A----(Middle)----B----(Right)----we know that Alice will take care of the left houses and Bob will take care of the right houses. The only thing we can do is to find the number of middle houses such that maximum time taken by Alice and Bob is minimum. To do this, we can simply iterate from 0 to "number of the middle houses" and find out the minimum time taken.Pseudo Codemid = number of middle house

minimum_total_time = INT_MAX

for i 0 to mid

time_taken_by_Alice = 2*min(i , left) + max(i , left);

time_taken_by_Bob = 2*min(mid-i , right) + max(mid-i,right);

minimum_total_time = min(minimum_total_time , time_taken_by_Alice + time_taken_by_Bob)

hi, can you please share the 4th question of this set in which this question was 1st?