18 Mar
2011
18 Mar
'11
11:01 p.m.
megcsinaltam alien gamet, de nem tudtam bekuldeni, mert szar a
bekuldorendszeruk es amig szamol visszafele hogy 6 perc van hatra,
kozbe irja hogy time expired azzal parhuzamosan...
nagyon szep megoldasa van kulonben
6 perc van megoldani, bekuldessel egyutt, szoval olyan megoldas kell,
ami kb 5 perc alatt lefut
enyem O(n^2*log(n)), es kb 5 mp alatt lefut a nagy inputfajlra, amiben
kb 45 bazinagy eset van
nem szeretnem elarulni megoldast (majd jovohet penteken), csak
sejtesekrol par szo:
- tenyleg nem szamit hogy ki mit lep, mindenkepp ugyanaz nyer (sot a
lepesszam is azonos mindig)
- a masik sejtes nem igaz, hogy 1-et irhatunk akarmilyen pozitiv szam
helyett (pl "0 -1 1 0"-ra 1 lepes utan van vege, amig "0 -1 2 0"-ra 2
lepes utan van vege)
ngg
19 Mar
19 Mar
1:18 a.m.
New subject: [acm-valogato] Safest-place -- 2D-ben, quad-tree demonstráció
Sziasztok!
Én pedig a maximális minimum távolságos "Safest Place" feladattal
foglalkoztam egy kicsit. Csináltam hozzá C#-ban egy kis szemléltető
programocskát [1], ami persze tesztelni is jó, hogy miként alakul a rács.
Hogy jól vizualizálható legyen, ez csak 2D-ben működik, így oct-tree
helyett quad-tree-t használ, de a működése alapelvét tekintve ugyanaz,
mint a 3D verziónak.
Közben amúgy rájöttem, hogy egy jó megoldás kapható úgy is, ha építünk a
pontokra egy Voronoi-diagramot ([2]), ennek ugyanis valamelyik csúcspontja
lesz a megoldás. Persze nem valószínű, hogy valakinek ezt lenne ideje
lekódolni...
[1]: http://cs.bme.hu/acm/felkeszito2011/05/SafestPlaceVisu.zip
[2]: http://en.wikipedia.org/wiki/Voronoi_diagram
Üdv,
Balázs
On Fri, 18 Mar 2011 23:01:07 +0100, NGG <ngg(a)ngg.hu> wrote:
megcsinaltam alien gamet, de nem tudtam bekuldeni,
mert szar a
bekuldorendszeruk es amig szamol visszafele hogy 6 perc van hatra,
kozbe irja hogy time expired azzal parhuzamosan...
nagyon szep megoldasa van kulonben
6 perc van megoldani, bekuldessel egyutt, szoval olyan megoldas kell,
ami kb 5 perc alatt lefut
enyem O(n^2*log(n)), es kb 5 mp alatt lefut a nagy inputfajlra, amiben
kb 45 bazinagy eset van
nem szeretnem elarulni megoldast (majd jovohet penteken), csak
sejtesekrol par szo:
- tenyleg nem szamit hogy ki mit lep, mindenkepp ugyanaz nyer (sot a
lepesszam is azonos mindig)
- a masik sejtes nem igaz, hogy 1-et irhatunk akarmilyen pozitiv szam
helyett (pl "0 -1 1 0"-ra 1 lepes utan van vege, amig "0 -1 2 0"-ra 2
lepes utan van vege)
ngg
_______________________________________________
acm-valogato mailing list
acm-valogato(a)sziami.cs.bme.hu
http://sziami.cs.bme.hu/mailman/listinfo/acm-valogato
11:42 a.m.
New subject: [acm-valogato] Safest-place -- 2D-ben, quad-tree demonstráció
nagyon szep vizualizacio lett, kosz :P
3d-ben voronoi diagram az sajnos lassu es nagyon nem trivialis,
megprobaltam egy elore megirt (voro++) programmal megoldani, de egy
picit is nagyobb peldara 24 giga ramot kezdett el hasznalni, es orakig
ment, ami nem jo na
kulonben irtam ra backtrackes oct-tree-t, es rendes inputra kevesebb
mint 1 sec alatt lefut, szoval nem kell branch-and-bound
Engedy, Balazs <engedy.balazs(a)gmail.com> írta (2011. március 19. 1:18):
Sziasztok!
Én pedig a maximális minimum távolságos "Safest Place" feladattal
foglalkoztam egy kicsit. Csináltam hozzá C#-ban egy kis szemléltető
programocskát [1], ami persze tesztelni is jó, hogy miként alakul a rács.
Hogy jól vizualizálható legyen, ez csak 2D-ben működik, így oct-tree helyett
quad-tree-t használ, de a működése alapelvét tekintve ugyanaz, mint a 3D
verziónak.
Közben amúgy rájöttem, hogy egy jó megoldás kapható úgy is, ha építünk a
pontokra egy Voronoi-diagramot ([2]), ennek ugyanis valamelyik csúcspontja
lesz a megoldás. Persze nem valószínű, hogy valakinek ezt lenne ideje
lekódolni...
[1]: http://cs.bme.hu/acm/felkeszito2011/05/SafestPlaceVisu.zip
[2]: http://en.wikipedia.org/wiki/Voronoi_diagram
Üdv,
Balázs
On Fri, 18 Mar 2011 23:01:07 +0100, NGG <ngg(a)ngg.hu> wrote:
megcsinaltam alien gamet, de nem tudtam
bekuldeni, mert szar a
bekuldorendszeruk es amig szamol visszafele hogy 6 perc van hatra,
kozbe irja hogy time expired azzal parhuzamosan...
nagyon szep megoldasa van kulonben
6 perc van megoldani, bekuldessel egyutt, szoval olyan megoldas kell,
ami kb 5 perc alatt lefut
enyem O(n^2*log(n)), es kb 5 mp alatt lefut a nagy inputfajlra, amiben
kb 45 bazinagy eset van
nem szeretnem elarulni megoldast (majd jovohet penteken), csak
sejtesekrol par szo:
- tenyleg nem szamit hogy ki mit lep, mindenkepp ugyanaz nyer (sot a
lepesszam is azonos mindig)
- a masik sejtes nem igaz, hogy 1-et irhatunk akarmilyen pozitiv szam
helyett (pl "0 -1 1 0"-ra 1 lepes utan van vege, amig "0 -1 2 0"-ra 2
lepes utan van vege)
ngg
_______________________________________________
acm-valogato mailing list
acm-valogato(a)sziami.cs.bme.hu
http://sziami.cs.bme.hu/mailman/listinfo/acm-valogato
_______________________________________________
acm-valogato mailing list
acm-valogato(a)sziami.cs.bme.hu
http://sziami.cs.bme.hu/mailman/listinfo/acm-valogato
11:51 a.m.
New subject: [acm-valogato] Safest-place -- 2D-ben, quad-tree demonstráció
Sziasztok!
Örülök, hogy tetszik :).
A "sima backtraces" oct-tree alatt mi értesz?
Üdv,
Balázs
2011/3/19 NGG <ngg(a)ngg.hu>
nagyon szep vizualizacio lett, kosz :P
3d-ben voronoi diagram az sajnos lassu es nagyon nem trivialis,
megprobaltam egy elore megirt (voro++) programmal megoldani, de egy
picit is nagyobb peldara 24 giga ramot kezdett el hasznalni, es orakig
ment, ami nem jo na
kulonben irtam ra backtrackes oct-tree-t, es rendes inputra kevesebb
mint 1 sec alatt lefut, szoval nem kell branch-and-bound
Engedy, Balazs <engedy.balazs(a)gmail.com> írta (2011. március 19. 1:18):
Sziasztok!
Én pedig a maximális minimum távolságos "Safest Place" feladattal
foglalkoztam egy kicsit. Csináltam hozzá C#-ban egy kis szemléltető
programocskát [1], ami persze tesztelni is jó, hogy miként alakul a rács.
Hogy jól vizualizálható legyen, ez csak 2D-ben működik, így oct-tree
helyett
quad-tree-t használ, de a működése alapelvét
tekintve ugyanaz, mint a 3D
verziónak.
Közben amúgy rájöttem, hogy egy jó megoldás kapható úgy is, ha építünk a
pontokra egy Voronoi-diagramot ([2]), ennek ugyanis valamelyik
csúcspontja
lesz a megoldás. Persze nem valószínű, hogy
valakinek ezt lenne ideje
lekódolni...
[1]: http://cs.bme.hu/acm/felkeszito2011/05/SafestPlaceVisu.zip
[2]: http://en.wikipedia.org/wiki/Voronoi_diagram
Üdv,
Balázs
On Fri, 18 Mar 2011 23:01:07 +0100, NGG <ngg(a)ngg.hu> wrote:
_______________________________________________
acm-valogato mailing list
acm-valogato(a)sziami.cs.bme.hu
http://sziami.cs.bme.hu/mailman/listinfo/acm-valogato
megcsinaltam alien gamet, de nem tudtam
bekuldeni, mert szar a
bekuldorendszeruk es amig szamol visszafele hogy 6 perc van hatra,
kozbe irja hogy time expired azzal parhuzamosan...
nagyon szep megoldasa van kulonben
6 perc van megoldani, bekuldessel egyutt, szoval olyan megoldas kell,
ami kb 5 perc alatt lefut
enyem O(n^2*log(n)), es kb 5 mp alatt lefut a nagy inputfajlra, amiben
kb 45 bazinagy eset van
nem szeretnem elarulni megoldast (majd jovohet penteken), csak
sejtesekrol par szo:
- tenyleg nem szamit hogy ki mit lep, mindenkepp ugyanaz nyer (sot a
lepesszam is azonos mindig)
- a masik sejtes nem igaz, hogy 1-et irhatunk akarmilyen pozitiv szam
helyett (pl "0 -1 1 0"-ra 1 lepes utan van vege, amig "0 -1 2 0"-ra 2
lepes utan van vege)
ngg
_______________________________________________
acm-valogato mailing list
acm-valogato(a)sziami.cs.bme.hu
http://sziami.cs.bme.hu/mailman/listinfo/acm-valogato
_______________________________________________
acm-valogato mailing list
acm-valogato(a)sziami.cs.bme.hu
http://sziami.cs.bme.hu/mailman/listinfo/acm-valogato
5261
days inactive
5262
days old
3 comments
2 participants
participants (2)
-
Engedy, Balazs -
NGG