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
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)$ Ein Algorithmus der dynamischen Programmierung (ebenfalls Ruby) braucht dafür etwa 9s. Die Komplexität ist $O(n^2 \log(n))$, wobei das $\log(n)$ von Lookups herrührt.