Foren » 39. Bundeswettbewerb Informatik

[39.1 Allgemein] Austausch über Lösungen!

    • 7 Beiträge
    24. November 2020 17:43:12 CET

    Liebe BwInf-Community,

    die erste Runde ist nun beendet und es ist interessant, sich über die Lösungen auszutauschen.

    Wenn keine Einwände auftauchen, werde ich den ersten Schritt beginnen und bald meine Lösungen euch hochladen.

    Viele Grüße

    • 391 Beiträge
    24. November 2020 20:40:33 CET

    Das ist eine schöne Anregung – danke, Erik! Gerne ab morgen (Mittwoch).

    • 7 Beiträge
    25. November 2020 13:08:50 CET

    Aufgabe 1 habe ich einfach mit Backtracking gelöst, sicher gab es hier schönere Lösungen...

    Aufgabe 2 habe ich reines Brute-Force verwendet. Ich habe eine Optimierung gefunden, aber nicht implementiert. Wie habt ihr das optimiert?

    Aufgabe 3 habe ich Monte-Carlo verwendet, mich würde interessieren, ob jemand hier stattdessen was mathematisch bewiesen/ausgerechnet hat.

    Aufgabe 5 habe ich mit einem Graphenalgorithmus für den Maximalen Fluss mit den Minimalen Kosten gelöst. Hier interessiert mich auch richtig, wie ihr das gemacht habt!

    Ich habe kurze, kompakte Dokus

    • 66 Beiträge
    25. November 2020 16:28:04 CET

    Aufgabe 1 habe ich mit einem bipartiten Graphen gelöst. Dazu habe ich bewiesen, dass der Graph, wenn genau eine korrekte Zuordnung existiert (das bedeutet praktisch „perfektes Matching“), immer mindestens einen Knoten enthält, der den Grad 1 hat. So kann man immer diesen (mindestens) einen Knoten zuordnen und erreicht für die Zuordnung lineare Laufzeit zur Anzahl der Kanten. Die Errechnung des Graphen lässt sich allerdings nur durch O(n²) einschränken.

    Aufgabe 2 habe ich auch mit Brute-Force gelöst (etwa bis zu 7,1*10^9 Möglichkeiten als sichere obere Schranke). Mein Backtracking-Verfahren hat immer nur passende Teile versucht anzusetzen; dadurch hat es für kein Beispiel länger als 0.1 Sekunden gebraucht.

    Aufgabe 3 habe ich durch einfache Simulation der Spiele gelöst. Durch eine mehr oder weniger ausgeschmückte graphische Benutzeroberfläche (ein Fenster mit Button) kann man die Simulationen sogar ganz bequem beenden. Bei K. O. werden die Paare vorher zufällig zugeordnet.

    Bei A3 hätte man die Gewinnwahrscheinlichkeit beim K. O. System sicher auch ausrechnen können, aber ich wollte nicht zu viel Arbeit in diese Aufgabe stecken, weil ich die Simulationslösung (die genau genug ist) schon fertig hatte.

    https://github.com/LinuxUserJTB/Einsendung_BwInf_39_1


    Dieser Beitrag wurde am 20. Dezember 2020 19:58:12 CET von Jonathan Busch bearbeitet
    • 1 Beiträge
    26. November 2020 21:46:48 CET

    Aufgabe 1: Endlosschleife, die solange die Wörter zuordnet, bis keine eindeutige Zuordnung mehr möglich ist.

    Aufgabe 2: Auch Brute-Force

    Aufgabe 3: Liga via Zufall. K.O.-Turnier via Zufall und Berechnung. Wenn die Startanordnung fürs K.O.-Turnier bekannt ist, kann man die genaue Wahrscheinlichkeit berechnen, mit der ein Spieler gewinnt (via Binomialverteilung). Ich bin dann einfach viele verschiedene zufällige Startpositionen durchgegangen, um eine Annäherung für den Durchschnitt zu erhalten.

    Für spielstaerken1.txt, spielstaerken2.txt und spielstaerken4.txt kann man so innerhalb von paar Sekunden auch die exakte Wahrscheinlichkeit berechnen (ohne Benutzung von Zufällen).

    • 391 Beiträge
    30. November 2020 11:32:12 CET

    Danke an die drei, die bisher ihre Lösungsideen berichtet haben. Gibt es noch andere?

    PS: Lieber "Rainer Zufall", bitte verwende hier deinen Realnamen.

    • 1 Beiträge
    20. Dezember 2020 15:33:38 CET
    Ein bisschen spät, aber hier sind meine Lösungen:
    https://github.com/kping0/BWINF39-Submissions
    • 3 Beiträge
    29. Dezember 2020 06:56:37 CET

    Und hier die Lösung meines Teams:
    https://github.com/christopher-besch/bwinf39_round1