Aufgabentext: https://soi.ch/contests/2016/round1/cablecar/

• Cable-Car Instanzen und Lösungen. Aufgabe 1 cable-10-100.txt cable-10-100-output.txt cable-50-10000.txt cable-50-10000-output.txt cable-100-1000000.txt cable-100-1000000-output.txt
• Cable-Car Aufgabe 2: cable2-100-1000-1000000.txt cable2-100-1000-1000000-output.txt

Achtung: Die Input-Datei war fehlerhaft, bitte laden Sie sich die neue Instanz-Datei herunter!

• cable3-1000-100000.txt cable3-1000-100000-output.txt

    public static void aufgabe3() throws IOException {
        Path datei = Paths.get("cable3-1000-100000.txt");
        // Speicher für die Ausgabe
        ArrayList<String> lines = new ArrayList<>();
        try (Scanner scanner = new Scanner(Files.newInputStream(datei))) {
            int anzahlFaelle = scanner.nextInt();
            for (int fall=0; fall<anzahlFaelle; fall++) {
                int maximum = 2;
                int m = scanner.nextInt();
                System.out.println(m);
                int erster = scanner.nextInt();
                int letzter = scanner.nextInt();
                int d = letzter-erster; // Differenz zwischen Masten 0 und 1
                int anzahl = 2;
                for (int j=2; j<m; j++) {
                    int aktueller = scanner.nextInt();
                    //System.out.println(aktueller);
                    if (aktueller-letzter!=d) { // Mit letztem Masten vergleichen
                        d = aktueller-letzter;
                        anzahl = 2;
                    } else {
                        anzahl++;
                        if (anzahl > maximum) {
                            maximum = anzahl;
                        }
                    }
                    letzter = aktueller;  // Aktueller Mast wird letzter Mast
                }
                lines.add(String.format("Case #%d: %d", fall+1, maximum));
            }
        }
        // Einzeiler, das eine Liste von Strings in eine Datei schreibt.
        Files.write(Paths.get("output.txt"), lines);
    }

• cable4.txt cable4-output.txt

Der “naive” Brute-Force Algorithmus in Ruby braucht (auf meiner 5-jährigen Kiste) etwa 3min 12s. Die Komplexität ist $O(n^3)$. Die entsprechende Java-Implementation braucht dafür 7 Sekunden (auf der gleichen Kiste).

Ein “dynamische Programmierung”-Algorithmus (ebenfalls Ruby) braucht dafür etwa 9s. Die Komplexität ist $O(n^2 \log(n))$, wobei das $\log(n)$ von Lookups herrührt. In Java habe ich den Algorithmus nicht implementiert.

Aufgabentext: https://soi.ch/contests/2016/round1/gotthard/

• $O(n)$ Lösung: http://www.zrzahid.com/sliding-window-minmax/

• tunnel1-100-1000-1000000.txt tunnel1-100-1000-1000000-output.txt

• tunnel2-100-1000-1000000.txt tunnel2-100-1000-1000000-output.txt

Anstatt einer Instanz-Datei (ca.0.5GB) gibt es hier einen Java-Code, der eine Instanz-Datei generiert:

    public static void generate(String fileName, int cases, int maxN, int maxH, int seed) throws IOException {
        ArrayList<String> lines = new ArrayList<>();
        lines.add(String.format("%d",cases));
        Random r = new Random(seed);        
        for (int c=0; c<cases; c++) {
            int n = r.nextInt(maxN-4)+5;
            lines.add(String.format("%d",n));
            List<Integer> bounds = Arrays.asList(r.nextInt(n), r.nextInt(n));
            Collections.sort(bounds);          
            int minH = r.nextInt(maxH/2)+maxH/4;
            System.out.println("Tunnel open at height "+minH+" from "+bounds.get(0)+" to "+bounds.get(1)+" min length="+(bounds.get(1)-bounds.get(0)));
            int heights[][] = new int[2][n];
            for (int i=0; i<n; i++) {
                int x = (i>=bounds.get(0) && i<bounds.get(1)) ? minH : r.nextInt(maxH-1)+1;
                heights[1][i] = r.nextInt(x);
                heights[0][i] = r.nextInt(maxH-x)+x+1;
            }
            StringBuilder sb = new StringBuilder();
            for (int j=0; j<2; j++) {
                for (int i=0; i<n; i++) {
                    sb.append(heights[j][i]);
                    if (i<n-1) {
                        sb.append(" ");
                    }
                }
                lines.add(sb.toString());
                sb = new StringBuilder();
            }
        }
        Files.write(Paths.get(fileName), lines);
        System.out.println("Wrote file "+fileName);
    }

Aufruf mit

        generate("tunnel3.txt", 50, 1000000, 100000000, 42);

Für diese Parameter sieht die Lösung wie folgt aus:

Case #1: 54553
Case #2: 118568
Case #3: 42236
Case #4: 95017
Case #5: 392495
Case #6: 23351
Case #7: 214369
Case #8: 207164
Case #9: 80147
Case #10: 101236
Case #11: 29947
Case #12: 272675
Case #13: 11311
Case #14: 568669
Case #15: 74155
Case #16: 36411
Case #17: 98517
Case #18: 118678
Case #19: 579076
Case #20: 364181
Case #21: 784906
Case #22: 10987
Case #23: 92835
Case #24: 208998
Case #25: 304626
Case #26: 130612
Case #27: 316250
Case #28: 88649
Case #29: 99034
Case #30: 256000
Case #31: 107054
Case #32: 178513
Case #33: 226822
Case #34: 64840
Case #35: 48131
Case #36: 4544
Case #37: 27783
Case #38: 66297
Case #39: 3345
Case #40: 44137
Case #41: 341521
Case #42: 226068
Case #43: 72879
Case #44: 383934
Case #45: 215890
Case #46: 58735
Case #47: 366097
Case #48: 263738
Case #49: 41854
Case #50: 6945