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


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());
}
}