PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Hasan Jaddouh
Tester: Aleksa Plasvic
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Observations and Optimality.
PROBLEM:
Chef wants to visit all N cities with temperatures of cities given in each city in array C, starting from city 1, not visiting any city more than one, where chef can go from city x to city y only if |C_x - C_y| \leq D where D is the temperature difference chef can tolerate, is given in the problem. We have to determine whether the chef will be able to visit all the cities or not.
QUICK EXPLANATION
- Sorting all cities by temperature, we can now see, that from each city, we have to start from a city (not necessarily in the beginning) and visit all cities. Now, if C_{x+1} - C_x > D, then from city at position x, we cannot visit any city later than x+1.
- It can be seen, that to cover all elements starting (possibly) from a middle element and covering all positions. The ideal strategy is to move from the start position to one end of the array and then reaching the other end.
- Suppose we choose to reach the left end. The ideal strategy would be to move from x to x-2 until we can reach the leftmost position and then moving to the nearest unvisited position until we visit all positions. We leave one position unvisited so that we can come back and move toward the right end. If at any step we cannot move to next position in this path, it is not possible to visit all. We try to fix both ends as first end one by one and if the answer exists for any case, We can reach all cities.
EXPLANATION
First of all, to ease out the movement from cities, let us sort cities by temperature. Now, If |C_{x+1}-C_x| > D, chef cannot move from any city before x city to the right. Same goes for moving to the left.
Now, by sorting, our first city can go to any position, say position st. So now, the problem is, starting from position st, visit all positions without visiting each position more than once.
Let us assume that st is at the left end. So, naturally, it will make sense to go to the city with just higher temperature which is unvisited, eventually reaching the right end.
But, if the start point is not at one of the ends, this approach may face trouble, since after reaching to one end, all the cities between city st and the leftmost city are already visited, but we need to visit cities to the right of st. Clearly, we need to reach one end, while keeping a path for returning back so that we can go to the other end.
Also, the ideal strategy would be to start from st, move toward one end while keeping the way for returning and then moving to the nearest unvisited position toward the other end.
In case we move from city x to city x-1 to city x+1 where city x-1 is not first city, then to visit city x-2, we’ll need to move directly from city x+1. For this case, it is better to move from city x to city x-1 to city x+1 to city x+2 as if we can reach from city x+1 to city x-2, we can reach from city x to city x-1 too. Hence, if a valid path exists, the path of this form will always exist.
Trying for the left end now, chef follows path x, x-2, x-4 and so on till it reaches the first element (move from the city 2 to 1 if required). Now, from city 1, move to closest unvisited city to the right. If in this path, if city x and city y are adjacent cities and |C_x - C_y| > D, this path is not valid. Similar path for choosing the right end now.
If either of the paths is valid, the answer is YES.
Time Complexity
Time complexity is O(N*logN) per test case due to sorting.
SOLUTIONS:
Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int T;
int n,d;
int arr[100100];
int sm_n=0;
int main(){
//freopen("03.txt","r",stdin);
//freopen("03o.txt","w",stdout);
T=readIntLn(1,1000);
while(T--){
n=readIntSp(1,100000);
d=readIntLn(0,1000000000);
sm_n += n;
assert(sm_n<=1000000);
for(int i=0;i<n;i++){
if(i==n-1){
arr[i]=readIntLn(0,1000000000);
} else {
arr[i]=readIntSp(0,1000000000);
}
}
if(n==1){
cout<<"YES"<<endl;
continue;
}
int vl=arr[0];
sort(arr,arr+n);
for(int i=0;i<n;i++){
if(arr[i]==vl){
vl=i;
break;
}
}
int left=3,right=3;
for(int i=vl-1;i>=0;i--){
if(arr[i+1]-arr[i] > d){
left &= 2;
break;
}
}
for(int i=vl+1;i<n;i++){
if(arr[i]-arr[i-1] > d){
right &= 2;
break;
}
}
for(int i=vl-2;i>=0;i--){
if(arr[i+2]-arr[i] > d){
left &= 1;
break;
}
}
if(vl > 0 && arr[1]-arr[0] > d){
left &= 1;
}
if(vl < n-1 && arr[n-1] - arr[n-2] > d){
right &= 1;
}
for(int i=vl+2;i<n;i++){
if(arr[i]-arr[i-2] > d){
right &= 1;
break;
}
}
if(vl >0 && vl < n-1){
if(arr[vl+1] - arr[vl-1] > d){
cout<<"NO"<<endl;
continue;
}
}
if((left & 2) && (right & 1)){
cout<<"YES"<<endl;
continue;
}
if((left & 1) && (right & 2)){
cout<<"YES"<<endl;
continue;
}
cout<<"NO"<<endl;
}
assert(getchar()==-1);
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
const int maxN = 100010;
int n,d;
int c[maxN];
int sum = 0;
void solve()
{
scanf("%d%d",&n,&d);
assert(n>0 && n<=1e5);
assert(d>=0 && d<=1e9);
sum+=n;
for (int i=1;i<=n;i++){
scanf("%d",&c[i]);
assert(c[i]>=0 && c[i]<=1e9);
}
int x = c[1];
sort(c+1,c+n+1);
int poz = 0;
for (int i=1;i<=n;i++)
if (c[i]==x) poz = i;
for (int i=1;i<n;i++)
if (c[i+1]-c[i]>d)
{
printf("NO\n");
return;
}
if (poz==1 || poz==n)
{
printf("YES\n");
return;
}
int ok = 1;
for (int i=poz+1;i<=n;i++)
if (c[i]-c[i-2]>d) ok=0;
if (ok)
{
printf("YES\n");
return;
}
ok = 1;
for (int i=poz-1;i>0;i--)
if (c[i+2]-c[i]>d) ok = 0;
if (ok) printf("YES\n"); else
printf("NO\n");
}
int main()
{
int t;
cin>>t;
assert(t>=1 && t<=1000);
while(t--)
solve();
assert(sum<=1e6 && sum>0);
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
//Solution Credits: Taranpreet Singh
class TRVLCHEF{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni();
long d = nl();
long[] c = new long[n];
for(int i = 0; i< n; i++)c[i] = nl();
long tmp = c[0];
Arrays.sort(c);
boolean check = check(c, d, tmp);
for(int i = 0, j = n-1; i< j; i++, j--){
long x = c[i];
c[i] = c[j];
c[j] = x;
}
check|= check(c, d, tmp);
pn((check)?"YES":"NO");
}
boolean check(long[] c, long d, long st){
int pos = -1;
for(int i = c.length-1; i>= 0; i--)if(c[i]==st)pos = i;
boolean v = true;
boolean[] vis = new boolean[c.length];
vis[pos] = true;
while(pos>=1){
int nxt = Math.max(0, pos-2);
v &= Math.abs(c[pos]-c[nxt]) <= d;
pos = nxt;
vis[pos] = true;
}
for(int i = 0; i< c.length; i++){
if(!vis[i]){
v &= Math.abs(c[i]-c[pos]) <= d;
pos = i;
}
}
return v;
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
long mod = (long)1e9+7, IINF = (long)1e18;
final int INF = (int)1e9, MX = (int)3e5+2;
DecimalFormat df = new DecimalFormat("0.00000000000");
double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
static boolean multipleTC = true, memory = false;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
int T = (multipleTC)?ni():1;
//Solution Credits: Taranpreet Singh
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
if(memory)new Thread(null, new Runnable() {public void run(){try{new TRVLCHEF().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
else new TRVLCHEF().run();
}
long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
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, If it differs. Suggestions are always welcomed. 
