Amit9's blog

By Amit9, history, 3 months ago, In English

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.

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how did you arrive at x-y-2?

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    After taking so many test cases, i found that pattern.
    I would be glad if anyone provide the proof of his solution too.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Using binary search can be a possible soln.

My Code
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah. Got it. I got it completely wrong.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is wrong.

    Spoiler
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Try this.

code
  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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)

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          11 2 7

          A path : 1 2 3 4 5 6

          B path: 6 7 8 9 10 11

          So answer is 6

          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh yes, sorry , my bad!

            • »
              »
              »
              »
              »
              »
              »
              3 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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

»
3 months ago, # |
Rev. 9   Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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



// 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; }
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This code is working check it out.

#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;
}
»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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