Foren » 39. Bundeswettbewerb Informatik

[39.2 Allgemein] Austausch über Lösungen

    • 4 Beiträge
    20. April 2021 11:58:36 CEST

    Hallo,

    jetzt wo auch die zweite Runde rum ist, könnten wir uns ja mal über Lösungen austauschen.

     

    • 7 Beiträge
    20. April 2021 12:25:14 CEST

    Hier meine Dokumentationen:

    Aufgabe1

    Aufgabe2 

    Wäre an Lösungen/Ausgaben für Aufgabe 1 interessiert da ich da nur optimiert habe und wissen will wie nah ich an anderen Ergebnissen bin.

    • 8 Beiträge
    20. April 2021 22:10:12 CEST

    Hier sind meine Lösungen: https://github.com/ChuangSheep/bwinf2020

    Für Aufgabe 1 habe ich nur die Straßenlänge berücksichtigt. Ich konnte keine Gegenbeispiele finden, wo die Prämisse ({\sum_{i = 0}^{n - 1} c_{i,j} x_i } \leq 1000 \forall j \in \{0,1,...,9\}) erfüllt ist und es aber unmöglich ist, dem Anbieter einem festen Platz zuzuordnen. Das zu bewiesen habe ich nicht geschafft, vielleicht weil es doch Gegenbeispiele gibt? 

    Aufgabe 2 kann man einfach mit einem linearen Gleichungssystem lösen. 

    • 4 Beiträge
    20. April 2021 22:23:29 CEST
    • 4 Beiträge
    20. April 2021 22:26:12 CEST
    Benedikt Kuder said:

    Hier meine Dokumentationen:

    Aufgabe1

    Aufgabe2 

    Wäre an Lösungen/Ausgaben für Aufgabe 1 interessiert da ich da nur optimiert habe und wissen will wie nah ich an anderen Ergebnissen bin.

     

    Als NP-schweres Problem könnte selbst das Bruteforcen viel Zeit benötigen. Insbesondere wenn man Eingaben wie Flohmarkt7.txt denkt. Mich würde aber auch interessieren, wenn jemand eine vollständige Lösung hat (und wie die Person da hingekommen ist).

    • 4 Beiträge
    20. April 2021 22:42:16 CEST

    Dann geselle Ich mich doch auch mal mit meiner Einreichung dazu. Ich habe Aufgabe 2 und 3 bearbeietet.

     

     

    • 66 Beiträge
    20. April 2021 23:18:17 CEST

    Ich habe die Aufgaben 2 und 3 bearbeitet:

    In A2 stelle ich jede Beobachtung als Matrix mit Aussagen (kann sich Obst X in Schüssel Y befinden?) dar, die Lösung erhält man, indem man die komponentenweise logische Konjunktion bildet. Laufzeit (b: Anzahl Beobachtungen, n: Anzahl Obstsorten) O(b * n^2)

    A3 habe ich mit Brute-Force gelöst. Für jede mögliche Konstellation K lässt sich dabei in O(1) (nach Vorberechnung in O(U^3)) die andere Konstellation L' errechnen, die die meisten Stimmen erhalten würde -  genau dann, wenn das mehr als die Hälfte der Anzahl der Häuser ist, ist K instabil. Gesamte Laufzeit: O(U^3)

    Und hier die Einsendung: https://github.com/LinuxUserJTB/Einsendung_BwInf_39_2


    Dieser Beitrag wurde am 20. April 2021 23:20:24 CEST von Jonathan Busch bearbeitet
    • 4 Beiträge
    21. April 2021 04:55:25 CEST

    Gerade auch nochmal Zeit gefunden ein paar Worte dazu zu schreiben, was ich gemacht habe.

    Bei Aufagbe 2 habe ich jeder Obstsorte auf Basis der Beobachtungen in denen sie vorkommen einen Wert zu gewiesen. Folgend sind also alle äquivalenten Obstsorten nicht voneinander zu unterscheiden. Dann kann man einfach alle Obstsorten raussuchen die die Werte der gesuchten Obstsorten besitzen. Worstcase ist der Ansatz O(k*n^2). Im Avargecase ist der Ansatz O(k*n).

    Bei Aufgabe 3 habe ich zunächst Untersucht, wie sich ein einzelnes Zentrum auf dem Zahlenstrahl verhält. Unter der gegebenen Bedingung ist jeder Punkt zwischen unterem und oberen Median ein stabiles Zentrum. Das dies auch für alle 3 Zentren auf dem Kreis gilt (jeweils für die Menge an Punkten, zu denen sie die nächsten sind) habe ich einfach mal angenommen. Vielleicht ließe sich das auch beweisen, aber ich fand, dass das als Heuristik durchgehen kann. Durch diese und ein paar weitere Beobachtungen kann ich die Menge an Kandidaten reduzieren und dann einfach mit einander vergleichen. Laufzeit dürfte O(n^6) sein, aber da bin ich mir gerade wirklich nicht sicher.

    • 3 Beiträge
    21. April 2021 09:28:50 CEST

    Bei Aufgabe 1 konnte ich Subset-Sum auf das Problem reduzieren und darüber die NP-Vollständigkeit zeigen. Ansonsten hat meine Heuristik denselben Ansatz wie die von den meisten hier, zuerst Reihenweise das Feld zu füllen.

    Aufgabe 2 habe ich wie Jonathan auch per Matrix mit Einträgen a_f,s gelöst, die angeben, ob Frucht f in Schüssel s liegen kann. Zusätzlich habe ich die Aufgabe dahingehend erweitert, dass das Programm ausgibt, welche Informationen noch benötigt sind, um eine eineindeutige Zuordnung feststellen zu können (dabei soll die Anzahl der Informationen/Beobachtungen minimiert werden).

    • 3 Beiträge
    21. April 2021 19:32:52 CEST

    Ich habe Aufgabe zwei und drei in C++ gelöst: https://github.com/christopher-besch/bwinf_39_round2

    Für Aufgabe drei habe ich ein Visualisierungsprogramm für's Web geschrieben. Man kann es hier benutzen. Der Source Code ist hier: https://github.com/christopher-besch/lake_visualizer

    • 1 Beiträge
    22. April 2021 23:03:37 CEST

    Dann stelle ich mal auch Lösungen vor.

    Aufgabe 2 habe ich ähnlich zu einigen, die bisher vorgestellt haben, gelöst. (Ich habe nicht alles durchgelesen.) Der vollständigkeit halber hier meine Dokumentation.

    Bei Aufgabe 3 habe ich eine Lösung mit O(N^3/K^2) im Averagecase. Man kann nämlich zeigen, dass sich bei einer stabilen Konfiguration die Anzahlen der Häuser zwischen Eisdiele 1 und 2, zwischen Eisdiele 2 und 3 sowie zwischen Eisdiele 3 und 1 jeweils höchstens um 3 unterscheiden, was den Suchraum deutlich verkleinert: Dokumentation

    Weiß jemand aus den Vorjahren, wo die "Cutoffs" normalerweise liegen?

    • 7 Beiträge
    21. Juni 2021 15:02:44 CEST

    Ich teile meine Lösung auch mal: https://gitlab.com/vypxl/bwinf39_2

    Doku ist auch enthalten.

    Aufgabe 2 ist in Python gelöst worden, Aufgabe 3 in Julia.