Minimum number of steps to move from one city to another
Okay, found problem online and solved it. The trick to the problem (as with most problems) lies in the constraints:



There are a lot of queries, but a small amount of cities. It would seem more important to optimize answering a query time, which is usually done with some precalculation or caching.

In this case, we can think that as there are at most 3000 cities, there is at most 3000 distinct city types. So all queries that don´t ask for an invalid city type (no city has that city type) will have one of those 3000 types. 

We can precalculate for all cities, the query of going to right or left for each of these types, ending with a O(cities * distinct types * 2) complexity, which would be 3000 * 3000 * 2 at most, much better than the original 500000 * 3000.

Then for each query, if the type of city is a valid type (at least one of the cities has it), we have already preprocessed the answer and can answer in O(1). If it isn´t, we just answer with -1.

Another hint is the topic of the problem, which is for practicing multi dimentional arrays. We use this to store the calculation of all valid queries to then answer in O(1).

I advice you to try coding the problem again with these hints.

If you get stuck:


   Even though city types can go up to 200000, we can map them to values between 1 and 3000, because we only have 3000 cities.


And if you still can´t solve it, here is my solution:


  
        Scanner kb=new Scanner(System.in);
        int cities = kb.nextInt();
        int queries = kb.nextInt();

        int types[] = new int[cities];
        HashSet uniqueTypes = new HashSet();

        for (int i = 0; i &lt; cities; i++) {
            types[i] = kb.nextInt();
            uniqueTypes.add(types[i]);
        }

        HashMap mapping = new HashMap();

        Integer idx = 0;
        for (Integer type: uniqueTypes) {
            mapping.put(type, idx++);
        }

        for (int i = 0; i &lt; cities; i++) {
            types[i] = mapping.get(types[i]);
        }

        int closestRight[][] = new int[cities][cities];
        int closestLeft[][] = new int[cities][cities];

        for(int i = 0; i &lt; cities; i++) {
            for (int j = 0; j &lt; cities; j ++) {
                closestRight[i][j] = closestLeft[i][j] = cities + 1; 
            }
        }

        for(int i = 0; i &lt; cities; i++) {
            for (int j = 0; j &lt; cities; j ++) {
                int leftIndex = ((i - j) + cities) % cities;
                int rightIndex = (i + j) % cities;
                int rightCityType = types[rightIndex];
                int leftCityType = types[leftIndex];

                closestRight[i][rightCityType] = Math.min(closestRight[i][rightCityType], j);
                closestLeft[i][leftCityType] = Math.min(closestLeft[i][leftCityType], j);

            }
        }

        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(new
        FileOutputStream(java.io.FileDescriptor.out), "ASCII"), 512);

        for (int i = 0; i &lt; queries; i++) {
            int city = kb.nextInt();

            int destinationType = kb.nextInt();

            if (mapping.get(destinationType) == null) {
                out.write("-1" + "\n");
                continue;
            }

            destinationType = mapping.get(destinationType);

            if (kb.next().charAt(0) == 'L') {
                out.write(closestLeft[city][destinationType] + "\n"); 
            } else {
                out.write(closestRight[city][destinationType] + "\n"); 
            }


        }

        out.flush();