PROBLEM LINK:
Author: Noob Learner
Tester: Noob Learner
Editorialist: Noob Learner
DIFFICULTY:
EASY
PREREQUISITES:
Greedy
PROBLEM:
Chef and Chefina are playing a game in which they have to pick coins together. You are given the position of N coins and it is given that the position of each of the coins is unique.
Chef stands at position 1 and Chefina stands at position 10^6. Both of these positions don’t contain any coins (These are initial positions of Chef and Chefina).
Both the players can move from any position say x to x+1 or x-1 in 1 second. If any player comes to a position where a coin is present, they picks it instantly.
What is the minimum time to pick all the coins such that each coin is picked by either Chef or Chefina or by both of them.
QUICK EXPLANATION:
We will go with greedy approach as the test constraints are small up to 10^6.
so keeping two pointers we will travers the array from both sides and get the max answer.
EXPLANATION:
We will traverse the array by using two pointers. Keeping 1st pointer at the initial location of the array and 2nd at the end of the array. The 1st pointer will go in forward direction from x to x+1,x+2… up to 10^3.
The 2nd pointer will move in backward direction form x to x-1,x-2… from 10^6 to 10^3-1.
After that we will compare both the pointers and the pointer which has travelled the maximum will be our answer
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
void tc()
{
ll n;
cin>>n;
ll z[n];
for(ll i=0;i<n;i++)
{
cin>>z[i];
}
int cnt=0,cnt1=0;
vector t;
vector j;
for(ll i=0;i<n;i++)
{
if(z[i]>=0 && z[i]<=500000)
{
t.push_back(z[i]);
cnt++;
}
else
{
j.push_back(z[i]);
cnt1++;
}
}
if(cnt==n)
{
ll to=*max_element(t.begin(), t.end());
cout<<to-1<<"\n";
}
else if(cnt1==n)
{
sort(j.begin(),j.end());
ll ans= 1000000 - j[0];
cout<<ans<<"\n";
}
else
{
int to=*max_element(t.begin(), t.end());
sort(j.begin(),j.end());
int xd=j[0];
to = to-1;
xd = 1000000 - xd;
int ans;
ans = max(to,xd);
cout<<ans<<"\n";
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
tc();
}
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
void tc()
{
ll n;
cin>>n;
ll z[n];
for(ll i=0;i<n;i++)
{
cin>>z[i];
}
int cnt=0,cnt1=0;
vector t;
vector j;
for(ll i=0;i<n;i++)
{
if(z[i]>=0 && z[i]<=500000)
{
t.push_back(z[i]);
cnt++;
}
else
{
j.push_back(z[i]);
cnt1++;
}
}
if(cnt==n)
{
ll to=*max_element(t.begin(), t.end());
cout<<to-1<<"\n";
}
else if(cnt1==n)
{
sort(j.begin(),j.end());
ll ans= 1000000 - j[0];
cout<<ans<<"\n";
}
else
{
int to=*max_element(t.begin(), t.end());
sort(j.begin(),j.end());
int xd=j[0];
to = to-1;
xd = 1000000 - xd;
int ans;
ans = max(to,xd);
cout<<ans<<"\n";
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
tc();
}
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
void tc()
{
ll n;
cin>>n;
ll z[n];
for(ll i=0;i<n;i++)
{
cin>>z[i];
}
int cnt=0,cnt1=0;
vector t;
vector j;
for(ll i=0;i<n;i++)
{
if(z[i]>=0 && z[i]<=500000)
{
t.push_back(z[i]);
cnt++;
}
else
{
j.push_back(z[i]);
cnt1++;
}
}
if(cnt==n)
{
ll to=*max_element(t.begin(), t.end());
cout<<to-1<<"\n";
}
else if(cnt1==n)
{
sort(j.begin(),j.end());
ll ans= 1000000 - j[0];
cout<<ans<<"\n";
}
else
{
int to=*max_element(t.begin(), t.end());
sort(j.begin(),j.end());
int xd=j[0];
to = to-1;
xd = 1000000 - xd;
int ans;
ans = max(to,xd);
cout<<ans<<"\n";
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
tc();
}
}