Ohne mich übetrieben lange mit dem Problem beschäftigt zu haben:
- bist du sicher dass du die Permutationen hinzufügen musst, 0 <= x <= y <= z <= 1000 gilt nach voraussetzung. Somit wird die erwartete Antwort wohl auch entsprechend sein.
- Eine losing configuration ist eine configuration von der du in einem Zug zwangsweise in einer Winning configuration landest. Was bedeutet das für die komponentenweise Differenz zwischen einer beliebigen und einer verlierenden configuration?
- ist (0,1,3) tatsächlich ein loser?

naja, ich muss die loser ausserhalb des bereichs ja irgendwie schon noch hinzufuegen, weil sie eine auswirkung auf andere (x,y,z) haben, die
in dem bereich liegen.
wie gesagt ist das aber echt easy, weil ich fuer jeden gefundenen loser (x,y,z) einfach
(x,y,z), (x,z,y), (y,x,z), (y,z,x), (z,x,y), (z,y,x) als loser speichere...



ne, (0,1,3) hat ja die form (0,1,2+x), wird also von einem "strahl" ausgehend von (0,1,2) getroffen.



hm, gute frage!
also wenn die differenz sowas ist wie (k,0,k) oder (0,0,k) etc., so waere der betrachtete punkt natuerlich ein winner.
der umkehrschluss gilt dabei aber nicht. wenn die differenz eine kompliziertere form hat, so hab ich im grunde keine ahnung... wenn sie nicht direkt durch einen zug auf "den" loser schliessen laesst, heisst das ja nicht unbedingt viel. es koennte ja ein anderer loser direkt erreichbar sein.

fuer jeden punkt einmal alle loser zu durchlaufen und zu gucken, ob die von da erreichbar sind, ist sehr ineffizient. kann man fuer n=100 ruhig machen, aber nicht fuer n=1000, weil es hier einfach zu viele loser gibt

This post was edited by fernsehen123 on Mar 16 2017 05:59am

Das klingt so weit schon ganz gut. Für mich war aber der Durchbruch nicht zu versuchen zu sagen, was eine losing konfiguration ist, sondern immer wenn man eine hat (und (0,0,0) ist ja auch eine) alle winning konfigurations vorherzusagen in dem man überlegt, was der Gegner gemacht haben könnte um einen in diese Position zu bringen.

Das in Verbindung mit simpler https://en.wikipedia.org/wiki/Memoization (braucht man sicher für 10% aller Probleme im Euler Style, fast immer wenn man das Gefühlt hat ein Beweis zu dem Problem wäre wohl induktiv, will man im Algorithmus entweder Graphen, Bäume oder eben memoization benutzen.)

Muss weiter arbeten, lese spätere posts später

hab jetzt schon 2x algorithmen mit n=1000 durchlaufen lassen, die fuer n=100 das richtige ergebnis geliefert haben.

die ergebnisse waren beide male falsch

Huch. Hätte nicht gedacht, dass es überhaupt möglich ist so einen Algorithmus zu finden xD
Soll ich noch schnell Ergebnisse für 10/200/500 produzieren?

PS: In eurer Dikussion oben vermisse ich noch (denke ist klar, aber wer weiß):
Es gibt nur winner und loser. Nichts dazwischen.

das hoert sich nach dem an, was wir strahlen nennen.
ein loser (x,y,z) hat ja die 7 strahlen

(x+*,y,z), (x,y+*,z), (x,y,z+*), (x+*, y+*,z), (x+*, y, z+*), (x,y+*,z+*), (x+*,y+*,z+*)

alle punkte die in so einem strahl liegen, sind automatisch winner.

wenn jetzt aber der trick sein soll, alle punkte in einer menge zu speichern und dann mit jedem gefundenen loser alles rauszuloeschen, so habe ich das schon probiert - bin am mangelnden speicher im java heap space gescheitert

This post was edited by fernsehen123 on Mar 16 2017 07:10am

joa, warum nicht

E: Achtung da war ein Rechenfehler, sollte gefixt sein, jetzt



Theoretisch brauchst du weniger als 1001^3 bits (< 1GB). Kannst Java heapspace auch immer mit -Xmx 5g vergrößern.
Im Prinzip geht es noch viel kleiner, weil die Punkte ja sortiert sind.

Außerdem ist es möglich, dass es nur wenige winner gibt und du nur alle winning speichern musst. Da lässt sich eine Konfiguration durch einen von (1000^3 / 2) unterschiedlichen Werten (also ceil(log_2(1000³ / 2)) = 29 bit pro Element) darstellen. Klar, wäre es brutal mega Absturz da extra man Informationstheoretischen Minimum zu bleiben, und um es mir leicht zu machen, habe ich auch ca 5GB RAM benutzt. Gerade Phyton und Java produzieren gerne overhead von mehr als einer Größenordnung, vereinfachte Darstellenungen im Programm nochmal mehr.

Aber zumindest in der Theorie ist es absolute möglich alle winner oder loser für x,y,z < 1000 im Speicher zu halten.



This post was edited by Kasiir on Mar 16 2017 07:22am

ah ok, das beruhigt mich irgendwie. dann war ich wohl doch nicht zu bloed um den algorithmus zu finden, sondern hab mich nur zu unrecht vom heap space error erschrecken lassen...

trotzdem hab ich ja im nachhinein methoden gefunden, einen ganzen strahl mit nur einem kleinen objekt abzudecken;
das sah in etwa so aus:




mir faellt dabei grad auf, dass ich nicht gucke, ob der z-wert wirklcih kleiner als der von dem loser ist, von dem der strahl aus geht.

keine ahnung ob man mich so verstehen kann...

hier nochmal der code, den ich durchlaufen lassen hab:

http://pastebin.com/frcMYaXm

n=100 liefert 173895
n=1000 liefert 18125494


edit: poste ruhig nochmal werte fuer 200 und 500. dann probiere ich meinen auch nochmal mit den werten aus

This post was edited by fernsehen123 on Mar 16 2017 11:04am

da war iwo n kleiner, lappiger fehler drin

edit: algorithmus lief fuer 42 min. ich sehe das als effizient genug an....
waer aber vllt trotzdem mal ne ueberlegung wert, mal mit python oder so zu arbeiten...?!

This post was edited by fernsehen123 on Mar 18 2017 02:40pm