Myujth

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)