3. WPC... geht weiter! -> wpc12

WPC... geht weiter! -> wpc12

  • V

    wirklich spannend ist, was die leute, die hier tricks veröffentlichen, in der hinterhand haben. man macht sich ja keine medallie kaputt, indem man einen trick verrät, den man nicht schon als nicht so wichtig abgetan hat.

    0
  • J

    Optimizer schrieb:

    Jester schrieb:

    Ich hab mich zumindest redlich bemüht eine Aufgabe zu finden, die in ein paar (wenigen) Stunden lösbar ist.

    rofl.
    *nochmal so durch den Thread querles* 😉

    ich hab nicht behauptet, daß man in wenigen Stunden ne optimale Lösung findet. Die erste Lösung ging aber noch Freitag abend (oder war's Samstag?) ein.

    0
  • J

    Bin aber echt gespannt, was so an Einsendungen kommt! Schätze mal es wird mindestens ne knappe Entscheidung. 🙂

    0
  • P

    volkard schrieb:

    wirklich spannend ist, was die leute, die hier tricks veröffentlichen, in der hinterhand haben. man macht sich ja keine medallie kaputt, indem man einen trick verrät, den man nicht schon als nicht so wichtig abgetan hat.

    Man kann auch versuchen durch mathematische Argumentationen und das Aufstellen von Sätzen potentielle Mitbewerber von vornerein abzuschrecken. 🙂

    0
  • M

    Ponto: Das klappt bei mir ziemlich gut 😞

    0
  • P

    Michael E. schrieb:

    Ponto: Das klappt bei mir ziemlich gut 😞

    Dann lass dir gesagt sein, dass man das meiste hier mathematisch Gesagte nicht für eine schnelle Lösung gebrauchen kann. Man kann auf einen linearen Algorithmus kommen, ohne das alles zu kennen. Ich glaube es kommen alle im Endeffekt auf äquivalente lineare Algorithmen, und nur die Güte der Implementierung wird über den Gewinner entscheiden. Schneller als linear kann man nicht werden, da alle Eingabebits gelesen werden müssen.

    Hattest du nicht am Anfang schon etwas schnelles?

    0
  • J

    Sehe ich genauso. Die mathematische Untersuchung macht einfach Spaß und hilft das Problem *vollständig* zu begreifen. Dazu gehört natürlich auch eine Klassifikation aller möglichen Situationen nach handlichen Kriterien, Eindeutigkeitsbeweise für Lösungen etc.

    Zum implementieren kann man nur einen kleinen Teil der Resultate brauchen. Macht aber nix. Geht ja um's Lernen.

    0
  • J

    und weg

    0
  • P

    Jester schrieb:

    Da ihr inwzischen schon fast alles beweisen konntet was ich auch hab verrate ich mal meinen Beweisansatz. Vielleicht kriegt ihr damit noch mehr raus. 🙂

    Wir haben ja bei d-f-g gesehen, daß es reicht Lampen ausschalten zu können.
    Also kann ich das ganze als Z/2Z-Vektorraum auffassen. Als Erzeugenden-System nehme ich die Bitvektoren die durch das anschalten einer einzelnen Lampe entstehen:

    110....0
1110...0
01110..0
   .
   .
   .
0..01110
0...0111
0.000011

    sind das. (ist egal ob ihr's waagrecht oder senkrecht lest).
    Eine Lichterkette komplett auszuschalten ist sozusagen eine Lösung des inhom. LGS A*x=b mit dieser Matrix als A und der geg. Lichterkette als b.

    Jetzt sind viele Aussagen leicht: Bei 3*n oder 3*n+1 geht's immer haben wir. Dann sagt uns das: die Matrix muß wohl invertierbar sein => Eindeutigkeit der Lösung.

    Wenn man weiß, daß diese Matrix immer mindestens Rang n-1 hat, daß es maximal zwei Lösungen gibt. Außerdem kennen wir die Struktur der Lösung:

    inhom. Lösung = spezielle Lösung + c*homogene Lösung. Achtung c ist nur 0 oder 1, da wir uns Z/2Z befinden. Die homogene Lösung habt ihr ja auch schon gefunden...

    MfG Jester

    Super, damit hab ich nichts mehr in der Hinterhand, wie es Volkard gesagt hat. 😞

    0
  • V

    Ponto schrieb:

    Super, damit hab ich nichts mehr in der Hinterhand, wie es Volkard gesagt hat. 😞

    haben jetzt alle den spaß verloren und ich bin der einzigste, der einsendet? 😃

    0
  • J

    Ponto schrieb:

    Super, damit hab ich nichts mehr in der Hinterhand, wie es Volkard gesagt hat. 😞

    Ups, aber wie kann das denn sein? 😞

    Ich meine, ich habe überhaupt nichts neues geliefert. Keine neue Aussage, nur einen Beweis für die Eindeutigkeit der Lösung, die war aber schon vor einigen Seiten postuliert.

    Hilft's was wenn ich editiere?

    0
  • P

    Jester schrieb:

    Ponto schrieb:

    Super, damit hab ich nichts mehr in der Hinterhand, wie es Volkard gesagt hat. 😞

    Ups, aber wie kann das denn sein? 😞

    Ich meine, ich habe überhaupt nichts neues geliefert. Keine neue Aussage, nur einen Beweis für die Eindeutigkeit der Lösung, die war aber schon vor einigen Seiten postuliert.

    Hilft's was wenn ich editiere?

    Lass es so wie es ist.

    0
  • D

    volkard schrieb:

    Ponto schrieb:

    Super, damit hab ich nichts mehr in der Hinterhand, wie es Volkard gesagt hat. 😞

    haben jetzt alle den spaß verloren und ich bin der einzigste, der einsendet? 😃

    Nene, ich habe da noch ein paar Tricks 🙂

    0
  • S

    volkard schrieb:

    Ponto schrieb:

    Super, damit hab ich nichts mehr in der Hinterhand, wie es Volkard gesagt hat. 😞

    haben jetzt alle den spaß verloren und ich bin der einzigste, der einsendet? 😃

    einzige ! 🕶

    Ich darf doch ein Zitat von Dir als Sig mißbrauchen!?? 🤡 👍

    0
  • V

    Sgt. Nukem schrieb:

    Ich darf doch ein Zitat von Dir als Sig mißbrauchen!?? 🤡 👍

    aber klar doch.

    0
  • ?

    volkard schrieb:

    haben jetzt alle den spaß verloren und ich bin der einzigste, der einsendet? 😃

    Hm, also ich werde sicher auch noch einsenden 😉

    Habe heute noch ein paar Millisekunden herausschlagen können, aber ich glaube, in der Optimierung des Algorithmus selbst kann ich mit meinem Wissen nicht mehr wirklich was erreichen. Das einzige, was jetzt nochmal einen echten Schub geben würde, wäre, wenn ich das Problem mit den zwei Wegen vorab entscheiden könnte... Ich glaube, wer das schafft (oder sogar schon geschafft hat), hat gute Karten auf den Sieg 😉

    0
  • T

    kwaart schrieb:

    Habe heute noch ein paar Millisekunden herausschlagen können, aber ich glaube, in der Optimierung des Algorithmus selbst kann ich mit meinem Wissen nicht mehr wirklich was erreichen. Das einzige, was jetzt nochmal einen echten Schub geben würde, wäre, wenn ich das Problem mit den zwei Wegen vorab entscheiden könnte... Ich glaube, wer das schafft (oder sogar schon geschafft hat), hat gute Karten auf den Sieg 😉

    Da ich bei der Bundeswehr bin und nur im Büro sitze, habe ich heute mal wieder sehr viel Zeit gehabt und meinen Algorithmus noch optimiert. Ich erreiche jetzt mit Dev-Cpp ca. 76 ms bei 1.000.002 Glühbirnen 🙂

    0
  • P

    TomasRiker schrieb:

    kwaart schrieb:

    Habe heute noch ein paar Millisekunden herausschlagen können, aber ich glaube, in der Optimierung des Algorithmus selbst kann ich mit meinem Wissen nicht mehr wirklich was erreichen. Das einzige, was jetzt nochmal einen echten Schub geben würde, wäre, wenn ich das Problem mit den zwei Wegen vorab entscheiden könnte... Ich glaube, wer das schafft (oder sogar schon geschafft hat), hat gute Karten auf den Sieg 😉

    Da ich bei der Bundeswehr bin und nur im Büro sitze, habe ich heute mal wieder sehr viel Zeit gehabt und meinen Algorithmus noch optimiert. Ich erreiche jetzt mit Dev-Cpp ca. 76 ms bei 1.000.002 Glühbirnen 🙂

    Warum gerade 1.000.002 Glübirnen und nicht 1.000.000?

    0
  • B

    Ponto schrieb:

    Warum gerade 1.000.002 Glübirnen und nicht 1.000.000?

    weils durch 3 teilbar ist.

    0
  • P

    borg schrieb:

    Ponto schrieb:

    Warum gerade 1.000.002 Glübirnen und nicht 1.000.000?

    weils durch 3 teilbar ist.

    Kann es sein, dass die Eingabe immer um zwei Elemente erweitert wird?

    0
Anmelden zum Antworten