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. 
