### Amit9's blog

By Amit9, history, 6 weeks ago,

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)

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.

• +9

 » 6 weeks ago, # |   0 how did you arrive at x-y-2?
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 After taking so many test cases, i found that pattern.I would be glad if anyone provide the proof of his solution too.
•  » » » 6 weeks ago, # ^ |   0 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.
•  » » » » 6 weeks ago, # ^ |   0 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!
 » 6 weeks ago, # |   0 Using binary search can be a possible soln. My Code#include using namespace std; #define ll long long #define endl "\n" bool check(ll n,ll x, ll y, ll mid){ if((mid<(x-1))||(mid<(n-y)))return false; ll rem_x = mid-(x-1); ll cover_x = x; if(x==1)rem_x++; if(rem_x>=1)cover_x += (rem_x-1); ll rem_y = mid-(n-y); ll cover_y = y; if(y==n)rem_y++; if(rem_y>=1)cover_y -= (rem_y-1); if((cover_x+1)>=cover_y)return true; return false; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int tc = 1; // cin>>tc; // cin.ignore(); while(tc--){ ll n,x,y; cin>>n>>x>>y; if(x>y)swap(x,y); ll low = 0, high = n+1; ll ans = 0; while(low<=high){ ll mid = (low+high)/2; if(check(n,x,y,mid)){ high = mid-1; ans = mid; } else{ low = mid+1; } } cout<
•  » » 6 weeks ago, # ^ |   0 Test case: 11 2 7Ans: 7Your code: 6
•  » » » 6 weeks ago, # ^ |   0 Yeah. Got it. I got it completely wrong.
•  » » » 4 weeks ago, # ^ |   0 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
•  » » » » 4 weeks ago, # ^ |   0 Yeah, you are correct, this is discussed in below comment, and the answer 6 is correct.
 » 6 weeks ago, # | ← Rev. 2 →   0 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 2if(a+c+c>b) return bif(b+c+c>a) return areturn 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
•  » » 5 weeks ago, # ^ |   0 It is wrong. Spoiler#include using ll = long long; using dl = double long; using namespace std; const ll MOD = 1e9 + 7; int main() { int t; cin >> t; while(t--){ int n, x, y; cin >> n >> x >> y; // if(x == y){ // cout << max((y - 1), (n - x)) << endl; // continue; // } if(x < y) swap(x, y); // cout << x << "_" << y << endl; int a = y - 1; int b = n - x; int c = x - y - 1; int q = (a+b+2*c) / 2 + ((a+ b+ 2*c) % 2 != 0); int w = (4*b+2*c+a)/3 + ((4*b+2*c+a) % 3 != 0); int e = (b+2*c+4*a)/3 + ((b+2*c+4*a)%3 != 0); int r = (2*a+2*b+c)/2 + ((2*a+2*b+c)%2 != 0); if(a+c+c>b) cout << b << endl; else if(b+c+c>a) cout << a << endl; else cout << min({q,w,e,r}) << endl; } return 0; }
 » 5 weeks ago, # |   0 Try this. code#include #define ll long long using namespace std; int main(){ int t; cin>>t; while(t-->0){ ll n, x, y; cin>>n>>x>>y; x--; y--; // i consider indexes of houses are 0-based if(x>y){swap(x, y);} ll a = 2*x - 1; ll b = y-x+1; ll c = 2*(n-y-1) - 1; if(abs(c-a)>=b){ cout<
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 No, didn't worked.Test cases you can try:Input:89 9 311 7 311 6 311 3 611 2 711 3 717 5 119 9 5Output:466676104 (These are generated by me, so cross check the expected answer)
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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. code#include #define ll long long using namespace std; int main(){ int t; cin>>t; while(t-->0){ ll n, x, y; cin>>n>>x>>y; x--; y--; if(x>y){ swap(x, y); } if(x==y){ cout<
•  » » » » 5 weeks ago, # ^ |   0 yes 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.
•  » » » » » 5 weeks ago, # ^ |   0 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
•  » » » » » 5 weeks ago, # ^ |   0 11 2 7A path : 1 2 3 4 5 6B path: 6 7 8 9 10 11So answer is 6
•  » » » » » » 5 weeks ago, # ^ |   0 Oh yes, sorry , my bad!
•  » » » » » » » 5 weeks ago, # ^ |   0 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
 » 5 weeks ago, # | ← Rev. 9 →   0 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 housesThe other 2 cases are more trivial(also included in the binary search aproach)A — — — — — — — — B— — — — A B — — — —
 » 5 weeks ago, # |   0 Let's assume that x
 » 9 days ago, # |   0 hi, can you please share the 4th question of this set in which this question was 1st?