Bundeswettbewerb Informatik: BWINF

thordk

hehe, wenn das programm dazu nicht fähig ist, dann löst es die aufgabe sehr wahrscheinlich auch nicht optimal

stalafin

Sag mal an, wielang dein Programm für alle Aufgaben braucht.

Ich habe bisher keine genauen Zeitwerte. Beispiel 3 wird gerade noch zusammengebaut (die Liste mit den vieeelen Zahlen).

Die anderen wollte ich gerade noch nicht durchlaufen lassen.

meinste mich? hab nur aufgabe 1 implementiert. die rennt unter einer sekunde durch, stütz mich aber auch nur auf lokale optimierung.

stalafin

Ja, ich mein Dich!
Ich rede von Aufgabe 1 (närrische Wirtschaft). Und da halt alle Beispiele (die, die Online auf www.bwinf.de als txt-Dokumente zu finden sind).
Oder hast Du nur bei der Aufgabe 1 das Beispiel 1?

Schildkroete

Hey,
da ich im Moment viel Zeit habe habe ich gedacht, ich mach mal auch den BWINF mit. Leider habe ich gleich schon eine Frage zu Nr1 (die Aufgabenstellung ist leider nicht sehr präzise). Ist es erlaubt, mehere gleiche Gegenstände zu kaufen und am Ende auch mehere gleiche Gegenstände zusammen gegen andere Gegenstände (<-Plural) umzutauschen?

[EDIT]Auch ich habe jetzt die FAQ gefunden und darin steht:

Nein, auch wenn das in der Aufgabenstellung nicht sehr deutlich ausgeschlossen ist. Entscheidend ist die Liste der Preise; jedem Listeneintrag entspricht genau ein Gegenstand, der zu diesem Preis erworben werden kann. Der Schatzmeister kann jederzeit immer nur eine Teilmenge der durch die Liste festgelegten Gegenstände haben; am Ende soll die Teilmenge möglichst groß sein und am besten der Gesamtmenge entsprechen.

[/EDIT]
OK, keine doppelten Gegenstände

thordk

also ganz ehrlich gesagt; die erste aufgabe des diesjährigen bwinf ist alles andere als trivial und hat sehr starke berühungspunkte mit diskreter optimierung. ist meiner meinung nach zu komplex für eine erste aufgabe.

Schildkroete

thordk schrieb:

also ganz ehrlich gesagt; die erste aufgabe des diesjährigen bwinf ist alles andere als trivial und hat sehr starke berühungspunkte mit diskreter optimierung. ist meiner meinung nach zu komplex für eine erste aufgabe.

Optimierung? Nach was wird den bewertet? Stärke des Algorithmus (effizienz)? Codestyle? Geschwindigkeit?

J. Mueller schrieb:

Ich will kein Spielverderber sein, deshalb frage ich ob es jemanden stoeren wuerde wenn ich meinen Code hier fuer alle zugaenglich mache?

Es würde stören. Sollte es nämlich eine korrekte Lösung sein, würde es doch den Bundeswettbewerb Informatik total verzerren - soll der Erfolg von der Googlefähigkeit abhängen?

Ich fänd's total unfair.

stalafin

Ich finde die erste Aufgabe allegemeinhin auch krass.

Immerhin gehört das Problem, welches da gelöst werden will, zu den NP-P Problemen. Und wer das löst, braucht beim BWINF wohl nicht mehr mitmachen. Der hat das dann nicht mehr nötig.

Weedjo

stalafin schrieb:

Ich finde die erste Aufgabe allegemeinhin auch krass.

Immerhin gehört das Problem, welches da gelöst werden will, zu den NP-P Problemen. Und wer das löst, braucht beim BWINF wohl nicht mehr mitmachen. Der hat das dann nicht mehr nötig.

whaa??? Ich hab die erste Aufgabe gelöst, obwohl ich mich erst seit zwei wochen mit C++ richtig beschäftige (davor nen bischen Delphi/Pascal aber mehr als arrays hab ich da auch nich gelernt) und habe die erste aufgabe dennoch an einem abend geschafft. Btw: Was zur Hölle ist ein NP-P Problem?
Hab mir ma das auf Wikipedia durchgelesen, aber daraus werd ich nich schlau. Was hat das mit der Aufgabe zu tun?

ness

stalafin schrieb:

Ich finde die erste Aufgabe allegemeinhin auch krass.

Immerhin gehört das Problem, welches da gelöst werden will, zu den NP-P Problemen. Und wer das löst, braucht beim BWINF wohl nicht mehr mitmachen. Der hat das dann nicht mehr nötig.

Das eine hat mit dem anderen nix zu tun. Wenn man einfach einen brute-force algorithmus implementiert (weil man z.B. keine Lust hat, sich übermäßig gedanken zu machen ), und ein paar sehr naheliegende optimierungen durchführt, sind alle Probleme bis auf das ganz große sehr schnell lösbar (und selbst das in unter 15min). Da muss man weder was über Komplexitätsklassen wissen noch die NP-Komplettheit des Problems erkennen (ist es das? es sieht ja so aus, aber ich kann grad nichts darauf reduzieren).

stalafin

Habe irgendwann mal im Netz etwas über NP in Zusammenhang mit Streckenoptimierung gelesen (100 Orte sind gegeben - welcher Weg ist der schnellste, wenn man am alle 100 Orte bereisen möchte). Kommt unserem Problem ja recht nahe.

Jaja - in die Richtung Brute Force geht mein Algorithmus auch. Hehe, nur schein ich nicht auf die entscheidende Optimierung zu kommen.
Ich mein, eine habe ich (ohne die es wohl Jahre dauern würde, die ganze Geschichte durchzugehen).
Aber ansonsten...

Aber ganz ehrlich - ihr benutzt Brute Force Methoden und braucht unter 15 Minuten egal für welche Aufgabe? Ich kann mir das irgendwie nicht so recht vorstellen.

Auch mit Ausgabe und allem (jeden Monat)?

Also ich hab den Thread mit viel Interesse gelesen. Hatte für Beispiel 2 auch erst 199 Monate, hab dann aber dank der Ergebnisse anderer Leute einen Fehler entdeckt, so dass ich hinterher nur noch 172 Monate hatte.

Beispiel 1: 131071 Moante; 1,444 Sekunden
Beispiel 2: 172 Monate; 0,137 Sekunden
Beispiel 3: 1026 Monate; 0,488 Sekunden
Sprache: C++

Es ist mir ein Rätsel, wie man für die Aufgabe im Aufgabenblatt unter 13 Monaten rausbekommen kann. Ich finde die Aufgabe auch zu anspruchsvoll für die erste Runde.

PS: Cool, dass es mal ein Forum ohne Registrierungspflicht gibt.

ness

stalafin schrieb:

Auch mit Ausgabe und allem (jeden Monat)?

Ohne natürlich.

Michael E.

CA schrieb:

Beispiel 1: 131071 Moante; 1,444 Sekunden
Beispiel 2: 172 Monate; 0,137 Sekunden
Beispiel 3: 1026 Monate; 0,488 Sekunden

Ich kann mir nicht vorstellen, dass ein korrekter Algorithmus so schnell arbeiten kann. Ich bin mal auf die Codes nach dem Abgabetermin gespannt.

Ich bin mir eigentlich recht sicher, dass die Ergebnisse korrekt sind. Ich weiß natürlich nicht, ob die Ergebnisse optimal sind.

Michael E.

CA schrieb:

Ich bin mir eigentlich recht sicher, dass die Ergebnisse korrekt sind. Ich weiß natürlich nicht, ob die Ergebnisse optimal sind.

Wie soll man diese beiden Aussagen miteinander vereinen? Denn nur ein optimales Ergebnis ist auch korrekt.

Michael E. schrieb:

CA schrieb:

Ich bin mir eigentlich recht sicher, dass die Ergebnisse korrekt sind. Ich weiß natürlich nicht, ob die Ergebnisse optimal sind.

Wie soll man diese beiden Aussagen miteinander vereinen? Denn nur ein optimales Ergebnis ist auch korrekt.

Da hast du natürlich recht. Ich meinte, dass ich die Regeln nicht verletze (z.B. dass ich in einem Monat nicht zu viel ausgebe oder einen Gegenstand in einem Monat mehrfach besitze). Die Ergebnisse sind allerdings gleich gut wie die Besten, die ich bisher in diesem Forum gehört habe. Deshalb vermute ich, dass sie die Bestmöglichen sind. Das muss natürlich nicht stimmen.

asotbb

Das ist so nicht ganz richtig, du kommst auch mit einem nicht optimalen Algorithmus zu einem Ergebnis, es gibt mehre Möglichkeiten, auf diese Monatszahlen zu kommen.
Dass er korrekt arbeitet, dafür spricht, dass alle deine Ergebnisse gleich denen der genannten ist! Aber, 100% richtig muss deine Algorithmus auch nicht sein, also es kann sein, dass er nicht ganz optimal ist.
Abdererseits müssen die genannten Zeiten keinesfalls eine Messlatte sein!

mfg
blut-lecker

blut-lecker schrieb:

Das ist so nicht ganz richtig, du kommst auch mit einem nicht optimalen Algorithmus zu einem Ergebnis, es gibt mehre Möglichkeiten, auf diese Monatszahlen zu kommen.

Dass er korrekt arbeitet, dafür spricht, dass alle deine Ergebnisse gleich denen der genannten ist! Aber, 100% richtig muss deine Algorithmus auch nicht sein, also es kann sein, dass er nicht ganz optimal ist.
Abdererseits müssen die genannten Zeiten keinesfalls eine Messlatte sein!

Ich bin auf jeden Fall mit dem zufrieden, was ich habe. Ich hatte schon gedacht, ich würde die Aufgabe garnicht lösen. Ich werd einfach mal abwarten, was nach der Bewertung rauskommt.
Ich mach sicherheitshalber mal vier Aufgaben, dann werden schon mehr als 12 Punkte übrigbleiben. Das hat letztes Jahr auch geklappt. Ich bin dann allerdings an der zweiten Runde hängengeblieben (wie dieses Jahr vermutlich auch wieder , aber man muss es ja versuchen ).

[Meine Meinung zu den Aufgaben]
Die anderen Aufgaben sind ja alle relativ leicht. Die Aufgabe 1 passt irgendwie garnicht rein. Aber als Ausgleich gibt es ja Aufgabe 5, die eigentlich nur Programmier-/Dokumentationsarbeit ist. Die Kreativaufgabe (3) ist auch nicht so mein Ding; viel Arbeit, aber nicht sehr interessant. Die Nummer 4 würde ich zwar normalerweise nicht machen, aber ich glaube mir bleibt keine andere Wahl, also bleibt insgesamt Aufgabe 1(fertig)+2(fertig)+4+5(fertig). Die Doku muss ich auch noch machen. Wird viel Arbeit diese Woche . So, das war jetzt meine ganz subjektive Meinung zu den Aufgaben, nur für den Fall, dass es jemanden interessiert .
[/Meine Meinung zu den Aufgaben]