In this HackerEarth Left or Right problem solution, A country X consists of N cities numbered 0 through N - 1. The map of this country can be represented as a cycle — for each valid i, city i has exactly two neighboring cities (i + 1)%N and (i - 1 + N)%N.
The cities in the country are broadly categorized into different types. For each valid i, the type of city i is denoted by Ai.
A person called Suarez wants to travel between some pairs of cities. You are given Q queries. In each query, Suarez wants to travel from city number Y to a city of type Z. Also, he wants to travel only in a given direction along the cycle.
The direction is represented by a letter — L or R. If it's L, Suarez may only move from city i to city (i - 1 + N)%N for each valid i. If it's R, he may only move from city i to city (i + 1)%N.
You need to find the minimum number of steps Suarez needs to take to reach a city of type Z if he starts moving from city Y in the given direction (he can take zero steps). In one step, Suarez can move from his current city to a neighboring city.
If Suarez can never reach a city of type Z for a given query, print 1 instead.
HackerEarth Left or Right problem solution.
import java.io.*;
import java.util.*;
import java.math.*;
import java.util.concurrent.*;
public final class new_sol
{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static FastScanner sc=new FastScanner(br);
static PrintWriter out=new PrintWriter(System.out);
static Random rnd=new Random();
static List<Integer> list=new ArrayList<>();
static int maxn=(int)(2e5+5);
public static void main(String args[]) throws Exception
{
int n=sc.nextInt(),q=sc.nextInt();int[] a=new int[n];
for(int i=0;i<n;i++)
{
a[i]=sc.nextInt();
list.add(a[i]);
}
Collections.sort(list);int[] rank=new int[maxn];
for(int i=0;i<maxn;i++)
{
rank[i]=Collections.binarySearch(list,i);
}
int[][] l_dis=new int[n+1][n+1],r_dis=new int[n+1][n+1];
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
l_dis[i][j]=r_dis[i][j]=Integer.MAX_VALUE;
}
}
for(int i=0;i<n;i++)
{
int pos=i,steps=0;
while(steps<n)
{
int now=rank[a[pos]];
r_dis[i][now]=Math.min(r_dis[i][now],steps);
steps++;pos=(pos+1)%n;
}
pos=i;steps=0;
while(steps<n)
{
int now=rank[a[pos]];
l_dis[i][now]=Math.min(l_dis[i][now],steps);
steps++;pos=(pos-1+n)%n;
}
}
while(q>0)
{
int idx=sc.nextInt(),type=rank[sc.nextInt()];char ch=sc.next().charAt(0);
int ans=-1;
if(ch=='L' && type>=0)
{
ans=l_dis[idx][type];
}
else if(ch=='R' && type>=0)
{
ans=r_dis[idx][type];
}
out.println(ans<Integer.MAX_VALUE?ans:-1);
q--;
}
out.close();
}
}
class FastScanner
{
BufferedReader in;
StringTokenizer st;
public FastScanner(BufferedReader in) {
this.in = in;
}
public String nextToken() throws Exception {
while (st == null || !st.hasMoreTokens()) {
st = new StringTokenizer(in.readLine());
}
return st.nextToken();
}
public String next() throws Exception {
return nextToken().toString();
}
public int nextInt() throws Exception {
return Integer.parseInt(nextToken());
}
public long nextLong() throws Exception {
return Long.parseLong(nextToken());
}
public double nextDouble() throws Exception {
return Double.parseDouble(nextToken());
}
}
0 Comments