(UVA) History Grading - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=142&page=show_problem&problem=47

The problem wants us to determine the length of the longest sequence of events in the student responses that are in correct chronological order relative to each other. For this reason, the solution below used Dynamic Programming to solve this problem, applying the concept of the Longest Increasing Subsequence. If you want to see more about this technique, click here.

Be aware about the input. If the correct chronological order is (3, 1, 2, 4, 9, 5, 10, 6, 8, 7), it means that:

• Event number 1 is in position number 3;
• Event number 2 is in position number 1;
• Event number 3 is in position number 2;
• Event number 4 is in position number 4;
• And so on...

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

class Main {
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        String line = br.readLine();
        int numEvents = Integer.parseInt(line);
       
        line = br.readLine();
        String[] s = line.split("\\s");
        EventInfo[] events = new EventInfo[numEvents];
        // read the chronological order of the events
        for (int i = 0; i < numEvents; i++) {
            // each event has a position and an event number
            events[i] = new EventInfo(Integer.parseInt(s[i])-1, (i+1));
        }
       
        line = br.readLine();
        while (line != null) {
            s = line.split("\\s");
            EventStudent[] eventsStudent = new EventStudent[numEvents];
            // read the chronological rank given by a student
            for (int i = 0; i < numEvents; i++) {
                // each event has a position, a number that will keep the largest subsequence, and an event number
                eventsStudent[Integer.parseInt(s[i])-1] = new EventStudent(Integer.parseInt(s[i])-1, 1, (i+1));
            }   
           
            for (int i = numEvents-1; i >= 0; i--) {
                int maxCount = 1;
                for (int j = i+1; j < numEvents; j++) {
                    // compare positions
                    if (events[eventsStudent[i].eventNumber-1].eventPos < events[eventsStudent[j].eventNumber-1].eventPos) {
                        int count = eventsStudent[i].eventMatch + eventsStudent[j].eventMatch;
                        maxCount = Math.max(maxCount, count);
                    }
                }   
                eventsStudent[i].eventMatch = maxCount;
            }
           
            int max = -1;
            for (int i = 0; i < numEvents; i++) {
                max = Math.max(max, eventsStudent[i].eventMatch);
            }
           
            System.out.println(max);
           
            line = br.readLine();
        }
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class EventInfo implements Comparable<EventInfo> {
    int eventPos;
    int eventNumber;
   
    public EventInfo(int eP, int eN) {
        eventPos = eP;
        eventNumber = eN;
    }
   
    public int compareTo(EventInfo ei) {
        return this.eventNumber-ei.eventNumber;
    }
}

class EventStudent {
    int eventPos;
    int eventMatch;
    int eventNumber;
   
    public EventStudent(int eP, int eM, int eN) {
        eventPos = eP;
        eventMatch = eM;
        eventNumber = eN;
    }
}