This is an old revision of the document!
SOI - Aufgaben
CableCar
Aufgabentext: https://soi.ch/contests/2016/round1/cablecar/
Teilaufgaben 1 & 2
- 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
Lösungsvorschlag Cablecar Aufgaben 1 und 2
Teilaufgabe 3
Achtung: Die Input-Datei war fehlerhaft, bitte laden Sie sich die neue Instanz-Datei herunter!
Teilaufgabe 4
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.
Tunnel
Aufgabentext: https://soi.ch/contests/2016/round1/gotthard/
- $O(n)$ Lösung: http://www.zrzahid.com/sliding-window-minmax/
Aufgabe 1
Aufgabe 2
Aufgabe 3
Anstatt einer Instanz-Datei (ca. 1GB) 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: