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