Interesting OA problem

Revision en1, by Amit9, 2024-08-03 13:55:44

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 format

  • 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)
Tags greedy, online assessment 2024, dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Amit9 2024-08-04 21:27:29 114 Tiny change: 'for their solutions.\n\n' -> 'for their explaination.\n\n'
en3 English Amit9 2024-08-04 21:22:51 726
en2 English Amit9 2024-08-03 15:36:08 45 Tiny change: 'oiler>\n\n' -> 'oiler>\n\n\nEdit:\nThe above solution is wrong.\n'
en1 English Amit9 2024-08-03 13:55:44 2760 Initial revision (published)