Selejtező megoldások

Megkértünk pár csapatot, hogy meséljék el, hogyan álltak neki, milyen nehézséggel találkoztak a feladatok megoldása közben. A csapatok hozzájárultak a megosztásukhoz, illetve párnál még a forrást is megtaláljátok.

A csapatoknak még egyszer köszönjük a hozzájárulást ;)

Autópálya

" URam, [..] ismertesd meg velem, melyik úton járjak, mert hozzád vágyódik lelkem. " / Zsoltárok 143:8 /

A feladat fő nehézsége szerintünk az, hogy az autópályához felhasználható szakaszok száma a városok számának négyzetével arányos, és míg ezen szakaszok nagy része emberi szemmel nézve nyilvánvalóan kizárható, algoritmikusan ezt megtenni egyáltalán nem egyszerű feladat.

Két megoldást is készítettünk, az első úgy működött, hogy elkészíti a városokhoz, mint síkbeli pontokhoz tartozó Delaunay-féle háromszögelést, mely a városok számával arányos mennyiségű szakaszt tartalmaz csak, és biztosan tartalmazza a legrövidebb szakaszt és a minimális összhosszú feszítőfát. Utóbbit könnyű megkeresni pl Kruskal algoritmussal, aztán ha ez tartalmaz K hosszú vonalat, azt adjuk vissza, egyébként pedig az elágazásoknál szétbontjuk szakaszokra, és azokból kombinálunk K hosszú vonalat. Megjegyezzük, hogy ez a módszer, a végleges megoldásunknál ismertett "keresztező élek" kiszedésével általában 15-25%-al jobb eredményt adott, mint a leadott megoldásunk, csak valami oknál fogva a szerveren szinte egyik esetre sem futott le, pedig a saját gépeinken nem volt memória/időhiány :(

Ez a probléma nem tántorított el, így elkészítettük a következő, jóval egyszerűbb megoldást: a városokhoz azonosítószámokat rendeltünk, melyeket két módon láncoltunk: az (x,y) koordináták szerinti kanonikus sorrendben és az (y,x) koordináták szerinti kanonikus sorrendben. Egy tetszőleges kezdőpontból indulva építünk mohó algoritmussal egy láncot az összes városból a következő stratégiával: mindkét végpontnak megnézzük a két láncolás szerinti valahány szomszédját, és kiválasztjuk a legközelebbit, melyet hozzácsatolunk a városlánchoz. Ezután kivesszük az azonosítóját a szomszédságok közül. Miután így láncba fűztük az összes várost, megkeressük a legrövidebb K hosszú vonalat. Ennek a mohó algoritmusnak az a hátránya, hogy miközben lépésenként a legrövidebb szakaszt igyekszik hozzávenni az úthoz, előfordul, hogy elfogynak az igazán közeli szomszédok, és így olyan szakaszt vesz fel, mely viszonylag hosszú és több korábbi szakaszt keresztez. Ezeket a "keresztező éleket" nagyrészt el tudjuk távolítani: a végén megkeressük azokat a szakaszokat, melyek az átlagos szakaszhossznál lényegesen hosszabbak, és hozzá azt a szakaszt, melyet kereszteznek, majd ezek végpontjainál újraláncoljuk a vonalakat, hogy ne legyen keresztezés - ez garantáltan rövidíti a végleges vonalat.

Állítható paraméterek: kezdőpont, hány darab szomszédot vizsgáljunk meg a láncoláskor, mennyivel hosszabb szakaszokra keressünk keresztező szakaszt. A megoldásban K értéke szerintire állítottuk a szomszédszámot és a hosszarányt a számítási idő jobb kihasználása érdekében, a kezdőpont-választással nem foglalkoztunk.

A megoldás tovább javítható két stratégiával: több kezdőpontra alkalmazzuk a fenti algoritmust és kiválasztjuk a legjobb eredményt; valamint további két "átlós" szomszédsági lánc is készíthető a városokhoz, ami a mohó stratégiát tovább javítja.

Sajnáljuk, hogy az első megoldásunk nem vált be, mert az lényegesen jobb eredményeket ad. A második megközelítésnél a hatékony implementáció volt a kulcs, mely lehetővé tette viszonylag nagy szomszédszám vizsgálatát, és a hosszúak mellett még a viszonylag rövid keresztező szakaszok kiszedését is.

Forrás letöltése
Zsoltárok megoldása

Intervallumok

Először beolvastuk az intervallumokat. Az intervallumok végpontjainak összehasonlítása alapján eldöntöttük, hogy a reláció csak részben vagy teljes rendezés.

Ez az ellenőrzés abból állt, hogy a bemeneti listában szomszédos intervallumok kezdőpontjait összehasonlítottuk. Ha találtunk egy nem összehasonlítható párt, akkor

nem vizsgáltuk tovább, mert nem lehet teljes rendezés.

Teljes rendezés esetén:

Rendeztük az intervallumok végpontjait merge sort-al. Kiszámoltuk, hogy ezek intervallumpontok mennyi intervallumban vannak benne (ez a számítás nem járt további összehasonlítással).

Minden pontra bináris kereséssel megkerestük a legkisebb olyan intervallum pontot amelyiknél nagyobb vagy egyenlő. Ebből már meg lehetett határozni, hogy a pontot mennyi intervallum tartalmazza.

Részben rendezés esetén:

Minden pontra végigmentünk az összes intervallumon és egyesével megnéztük tartalmazza-e a pontot.

Gyorsítások:

Nyers adatok kinyerése (ValueString): Először beolvastuk stringstream/string-be a intervallumok/pontok nyers értéket, majd csak utána adtuk át a Value osztálynak. A nyers értéket lehetett másolni és lehetett vele egyenlőséget vizsgálni .

Válaszok cache-elése: Ha egy pontra már kiszámoltuk mennyi intervallumban van benne, akkor elmentettük a választ a ValueString segítségével. Későbbi pontoknál a ValueString alapján kikerestünk a cache-ből, és ha tartalmazta, akkor összehasonlítás nélkül ki lehetett írni a helyes választ.

Összehasonlítások cache-elése: ValueString alapján lehetett azonosítani a Value-kat, igy el lehetett menteni az összehasonlítások eredmenyét. Továbbá 1 lépéses tranzitivitást is megengedtünk, azaz ha x<=y eredménye nincs a cache-ben, de x<=z és z<=y igen és mindkettő igaz értékkel, akkor valódi összehasonlítás nélkül is tudjuk, hogy x<=y igaz.

Duplikációk kiszűrése: ValueString alapján szűrtünk.

Részben rendezésnél partícionálás: Ezt a gyorsítást csak akkor használtuk, ha keresett pontok száma legalább két nagyságrenddel nagyobb volt, mint az intervallumok száma. Az összes intervallumra meghatároztuk, hogy mely másik intervallumnál kisebbek. Pl "a" intervallum [a1, a2] kisebb "b" intervallumnál [b1, b2], ha a2 <= b1. Ha egy keresett x pontra nem volt igaz az a1<=x, akkor az összes nála nagyobb intervallumot is ki lehetett zárni,

Saját streambuffer osztály: Az egyik feladatnál csak az adatok beolvasása több mint 40 másodpercig tartott hagyományos módszerrel. A saját osztályunk 4kB-os blokkokban olvasott az inputról, ezzel jelentősen gyorsítva a beolvasást.

Syntax Terror megoldása

Tervrajzok

A nagy pályaméret miatt rögtön heurisztikában kezdtem gondolkodni. Visszalépéses technikát vagy más időigényes módszert csak jóval kisebb elemszámnál fontoltam volna meg.

Csúcsnak nevezem a bal felső sarkát minden olyan beugrásnak, ahová tervrajzot lehetne rakni. Az 1. ábrán pl. 3. db csúcs van.

A heurisztika az, hogy a csúcsok számát igyekszem minimálisan tartani. Minden csúcshoz bepróbáltam az összes még szabad tervrajzot, és kiválasztottam a legjobbat az alábbi értékelés szerint:

Legjobb a csúcsmegszüntetés. Pl. a B csúcsot úgy lehet megszüntetni, ha találunk egy vékony vonallal jelölt méretű tervrajzot. (2. ábra)

Ha csökkenteni nem tudom a csúcsszámot, akkor legalább ne növeljem. Azaz olyan elemet keresek, ami legalább az egyik irányban megfelelő méretű (3. ábra)

Ha ilyen sincs, akkor a legnagyobb olyan darabot teszem le, ami még nem log túl. Ilyenkor új csúcs jön létre. (4. ábra)

Ilyet nem csinálok (5. ábra).

Ha nem tudok már semmit lerakni, akkor a legkisebb lyukat teszem le, ami megszüntet egy csúcsot. (Szintén a 2 es ábra, csak most nem teszek oda semmit, hanem beletörődök, hogy az a rész üresen marad.)

Random pályán a 6. ábrán látható eredményt kapjuk.

Aminek a jobb alsó sarkát kinagyítva (7. ábra) láthatjuk, hogy még maradtak pici le nem fedett területek. Nekem a hasonló feladatoknál mindig nagy segítséget jelent, ha ki is rajzolom az eredményt.

Természetesen egy tervrajz lerakása után csak a szükséges dolgokat frissítettem, azokat a csúcsokat nem amelyekre a lerakás nem volt hatással. Igy bármely pályát 1 secnél rövidebb idő alatt megold.

A fenti módszerrel sikerült 100 pontot kapni, azért a biztonság kedvéért tettem bele még egy optimalizálást. A legnagyobb lerakható elemet többféleképp lehet definiálni. Pl. legnagyobb terület, a két oldal összege vagy a hosszabb oldal 5-szöröset + a rövidebb oldal. A 6-os ábrán olyan függvényt alkalmaztam, ami a hosszabbik oldalt erősen preferálja. Ha 10 féle értékelőfüggvénnyel lefuttatom, mindig picit más eredményt kapok, és ezek közül ki lehet választani a legjobb megoldást.

Delphi forever megoldása

Az első fázisban egy egyszerű Guillotin algoritmust alkalmaztunk egy előzetes terület alapján történő csökkenő rendezést. Az algoritmus alapján számon kell tartani téglalap alakú tartályokat, amik az üres helyeket tartalmazzák. Az elején egy tartály van, ami magába foglalja az egész területet. Minden iterációnál vettük a következő rajzot csökkenő sorrendben, amihez megkerestük az olyan legkisebb területű tartályt, amibe még belefér a rajz. Amennyiben nincs ilyen, véget ér a futás. Amikor találunk egyet, akkor annak bal alsó sarkába helyezzük a rajzot, majd a tartály maradék területét két tartályra bontjuk szét: a vágáshoz (split) többféle stratégia is tartozhat. Először forgatás nélkül próbáltuk elhelyezni a rajzokat, a maradék rajzokat pedig forgatva.

Az alap Guillotin Bin packing program még csak a 14. helyre vitt minket 3 nappal a verseny vége előtt, de még nagy lehetőségek rejlettek benne: nagyon gyors volt. Az eredeti algoritmusban lehetett változtatni, hogy az az egyes tervek berakása utáni split műveleteket melyik tengely szerint végezzük el, és a tervek sorrendjét is. Hát változtattuk. A splitet két féle képpen próbáltuk, vagy, hogy mindig a hosszabb megmaradó oldalé legyen a nagyobb rész, vagy hogy minél nagyobb terület maradjon. A tervek sorrendjére pedig 9 külön verziónk volt:

  • Növekvő/csökkenő területtel
  • Növekvő/csökkenő szélességgel
  • Növekvő/csökkenő magassággal
  • Minél inkább négyzetszerű (hosszabb/rövidebb oldal)/ minél kevésbé négyzetszerű, és szélesség/magasság szerint növekvőben.

Ezzel 18 féle módon futtattuk az eredeti guillotin algoritmust, ami közül kiválasztottuk a legjobbat.

Ez már olyan pontszámot adott, amivel elégedettek voltunk, 99.

A feladat elkészítése során azt a konkluziót vontuk le, hogy előnyös egy olyan gyors algoritmust implementálni, aminek lehet többféle paramétere, mivel ilyenkor többféle módon is lehet futtatni, aztán kiválasztani a legjobbat. Így minél több típusú esetet le tudjuk fedni.

Csirkés piskóta csapat megoldása

Az algoritmus leírása:

Betöltés után terület szerint csökkenő sorrendben rendezzük a inputként kapott tervrajzokat. Nyilvántartjuk egy vectorban a szabad területeket, kezdetben egy téglalap lesz benne, a teljes pálya.

Az inputként kapott tervrajzokat terület szerint csökkenő sorrendben próbáljuk elhelyezni a még szabad területek egyikén. A szabad területet úgy választjuk ki, hogy a legjobban kitöltse az aktuális tervrajz, és lehetőleg ne kelljen forgatni. Ezt úgy oldjuk meg, hogy először sorba rendezzük a szabad helyeket kitöltési arány szerint csökkenő sorrendben, majd végigmegyünk a szabad helyeken, és ha forgatás nélkül befér a tervrajz valamelyikbe, akkor elhelyezzük. Ha nem fért el, akkor újra végignézzük a szabadhelyeket, hogy forgatással elfér-e. A kiválasztott szabad hely a bal felső sarkába lehelyezzük a tervrajzot.

Mielőtt a következő tervrajzzal foglalkoznánk, karbantartjuk a szabad helyek vectorát. Minden szabad területet, amit metsz a lehelyezett tervrajz, felbontunk kisebb téglalapokra az alábbi ábra szerint.

Tehát ha egy terület közepét metszi a lehelyezett tervrajz, akkor felette, alatta, balra, és jobbra lesz egy-egy új szabadhely. Ezek között mint látható átfedés lesz. A lényeg, hogy egy-egy szabad hely a legnagyobb ott lehelyezhető tervrajzot reprezentálja. Valójában általában kevesebb új szabad hely jön létre. Mivel például a kiválasztott szabad hely bal felső sarkába helyezzük le a tervrajzot, ott csak kettő. Lásd alábbi ábra.

Felbontás után az eredeti szabad helyet töröljük. Felbontások utána pedig még végigmegyünk a szabad helyeken, és ha olyat látunk, hogy egy szabad hely teljes mértékben tartalmaz egy másikat, akkor a kisebbet töröljük.

Ez után megyünk a következő tervrajzra.

Az algoritmus debugolására készíthető körönként egy-egy svg export, ami fehérrel négyzetrácsosan megjeleníti a lehelyezett tervrajzokat, illetve áttetsző kékkel a szabad helyeket jelző téglalapokat. Az alábbi ábrán látható egy megoldás három egymás utáni állapota:

Az algoritmus egyébként nagyon hamar összeállt. Amint elkészült, és a szabad helyek karbantartása is jól működött, feltöltöttük, és 100 pontot kaptunk érte. Az utolsó napokig nem is nyúltunk hozzá, amikor már csak 98 pontot ért. Akkor egy kicsit próbálkoztunk még a szabadhelyez rendezésén változtatni, illetve próbálkoztunk azzal is, hogy ne mindig a szabad helyek bal felső sarkába helyezze el a tervrajzot, de nem hozott jobb eredményt, és inkább másik feladatra koncentráltunk.

Forrás letöltése
Utolsó csapat megoldása

Világítás

Gyors algoritmust írtunk, hogy egy feladat megoldásakor többféle paraméterezéssel futtathassuk. Ezen futások legjobb eredményét adja vissza a program.

Az alap algoritmus az volt, hogy:

1. hagyományos 10-es lámpát rak le addig amíg tud
2. majd spot lámpákat rak le azokra a helyekre ahová nem jutott elég fény
3. ezután a 10-es hagyományos lámpákat lecseréli 5-ösre ahol lehet
4. majd az 5-ös lámpákat cseréli le 3-asra, ahol lehet

A 12 féle paraméterezés:

1. Milyen sorrendben járjuk be az épületet:
a) soronként haladva fentről lefelé
b) belülről haladva körkörösen kifelé
c) kívülről haladva körkörösen befelé

2. A mezők bejárásakor a következő mező, aminek a teljes megvilágításához teszünk le lámpát, az a mező:
a) amely még nincs teljesen megvilágítva
b) amely még nincs teljesen megvilágítva és le lehet rakni arra a mezőre lámpát

3. Lámpa lerakásakor hogyan határozza meg a lerakás értékét:
a) minél több "hasznos" megvilágítás
b) minél több teljesen megvilágított mező

Ezen paraméterek kombinációjából jön ki a 12-féle paraméterezés (3x2x2).

Példa az értékfüggvényekre egy 8x4 -es pályán, ahol mindegyik mezőt 6-ra kell megvilágítani:

A fenti példában ha soronként megy végig a mezőkön, akkor a (3,0)-ás mezővel kezdi mindenképp, mert nincs megvilágítva és lehet lerakni lámpát.

Ha teljesen meg akarjuk világítani a mezőt (6-ra), akkor letehetjük a lámpát, a 0-ás sorban bárhova, vagy a 3-as oszlopban bárhova. A (3,1) mező lesz a legjobb bármelyik értékfüggvénnyel.

A következő, amit teljesen meg kell világítani az a (4,0) mező. Hasonlítsunk össze két lámpa lerakást:

1. (4,0) mezőre rakjunk le (zöld színnel a hasznos megvilágítás):

-> Ezzel a lerakással 5 mezőt világítunk meg teljesen (3/b értékfüggvény), hasznos világítás 30 (3/a értékfüggvény).

2. (4,2) mezőre rakjunk le (zöld színnel a hasznos megvilágítás):

-> Ezzel a lerakással 3 mezőt világítunk meg teljesen (3/b értékfüggvény), hasznos világítás 32 (3/a értékfüggvény).

Tehát a 3/a értékfüggvény alapján a (4,2) mezőre kellene rakni, a 3/b alapján a (4,0) mezőre.

Syntax Terror megoldása

A megoldásunk a következőt csinálja:

Megkeresi azt a mező-lámpaméret párost, ahova a legjobban megéri hagyományos lámpát tenni egy eval alapján.

Leteszi ide a lámpát.

Mindezt addig csinálja, amíg a legnagyobb eval nagyobb, mint nulla. Ezután azokra a mezőkre, amik nincsenek eléggé megvilágítva tesz egy spot lámpát.

Egy placement evalja a következőkből áll:

  • a teljesen megvilágított mezők száma * 1000
  • lámpasugár * -10
  • nem teljesen megvilágított mezőknek a teljes megvilágítottságához szükséges fényerő * -1

Mivel ez O(N*M * N * M), az utolsó tíz tesztesetre nem futott le időben, ezért optimalizálni kellett rajta.

Létrehoztunk egy cachet, ami egy multi_mapben tárolja a mezőket. A kulcs a mező evalja, az érték a mező és a lámpasugár méretéből létrehozott hash érték. Így O(1) alatt meg lehet találni a legnagyobb evallal rendelkező mezőt.

Ha lerakunk egy lámpát egy mezőre a környező mezők evalja megváltozhat. Ha letett lámpa megvilágít egy mezőt, annak az evalja nullára csökken, mivel oda már nem tehetünk másik hagyományos lámpát. Ha keresztezi egy másik placement mezőit, akkor annak az változni fog. Ha valamelyik érintett mező megvilágítottsága eléri a szükséges mértéket az már 0-t ér az evalban, ha nem, akkor annak evalja megnő, mert a vizsgált placement már lehet, hogy eléggé meg tudja világítani.

Hogy az evalt up-to-date tudjuk tartani a maximum keresésére használt multi_mapben, használunk még egy tárolót. Ez egy unordered_map, melynek a kulcsa a mező poziciójából és a lámpasugárból képzett hash, az értéke pedig a multi_map egy nodejára mutató iterator.

Amikor leteszünk egy lámpát, megkeressük az összes mező-lámpaméret párost, melynek az evalja megváltozott. Ezeket kivesszük a multi_setből és visszarakjuk az új evallal, ha amennyiben az eval nagyobb, mint nulla. A hash_mapben updateljük a multi_map iteratort.

Amikor egy lámpát lerakunk, az érintett mezők evalját nem a nulláról számuljuk ki. Csak azt a komponensét updateljük, amelyik megváltozhatott. Végigmegyünk az összes olyan mezőn, amit megvilágít a letett lámpa. Megnézzük, hogy ezeket a mezőket, mely másik mezőre letett lámpa világítja meg és ezeket az eval komponenseket updateljük. A szomszédos és érintett mezők cachelésére szintén használunk 1-1 tárolót.

Így sikerült elérni, hogy 19/20 pályán lefusson időben a megoldás. A 20. pályán nem update-elődik az eval, így ott is lefut időben, bár nem optimális megoldást ad.

if (N < 990 || K < 990 ) update_eval() :)

javascript expert team megoldása

Résztvevők

88
Cevert
87
Elvis
86
Spontaneus
Budapesti Műszaki és Gazdaságtudományi Egyetem
85
Booldogs
Veres Péter Gimnázium
84
4everalon3
83
Girc
82
Nindzsák
81
Nincs
80
Nagy Jamaikai Törpe Poloska
Pannon Egyetem
79
Insert name here
Pannon Egyetem