WPC-Aufgabe (Programmierwettbewerb)
-
Michael E. schrieb:
Kompiliert mit VC++ 2003 Toolkit auf Speed optimiert komm ich auf folgende Ausgabe:
5 174 824
722 308 723gcc -O
562 092
163 260 531
-
c.rackwitz schrieb:
volkard schrieb:
leider nicht.
ich hab 16628462.
ich hab aber auch 16628551 in meinem ersten versuch gehabt.postest du im neuen jahr die zwischenschritte fuer dieses ergebnis? ich waer interessiert.
viel einfacher. auch wenn es mich und bashar den sieg kostet, ich verrate das problem meines ersten algos algos an einem beispiel:
1 32 33 34 31
was sagt dein programm dazu?
-
Ponto schrieb:
O(n)? Da muss ich noch rauskriegen, wie man es ohne Sortieren macht.
ich glaube nicht, daß es ohne sortieren geht. und daß es mit sortieren plus O(n) geht, ist noch nicht bewiesen. sicher ist für mich bisher nur, alle möglichleiten durchzuprobieren (sagen wir mal mit höchstens 2*n vertauschungen), und die leichteste zu nehmen. klingt nach O(n!). sollte ich eine schnelle lösung abgeben, wo ich nicht weiß, ob sie stimmt, oder eine langsame?
-
volkard schrieb:
viel einfacher. auch wenn es mich und bashar den sieg kostet, ich verrate das problem meines ersten algos algos an einem beispiel:
Das "gut" ist wohl falsch rübergekommen. Ich meinte nicht, das ich das gleiche Ergebnis bekomme, sondern hab mich gefreut, dass es noch Optimierungspotential gibt.
-
volkard schrieb:
Ponto schrieb:
O(n)? Da muss ich noch rauskriegen, wie man es ohne Sortieren macht.
ich glaube nicht, daß es ohne sortieren geht. und daß es mit sortieren plus O(n) geht, ist noch nicht bewiesen. sicher ist für mich bisher nur, alle möglichleiten durchzuprobieren (sagen wir mal mit höchstens 2*n vertauschungen), und die leichteste zu nehmen. klingt nach O(n!). sollte ich eine schnelle lösung abgeben, wo ich nicht weiß, ob sie stimmt, oder eine langsame?
Da du ja jetzt den Witz an der Aufgabe verraten hast, kann man mal darüber nachdenken. Die Zeit in die Laufzeitoptimierung zu stecken halte ich für sinnlos. Da sind andere immer besser und ohne die Testplattform kann man auch nicht viel machen. Ich bin mir aber bei Sortieren + O(n) ziemlich sicher. Zum Beweis fehlt noch was Zeit zum nachdenken.
-
Im übrigen denke ich, dass die Aufgabe spannender wäre, wenn Pakete auch identisches Gewicht haben könnten. Aber dafür ist es zu spät.
-
Ja, die Aufgabe wäre dann definitiv schwieriger. Allerdings muß ich ehrlich gestehen, daß mir dann meine Lösungsansatze nahezu alle kaputt gehen und mir nur noch eine Idee übrig bleibt.
Um mehr Spielraum zu lassen habe ich mich daher entschieden, die Aufgabe so zu stellen.
MfG Jester
-
wer macht eigentlich die streckenschneideaufgabe?
-
Jester schrieb:
Ja, die Aufgabe wäre dann definitiv schwieriger. Allerdings muß ich ehrlich gestehen, daß mir dann meine Lösungsansatze nahezu alle kaputt gehen und mir nur noch eine Idee übrig bleibt.
da bin ich ja mal gespannt. ich hab nur einen lösungsansatz, un dem ist egal, ob doppels vorkommen.
-
Ponto schrieb:
Ich bin mir aber bei Sortieren + O(n) ziemlich sicher. Zum Beweis fehlt noch was Zeit zum nachdenken.
na, hoffen wir mal, daß du nicht recht hast. was machen wir, wenn du recht hast? wie soll man das noch messen? vielleicht hängen wir alle noch nen bäckerwitz in die kommentierung und im zweifelsfall gewinnt der beste bäckerwitz?
-
Dann bin ich auch gespannt!
In #cpp ist grad einer, der die Streckenaufgabe macht. Hoffe, daß es noch ein paar mehr versteckte Teilnehmer gibt.
-
volkard schrieb:
c.rackwitz schrieb:
volkard schrieb:
leider nicht.
ich hab 16628462.
ich hab aber auch 16628551 in meinem ersten versuch gehabt.postest du im neuen jahr die zwischenschritte fuer dieses ergebnis? ich waer interessiert.
viel einfacher. auch wenn es mich und bashar den sieg kostet, ich verrate das problem meines ersten algos algos an einem beispiel:
1 32 33 34 31
was sagt dein programm dazu?192. Geht es wirklich billiger? Mach mir keine Angst, ich hasse das.
-
Ja, leider geht es billiger.
Kosten 1 32 33 34 31 31 32 33 34 1 32 31 32 33 1 34 + 35 31 32 1 33 34 + 34 31 1 32 33 34 + 33 1 31 32 33 34 + 32 ---- 166
-
Gute Nacht.
-
Ebenfalls...
Da hatte ich grade meinen alten Algorithmus schön optimiert und dann sowas.
Vielleicht mache ich doch die Aufgabe mit den Linien
-
volkard gewinnt eh.
-
Einmal hab ich ihn geschlagen *g*
wenn auch nur knapp!
-
volkard schrieb:
wer macht eigentlich die streckenschneideaufgabe?
ich
Ach ja, ihr Sortieraufgabenlöser, gebt euch doch nicht alle gleich immer auf, ist volkard nicht eine "Motivation" für euch? Denkt halt nochmal scharf nach, irgendwie wird er auch auf seinen Algo. gekommen sein ;-). Wie ich das verstanden habe, besteht das Risiko, wenn er seine schnelle Lösung abgibt, dass die nicht unbedingt korrekt ist. Braucht ihr noch mehr Motivation?
-
volkard schrieb:
wer macht eigentlich die streckenschneideaufgabe?
Ich versuchs *duck*
-
volkard schrieb:
Ponto schrieb:
Ich bin mir aber bei Sortieren + O(n) ziemlich sicher. Zum Beweis fehlt noch was Zeit zum nachdenken.
na, hoffen wir mal, daß du nicht recht hast. was machen wir, wenn du recht hast? wie soll man das noch messen? vielleicht hängen wir alle noch nen bäckerwitz in die kommentierung und im zweifelsfall gewinnt der beste bäckerwitz?
Wenn das mit O(n) stimmt, ist da nicht viel zu machen. Und die Sortierung schaue ich mir auf keinen Fall an.