TRVLCHEF - EDITORIAL

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. :slight_smile:

8 Likes

Hey @taran_1407 Can u please see where i am going wrong. I think I have pity much implemented the same logic but only the way to implement is different.
Logic :- First i sort the array except the first element which was taken separately in variable x. After that i calculated prefix and suffix arrays where prefix[i] denotes whether it’s possible to reach the ith vertex from the 2nd vertex(first one is 1) , same goes for suffix[i] which denotes whether it’s possible to reach from the ith vertex to the end. Now i will iterate over all possible vertices(2 to n) and check if that vertex would be the one taken just after the first vertex and try both the left and right directions and if the answer is possible from any of the ways then flag gets set.
Solution link :- https://www.codechef.com/viewsolution/23726616

Isn’t this question asking to find if the graph is a Hamiltonian path?

Can someone explain how we are managing to solve this question in less than exponential time in spite of the Hamiltonian path problem being NP-complete?

What property of the graph allows it?

3 Likes

The graph you are talking about can be considered as a fully connected graph where each edge (u,v) has weight equal to abs( value(u) - value(v) ). As it is a fully connected graph any permutation of all the vertices of the graph will qualify as a valid hamiltonian path. You should probably read the original Hamiltonian Path problem once.

The constraints given on the graph and movement from one vertex to another makes it solvable.

In the hamiltonian problem, you’re given a graph, and asked to find a path that visits all of it’s vertices, without any constraints on which vertex you can go to (following the edges, ofcourse).

A fair example can be, finding a hamiltonian path of a connected graph of N vertices, given that the graph is complete (every pair of vertices are connected by an edge).
This problem is no longer NP-Complete, as you can easily find a hamiltonian path, given the constraint that the graph is complete.

2 Likes

Why are the small test cases showing WA using simple dfs i.e you start form node 1 and if the node has temperature difference less than d you visit it. At the end if all nodes are visited then it should be yes else no.

I have applied the same procedure as editorial but I m getting wrong ans. Can somebody please look into my Solution.
Thanks in advance

I believe there would be some error in code cause if the dfs approach is correct then in worst case the time complexity would be O(n!) and n=1000 for sub-task. Hence it would give TLE.

I had tried the same procedure in editorial and I had WA. I am pretty sure you are missing something. After 3 hr of trying different methods to code the same thing, I succeeded finally.
Sorry, I don’t have time to debug yours, but I have working code with comments for you to understand.
Here’s the link:
My solution with comments for the above editorial

1 Like

I think everything is correct except pos = arr[i].index;.
And the other one thing is missing that you are not setting result = true after checking for one side.

1 Like

Its ok, no problem. Thanks for the help :slight_smile:

Oh yes I forgot. Thanks for pointing out the error.

my logic:-

  1. First take the first element in a separate variable say x.
  2. now sort the n-1 elements.
  3. check if we can go to first element of the sorted array if yes then traverse the whole array, if we can reach the last element in the array then ans is yes otherwise check if we can go to the last element in the array from x, if yes traverse the array backwards if we can reach the first element then ans is yes otherwise no.
    please tell me why is this incorrect? On what test case it will fail?
1 Like

@lakshayv1 u are only considering the case when the first element is either at first and last position of sorted elements(ie when its travel is possible to the first or last element). There’s also one more case when the first element lies in the middle, then it can go left and right and traverse the whole array. In this case, note that its not always possible to return back from left/right end position to the position after first element, so to take care of that move to the left/right end in steps of 2 ie x, x-2, x-4… or x,x+2,x+4 resp. (so that there’s path to return back) and after reaching the end, move back to the other end. If a path does not exist then there’s no way to traverse the whole array.

I used the same logic, it won’t work you have to leave a path for returning back