(UVA) Stacking Boxes - Solution

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

The problem wants us to find the longest nesting string and the length of that nesting string. For this reason, Dynamic Programming was used to find the answer, applying the concept of the Longest Increasing Sequence (LIS).

First, we manipulate the entry in order to sort it. It allows us to know that box n can fit inside box n+1, but box n+1 will not fit inside box n. Then, we only need to apply the LIS approach to find the answer.


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

class Main {
    public List<Box> boxes;
    public List<Integer> matches;
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
       
        while (sc.hasNext()) {
            int numBoxes = sc.nextInt();
            int dimension = sc.nextInt();
           
            boxes = new ArrayList<>();
            for (int i = 0; i < numBoxes; i++) {
                boxes.add(i, new Box((i+1)));
            }       
           
            for (int i = 0; i < numBoxes; i++) {
                List<Integer> list = new ArrayList<>();
                for (int j = 0; j < dimension; j++) {
                    list.add(sc.nextInt());
                }
                // sort the dimensions of the box
                Collections.sort(list);
                boxes.set(i, new Box((i+1),list));
            }
            // sort the boxes
            Collections.sort(boxes);
           
            // list to keep in how many boxes the current box fits
            matches = new ArrayList<>();
            for (int i = 0; i < numBoxes; i++) {
                matches.add(i, 1);
            }
           
            // list to keep the order of the boxes that fit inside another one
            ArrayList<ArrayList<Integer>> order = new ArrayList<>();
            for (int i = 0; i < numBoxes; i++) {
                order.add(i, new ArrayList<Integer>());
                order.get(i).add(boxes.get(i).id);
            }
           
            // LIS
            for (int i = numBoxes-1; i >= 0; i--) {
                List<Integer> list1 = boxes.get(i).box;
                int maxMatch = matches.get(i);
                for (int j = i+1; j < numBoxes; j++) {
                    boolean fit = true;
                    List<Integer> list2 = boxes.get(j).box;
                    for (int k = 0; k < dimension; k++) {
                        // if one dimension does not fit, break
                        if (list1.get(k) >= list2.get(k)) {
                            fit = false;
                            break;
                        }
                    }
                    // if box i fits inside box j
                    if (fit) {
                        int count = matches.get(i) + matches.get(j);
                        if (count > maxMatch) {
                            maxMatch = count;
                            order.set(i, new ArrayList<Integer>());
                            order.get(i).add(boxes.get(i).id);
                            for (int k = 0; k < order.get(j).size(); k++) {
                                order.get(i).add(order.get(j).get(k));
                            }
                        }
                    }
                }               
                matches.set(i, maxMatch);
            }
           
            // find the length of longest nesting string
            int maxMatch = 0;
            for (int i = 0; i < numBoxes; i++) {
                maxMatch = Math.max(maxMatch, matches.get(i));
            }
           
            System.out.println(maxMatch);
            // find the longest nesting string
            for (int i = 0; i < order.size(); i++) {
                if (order.get(i).size() != maxMatch) {
                    continue;
                }
                for (int j = 0; j < order.get(i).size(); j++) {
                    if (j == order.get(i).size()-1) {
                        System.out.println(order.get(i).get(j));
                        break;
                    }
                    System.out.print(order.get(i).get(j) + " ");
                }
                break;
            }
        }
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class Box implements Comparable<Box> {
    int id;
    List<Integer> box;
   
    public Box(int id) {
        this.id = id;
        box = new ArrayList<>();
    }
   
    public Box(int id, List<Integer> box) {
        this.id = id;
        this.box = box;
    }
   
    public int compareTo(Box b) {
        for (int i = 0; i < b.box.size(); i++) {
            if (this.box.get(i)-b.box.get(i) == 0) {
                continue;
            }
            return this.box.get(i)-b.box.get(i);
        }
        return 0;
    }
}