Shortest Route Codechef Solution | AskTheCode

June Long Challenge 2021 Solution | Shortest Route Solution (SHROUTE) | AskTheCode

---

Problem:

There are N cities in Chefland numbered from 1 to N and every city has a railway station. Some cities have a train and each city has at most one train originating from it. The trains are represented by an array A, where Ai=0 means the i-th city doesn't have any train originating from it, Ai=1 means the train originating from the i-th city is moving right (to a higher numbered city), and Ai=2 means the train originating from the i-th city is moving left (to a lower numbered city).

Each train keeps on going forever in its direction and takes 1 minute to travel from the current station to the next one. There is a special station at city 1 which lets travellers instantaneously teleport to any other station that currently has a train. Teleportation and getting on a train once in the city both take 0 minutes and all trains start at time 0.

There are M travellers at city 1, and the i-th traveller has destination city Bi. They ask Chef to guide them to teleport to a particular station from which they can catch a train to go to their destination in the least time possible. In case it's not possible for a person to reach his destination, print −1.

Note: The input and output of this problem are large, so prefer using fast input/output methods.

---

Input:

• The first line contains an integer T, the number of test cases. Then the test cases follow.

• Each test case contains three lines of input. The first line contains two integers N, M.

• The second line contains N integers A1,A2,…,AN.

• The third line contains M integers B1,B2,…,BM.

---

Output:

For each test case, output M space-separated integers C1,C2,…,CM, where Ci is the minimum time required by the i-th traveller to reach his destination and if the i-th traveller can't reach his destination, Ci=−1.

---

Sample Input:

3
5 1
1 0 0 0 0
5
5 1
1 0 0 0 2
4
5 2
2 0 0 0 1
3 1

---

Sample Output:

4
1
-1 0

---

EXPLANATION:

Test Case 1: The only person takes the train from station 1 and hence takes |5−1|=4

minutes to reach his destination.

Test Case 2: The only person takes the train from station 5 and hence takes |5−4|=1

minute to reach his destination.

Test Case 3: Since no train passes station 3, it's impossible for the first person to reach his destination and since the second person is already at station 1, it takes him 0 minutes to reach his destination.

---

Code:

In C++ :

#include<bits/stdc++.h>
using namespace std;
main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,m;
		cin>>n>>m;
		int a[n+1],b[m+1];
		unordered_map<int,int>n1,n2;
		int poi=-1;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			if(a[i]==1)
			{
				poi=i;
			}
			n1[i]=poi;
		}
		for(int i=1;i<=m;i++)
		cin>>b[i];
		int pti=-1;
		for(int i=n;i>0;i--)
		{
			if(a[i]==2)
			pti=i;
			n2[i]=pti;
		}
		for(int i=1;i<=m;i++)
		{
			if(b[i]==1)
			{
				cout<<"0 ";
			}
			else if(n1[b[i]]==-1&&n2[b[i]]==-1)
			cout<<"-1 ";
			else if(n1[b[i]]!=-1&&n2[b[i]]!=-1)
			cout<<fmin(b[i]-n1[b[i]],n2[b[i]]-b[i])<<" ";
			else if(n1[b[i]]!=-1)
			cout<<b[i]-n1[b[i]]<<" ";
			else
			cout<<n2[b[i]]-b[i]<<" ";
		}
		cout<<endl;
	}
}

---

In Java :

import java.io.*;
import java.util.Arrays;
import java.util.*;
public class Main {
	
	
	public static void main(String[] args)throws Exception{
		 BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
		int t=Integer.parseInt(s.readLine());
		while(t--!=0){
			String[] s1=s.readLine().split(" ");
			int n=Integer.parseInt(s1[0]);
			int m=Integer.parseInt(s1[1]);
			int[] a=new int[n];
			int[] b=new int[m];
			int[] c=new int[n];
			
			String[] s2=s.readLine().split(" ");
			String[] s3=s.readLine().split(" ");
			int left=-1,right=-1,cm=Integer.MAX_VALUE;
			for(int i=0;i<n;i++) {
				a[i]=Integer.parseInt(s2[i]);
				if(a[i]==1) cm=0;
				else if(cm!=Integer.MAX_VALUE) cm++;
				c[i]=cm;
				
			}
			/*for(int i=0;i<n;i++) {
				
			}*/
			cm=Integer.MAX_VALUE;
			for(int i=n-1;i>=0;i--) {
				if(a[i]==2) cm=0;
				else if(cm!=Integer.MAX_VALUE) cm++;
				
				c[i]=Math.min(cm, c[i]);
				
			}
			BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
			for(int i=0;i<m;i++) {
				int k=Integer.parseInt(s3[i]);
				k--;
				int x=c[k];
				if(x==Integer.MAX_VALUE) x=-1;
				if(k==0) x=0;
				output.write(x+" ");
			}
			output.write("\n");
			output.flush();
		}
	}
}