BFRIEND - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Ashish Lal
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Alice, Bob and N friends of Bob live in a particularly huge building. Alice lives on the floor a, Bob lives on floor b and i-th friend of Bob lives on floor F_i. It takes exactly one minute to move from floor i to floor i+1 and vice versa. Bob first visit one of his friend’s house, takes c minutes to change and then goes to Alice’s house.

Calculate minimum time required to do so.

QUICK EXPLANATION

  • For a friend living at floor x, the time taken by Bob to reach Alice’s floor is |a-x|+|b-x|+c
  • We can consider each friend and calculate the time required to reach Alice, and take the minimum time.

EXPLANATION

Suppose Bob needs to go from floor b to floor x, spend c minutes here and then go from floor x to floor a. As we can see, it takes him |x-b|+c+|x-a| minutes to reach Alice.

We can actually try all the friend’s floor at x and see which gives us the minimum time.

Bonus problem
Suppose it takes a fee to move from floor x to floor x+1 and vice versa, which is equal to the number of minutes till now+1 i.e. If you are at floor x at time y minutes, it costs y+1 units to move to floor x+1 or x-1 in one minute.

Calculate the minimum cost to reach Alice’s floor.

TIME COMPLEXITY

The time complexity is O(N) per test case.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int32_t main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin>>t;
  while(t--)
  {
		long long int n,a,b,c;
		cin>>n>>a>>b>>c;
		long long int ans=-1;
		long long int f;
		cin>>f;
		n--;	
		ans=c+abs(b-f)+abs(f-a);
		while(n--)
		{
			cin>>f;
			ans=min(ans,c+abs(b-f)+abs(f-a));
		}  
		cout<<ans<<'\n'; 	
  }
  return 0;
} 
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;

#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
#define int ll
int gg[123456];
main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		int a,b,c;
		cin>>a>>b>>c;
		int i;
		rep(i,n){
			cin>>gg[i];
		}
		int mini=abs(gg[0]-b)+abs(gg[0]-a);
		rep(i,n){
			mini=min(mini,abs(gg[i]-b)+abs(gg[i]-a));
		}
		mini+=c;
		cout<<mini<<endl;
	}
	return 0;   
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class BFRIEND{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int n = ni();
	    long a = nl(), b = nl(), c = nl();
	    long ans = Long.MAX_VALUE;
	    for(int i = 0; i< n; i++){
	        long x = nl();
	        ans = Math.min(ans, Math.abs(a-x)+Math.abs(x-b)+c);
	    }
	    pn(ans);
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	DecimalFormat df = new DecimalFormat("0.00000000000");
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new BFRIEND().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

Why this shows wrong answer ?? Plzz tell me?

#include <stdio.h>
#include <stdlib.h>
int main()
{
int T, i, j, m;
long int N;
long long int a, b, c, y;
scanf("%d",&T); //takes the no. of test case
while(T–)
{
scanf("%ld",&N);
scanf("%lld",&a);
scanf("%lld",&b); //takes the 1.no of friends 2.alice floor 3. bob initial floor 4.time to change
scanf("%lld",&c);

     long long int F[N];
     long long int arr[N], smallest;

    for(i=0; i<N; i++)
    {
        scanf("%lld",&F[i]);
    }

    for(j=0; j<N; j++)
    {
        y=abs(F[j]-a)+abs(F[j]-b);
        arr[j]=y;
    }


    smallest = arr[0];

    for (m = 0; m < N; m++)
        {
            if (arr[m] <= smallest)
            {
                smallest = arr[m];
            }


        }
           printf("%lld",smallest+c);
        }
         return 0;

    }

why this code is wrong

#include<bits/stdc++.h>
using namespace std;

int main()
{
int t;
cin>>t;
while(t–)
{
long long int n,a,b,c,min=LLONG_MAX,sum,x ;
cin>>n>>a>>b>>c;
while(n–)
{
long long int f;
cin>>f;
if( min> abs(f-a) )
{
min=abs(f-a) ;
x=f;
}
}

     sum = abs(a-x) + c + abs(b-x)  ;
     cout<<sum<<endl ;
}
return 0;

}

In the code you have implemented, you are completely ignoring the distance that Bob has to travel to go to his friend’s room.
Let’s say a=13,b=8 and his friends are at 10 and 14.
According to your code min=13 (because abs(14-13) < abs(10-13)) but this way Bob will be travelling much more than what he would have to travel if he went to his friend at 10th floor.

Change your code to find the minimum value of abs(f-a)+abs(f-b) instead.

what is wrong with my code?

#include <bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
long n,a1,b,c;
cin>>n>>a1>>b>>c;
long a[n];
long i;
for(i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
long time=0;
if((a[0]>b && a[0]<a1) || (a[0]>a1 && a[0]<b))
{
time+=(abs(b-a1)+c);
}
else if((b>a[0] && b<a1) || (b>a1 && b<a[0]))
{
time+=(abs(b-a1)+c+(2abs(b-a[0])));
}
else if((a1>a[0] && a1<b) || (a1>b && a1<a[0]))
{
time+=(abs(b-a[0])+c+(2
abs(a[0]-a1)));
}
cout<<time<<endl;

}
return 0;

}

My code works for small inputs but not large ones like 10^9. I have used binary search to find smallest and largest friend index near bob (smallest I found by multiplying bob with -1 and friend indices by -1), and taken nearer friend of the two. Why does it not work for large inputs? In second testcase when for c and friend I substitute 10 instead of 10^9 I get correct answer.

Blockquote#include
#include
#define ll long long int
using namespace std;

int main()
{
ll t,nooffriends,bob,alice,changetime,i;
cin>> t;
while(t–)
{
cin>> nooffriends>> bob>> alice>> changetime;
ll friends[nooffriends];
for(i=0;i<nooffriends;i++)
{
cin>> friends[i];
}
sort(friends,friends+nooffriends);
ll ans=0,f=friends[nooffriends-1];
if(bob<f)
f=lower_bound(friends,friends+nooffriends,bob);
for(i=0;i<nooffriends;i++)
{
friends[i]
=-1;
}
bob*=-1;
if(bob>friends[nooffriends-1])
{
ll f1=(lower_bound(friends,friends+nooffriends,bob))(-1);
if(abs(((-1)*bob)-f1)<abs(((-1)bob)-f))
f=f1;
}
bob
=-1;
ans+=abs(bob-f);
ans+=abs(f-alice);
ans+=changetime;
cout << ans << “\n”;
}
return 0;
}

a = int(input())
N,a,b,c = map(int, input().split())
def closest(lst, K):
return lst[min(range(len(lst)), key = lambda i: abs(lst[i]-K))]
lst = [1,6]
K = b
go = closest(lst,K)
g1 = abs(K - go) *1
want = abs(go - a) * 1
total = g1 + want + c
print(total)

This question seems to be inspired from one of the recent codeforces problem :stuck_out_tongue:

What is wrong with this code?
It shows TLE error.

#include <bits/stdc++.h>
using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long t;
cin>>t;

while(t--){
  long long time=0;
  long long min=INT_MAX;
  long long n,a,b,c;
  cin>>n>>a>>b>>c;
  if(b-a>=0){
    time=b-a+c;}
  else if(b-a<0){
    time=a-b+c;
  }
  long long i=0;
  while(n--){
    
    long long a[n];
    cin>>a[i];
    time=time+2*a[i];
    if(time<=min){
      min=time;
    }
    else if(time>INT_MAX){
      min=time;
    }
    time=time-2*a[i];
    i++;
    
  }
  cout<<min-2*b<<endl;

}
}

All the outputs are correct but why iam getting Time limit exceeded problem…Pls help…

#include

using namespace std;
int main()
{
long long int x,uu,t,n,a,i,b,c;
long long int f[100];
long long p[100];

cin>>t;
while(t–)
{
cin>>n>>a>>b>>c;
for(i=0;i<n;i++)
{
long long int element;
cin>>element;
p[i]=element;
int distance=abs(element-b);
f[i]=distance;
}
sort(f,f+n);
long long int fd=f[0];
int flag=0;
uu=0;
for(int it=0;it<n;i++)
{

        if(abs((p[it]-fd)==b))
        {
            uu=p[it];
            flag=1;
            break;
        }
        if(flag==1)
        break;
    }
    x=0;
    x=fd+c+(uu-a);

    cout<<x<<endl;


}



return 0;

}

why this is showing wrong ans??

#include<bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < n; i++)
#define mod 1000000007
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

#define vi vector
#define vii vector
#define ll long long
#define INF 1000000000
#define endl ‘\n’

using namespace std;

int main()
{
fastio;
cin.tie(0);
cout.tie(0);
short t;
int n,a,b,c;
int ma;
ll ans;
cin>>t;
while(t–)
{

    cin>>n>>a>>b>>c;
    int f[n];
    ans=abs(b-a)+c;

    ma=INT_MAX;
    a=max(a,b);
    b=min(a,b);
    for(int i=0;i<n;i++)
    {
        cin>>f[i];

    }
    for(int i=0;i<n;i++)
    {
        if(f[i]<=a && f[i]>=b){ ma=0; break;  }
      
          if(f[i]<b)
            {
                ma=min(ma,b-f[i]);
            }
            else
            {
               
                    ma=min(ma,f[i]-a);
                
            }
    }
    ans=ans+(2*ma);
    cout<<ans<<endl;




}




return 0;
}

tried to prform the operation all friends while taking input as well but that was showing TLE?

Here’s my code- It’s working perfecting fine for the given constraints in my machine but codechef says wrong answer(WA). Can anyone explain what’s wrong with my code?

Edited*

https://www.codechef.com/viewsolution/29193775

here’s the link of my submission, can you explain please?

Please either format your code or link to your submission - the forum software has mangled it and it won’t compile! :slight_smile:

Edit:

Why are you using arr[0] but no other indices of arr?

1 Like

I’ve edited my previous comment now, please help.

        long long int arr[n];
        cin >> n >> a >> b >> c;

You’re allocating a dynamic array of size n before you’ve read in the value of n.

1 Like

Then why it is working completely fine on my machine and even on codechef when I provide custom input(same inputs given in the question) and even answer is correct.

There’s Undefined Behaviour for you :man_shrugging:

2 Likes

Sorry, I didn’t get it. :grimacing:

Which one exactly? Would appreciate if you can share😅