Interesting OA problem

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
8	Dominater069	154
8	nor	154

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)

#include <bits/stdc++.h>
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 rem = n - 2;
    if(y == 1 && x == n){
      cout << rem / 2 + (rem % 2 != 0) << endl;
      continue;
    }
    if((x == n && y > 1) || (y == 1 && x < n)){
      cout << x - y - 2 << endl;
      continue;
    }

    int temp = x - y - 2;
    cout << max((y - 1) + temp, (n - x) + temp) << endl;
  }
  
  return 0;
}

Edit: The above solution is wrong.

Edit 2:
Correct solution (as of now) by mrxaid

Spoiler

#include <iostream>
#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<<max(x, n-1-y)<<endl;
      continue;
    }
    ll ans = 1e9;
    for(int i=x; i<=y; i++){
      ll minix = min((i-x),x);
      ll maxix = max((i-x),x);
      ll miniy = min((y-i-1),(n-1-y));
      ll maxiy = max((y-i-1),(n-1-y));
      ans = min(ans, max(2*minix+maxix, 2*miniy + maxiy));
    }
    cout<<ans<<endl;
  }
  return 0;
}

Also thanks to xQConqueror and Sahu_1402 for their explaination.

// JAI SHREE KALYAN #include <bits/stdc++.h> #include<iostream> using namespace std; #define ll long long #define pl pair<long long , long long> void solve(){ ll n , x , y ; cin >> n >> x >> y ; if(x > y )swap(x , y) ; ll ans = max(n-x,y-1); // 1 a 3 4 5 6 b 8 9 10 11 // if((x-1) > (n-y)){ ans = min(ans , max((y-x-1) + 2*(n-y) , x-1)); }else{ ans = min(ans , max(n-y, y-x-1 + 2*(x-1))) ; } cout << ans << endl ; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); return 0; }

#include <bits/stdc++.h> using namespace std; #define ll long long #define mod 1000000007 void solve() { } int main() { ll test = 1; cin >> test; while (test--) { ll n, x, y; cin >> n >> x >> y; if (x < y) { ll dxy = abs(y - x) - 1; ll dx1 = abs(x - 1) - 1; ll dyn = abs(n - y) - 1; ll ans = min((2 * dxy) + dyn + dx1, min(dxy + (2 * dyn) + dx1, dxy + dyn + (2 * dx1))); cout << ans << endl; } else { ll dxy = abs(y - x) - 1; ll dy1 = abs(y - 1) - 1; ll dxn = abs(n - x) - 1; ll ans = min((2 * dxy) + dy1 + dxn, min(dxy + (2 * dy1) + dxn, dxy + dy1 + (2 * dxn))); cout << ans << endl; } solve(); } return 0; }

Comments (26)

Write comment?

Plutonium_09

3 months ago, # |

how did you arrive at x-y-2?

→ Reply

Amit9

3 months ago, # ^ |

← Rev. 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!

akumar_23

Using binary search can be a possible soln.

My Code

#include<bits/stdc++.h>
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<<ans<<endl;
	}
 	
		
}

Test case: 11 2 7
Ans: 7
Your code: 6

Yeah. Got it. I got it completely wrong.

aaditya02

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.

jokkeer

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.

#include <bits/stdc++.h>
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;
}

mrxaid

Try this.

code

#include <iostream>
#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<<max(a, c)<<endl;
    }
    else{
      b -= 1;
      b -= (abs(c-a));
      cout<<max(a, c)+(b+1)/2<<endl;
    }
  }
  return 0;
}

No, 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.

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.

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

xQConqueror

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

← Rev. 9 →

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 — — — —

Sahu_1402

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 Code

Honkai_Star_Rail

3 weeks ago, # ^ |

you should do, min_tot_time = min(min_tot_time, max(alice,bob)), instead of adding them up

KRISHNA.

2 months ago, # |

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

naman.gokhru.mst20

4 weeks ago, # |

This is my code , i tried it on so many test cases , please prove me wrong if i am.1. —

shubhamdhingra2003

This code is working check it out.

dharmesh_kumar

3 weeks ago, # |

1488C - Two Policemen Here is the question, if anyone is still searching

Amit9's blog