(UVA) Start Grid - Solution 1

Brute Force was used to solve this problem.

For every competitor in the starting grid, there is a list of all the competitors that are in a better position. Then, by using this list for every competitor in the finishing grid, it is possible to check who and how many competitors were overtaken.


import java.io.*;
import java.util.*;

class Main {
    public static int reader(BufferedReader br) throws NumberFormatException, IOException {    
        int n;
        int resp = 0;    
     
        while (true) {        
            n = br.read();        
            if (n >= '0' && n <= '9') {
                break;
            }
        }
          
        while (true) {        
            resp = resp*10 + n-'0';        
            n = br.read();        
            if (n < '0' || n > '9') {
                break;    
            }
        }
     
        return resp;    
    }
  
    public static void process() throws NumberFormatException, IOException { 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      
        String line = br.readLine();
        while (line != null) {
            int numCompetitors = Integer.parseInt(line);
          
            ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
            for (int i = 0; i <= numCompetitors; i++) {
                list.add(i, new ArrayList<Integer>());
            }
          
            ArrayList<Integer> previousToCompetitor = new ArrayList<Integer>();
            for (int i = 0; i < numCompetitors; i++) {
                int competitorID = reader(br);
                ArrayList<Integer> tmp = new ArrayList<Integer>(previousToCompetitor);
                list.set(competitorID, tmp);
                previousToCompetitor.add(competitorID);
            }

            int count = 0;
            HashSet<Integer> previous = new HashSet<Integer>();
            for (int i = 0; i < numCompetitors; i++) {
                int competitorID = reader(br);
                previousToCompetitor = list.get(competitorID);
                for (int j = 0; j < previousToCompetitor.size(); j++) {
                    if (!previous.contains(previousToCompetitor.get(j))) {
                        count++;
                    }
                }
                previous.add(competitorID);
            }
          
            System.out.println(count);
          
            line = br.readLine();
        }
                  
        return;
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}