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 “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.
Tunnel
- O(n) Lösung: http://www.zrzahid.com/sliding-window-minmax/