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/