Wsrtjtyk

The first line contains the number of marathons t < 100. Each marathon is specified by three lines. The first line contains the number of runners 1 < n <= 40000. The second line is a permutation of the starting numbers 1,...,n which represents the order in which the runners passed the starting line. Finally, the third line is a permutation which represents the finishing order. For each marathon output one line which contains the minimal number of overtakings that have happend during the race.

So for example

I really don't know how I can create a random permutation 1 < n and how to find out then how many overtakings took place. For the latter I would check how many numbers are bigger than the next, i.e. if 4 > 3 then I increase an int overtaking++;

import java.util.Scanner;



public class MarathonMovement {



   public static void main(String args) {



       Scanner NoM = new Scanner(System.in); // Number of marathons

       int t = NoM.nextInt();



       Scanner NoR = new Scanner(System.in); // First line: Number of runners

       int n = NoR.nextInt();



       // Second line: Permutation of starting numbers representing the order in which the runners passed the starting line



       // Third line: Permutation which represents finishing order



        int overtakings = 0;



        for (int i = 0; i < n; i++){

           if {

               // logic

               overtakings++;

           }

        }



       for(int x = 0; x < t; x++){

          System.out.println("at least" + overtakings + " overtaking(s)");

       }

   }

}

For the first part of your question (generate a random permutation), you can use the method Collections.shuffle:

    List<Integer> start = new ArrayList<>();

    for (int i = 0; i < n; ++i) {

        start.add(i + 1);

    }

    List<Integer> finish = new ArrayList<>(start);

    Collections.shuffle(finish);

To count the overtakings:

    int overtakings = 0;

    for (int i = 1; i < n; ++i) {

        if (finish.get(i) < finish.get(i-1)) {

            ++overtakings;

        }

    }

If I understand this task correctly, then this is my solution:

public static void main(String... args) {

    try (Scanner scan = new Scanner(System.in)) {

        int t = scan.nextInt();



        for (int i = 0; i < t; i++) {

            int n = scan.nextInt();

            int arr = new int[n];

            Set<String> uniqueOvertaking = new HashSet<>();



            for (int j = 0; j < n; j++)

                arr[j] = scan.nextInt();

            for (int j = 0; j < n; j++) {

                int val = scan.nextInt();



                if (arr[j] != val)

                    uniqueOvertaking.add(Math.min(arr[j], val) + "->" + Math.max(arr[j], val));

            }



            int res = uniqueOvertaking.size() == n ? uniqueOvertaking.size() - 1 : uniqueOvertaking.size();

            System.out.println("at least " + res + " overtaking(s)");

        }

    }

}

Output:

at least 1 overtaking(s)

at least 5 overtaking(s)

at least 3 overtaking(s)