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 ;)

Labirintus

A feladat nem tűnt nehéznek, ami miatt többször kellett próbálkoznunk, az a furcsa számozás (1-gyel kezdve, valamint az oszlopok balról jobbra nem is monoton nőttek), illetve később került bele a kiírásba, hogy rendezve kell kiírni az eredményt.

Algoritmus

Ellenőrizve, működik:

Bemenetből mezők létrehozása úgy, hogy extra üres mezők vannak a kerületen.
A számozás saját, a sorszámozás maradt (az extra üres sor lett a 0.), az oszlopszámozás viszont monoton nő balról jobbra (az első extra üres oszlop a 0.).
Minden mezőnek beállítjuk a fizikai szomszédait, vagyis az élszomszédos mezőket, a kerületen levő üreseknek a még kijjebbiek pedig NULL-ok.
Utána minden mezőnek összeszedjük a logikai szomszédait, vagyis azon mezőket, amire onnan lépni lehet. A kerületen levő üresekből csak monitorra vagy rendes üres mezőre lehet lépni.
Egy ciklussal meghatározzuk, hogy melyik mezőt hány lépésben lehet elérni egy kerületen levő üresből. Ehhez minden mező tárolja ezt a távolságszámot, és a későbbi lépdelésért azt a logikai szomszédot, ahonnan oda lehet lépni és ennyi lesz az eredmény. A kerületen levő üresek számát 0-ra inicializáljuk. Egy priority queue-ba betesszük a kerületen levő üreseket. A priority queue a lépésszám szerint rendez, top-on a legkevesebb.
Minden ciklusban kivesszük a queue első elemét, és azon logikai szomszédainak beállítjuk 1-gyel az övénél nagyobbra a számot, akiknek még nincs beállítva. Mindig, amikor beállítunk egy mezőnek számot, akkor azt betesszük a queue-ba. Addig megy a ciklus, amíg van elem a queue-ban. Közben mindig megjegyezzük, hogy melyik az a legnagyobb lépésszám, amivel kintről mező elérhető.
A végén minden mezőre meglesz, hogy kintről legalább mennyi lépéssel lehet elérni, és tudni fogjuk, hogy mennyi a legnagyobb ilyen lépésszám. Így egy ciklussal még összeszedjük azokat a mezőket, amiknek megegyezik a lépésszámértékük ezzel a legnagyobb értékkel.
Print, done.

Ellenőrzés

A mintapéldára jó volt, de csináltam egy Qt-s GUI-t, ahol lehet térképet load-olni, save-elni, random generálni és természetesen kirajzolja. Mezőre kattintva az exitPath-t is berajzolja, így a lépésszámok és az útvonal is ellenőrizhető. Derültek ki apró hibák, de a fenti algoritmus jónak bizonyult.

Forrás letöltése

Mazeshetek megoldása

A feladat megoldásakor hamar eldöntöttük, hogy szélességi bejárással fogjuk megoldani a problémát. Ehhez a labirintus négy oldalán felvettünk további cellákat, melyekből 0 lépéssel tudunk kijutni a labirintusból. Ezekből a cellákból indulva jártuk be befelé a labirintust.

A gráf éleit, vagyis hogy egy cellából mely cellákra tudunk lépni közvetlenül, nem számítottuk ki előre, a bejárás során vizsgáltuk hogy hova léphetünk.

Minden cellához tároltuk azt is, hogy melyik irányokból látogattuk már meg, hiszen ha egyszer már egy adott irányból bejártuk, akkor az összes “mögötte lévő” és közvetlen elérhető cellában is voltunk.

Miután a bejárás végzett és minden cellának ismertük a labirintus szélétől való távolságát, megkerestük a maximális távolságú, de elérhető cellákat.

Forrás letöltése

asdf megoldása

A labirintus hatszögletű mezőkből állt, ezért az egyszerűség kedvéért gráffá alakítottuk.

A csúcsok a mezők voltak, az élek pedig, hogy egy lépéssel melyik mezőbe lehet eljutni. Minden él súlyát 1-nek vettük.

Az egy irányban lévő mezőket kiszámító függvényhez unit tesztet írtunk, hogy biztosak legyünk a helyességében.

1 távolságúnak vettük azokat a mezőket amelyekről 1 lépéssel ki lehet jutni, majd egy útkereső algoritmust futtattunk és így kerestük meg a kijáratoktól a legtávolabb lévő mezőket.

A labirintushoz egy JS/HTML megjelenítőt is készítettünk, hogy az eredményt könnyebben ellenőrizzük, ezzel a megjelenítővel labirintus bemeneteket is tudtunk tervezni.

Az első kiértékeléseknél kiderült túl lassú az implementáció, ezért készítettünk egy maximális méretű labirintust, amiben csak monitor mezők voltak és ezzel mértük a sebességet.

Syntax Error Team megoldása

Iskolabusz

A következő megközelítésekkel próbálkoztunk. Mindegyiknél először lekódoltuk szépen és érthetően, majd addig tömörítettük, amíg tudtuk.

Brute

Lefoglalunk egy N méretű tömböt a heap-en, és úgy inicializáljuk, hogy még mindegyik gyerek otthon van. A sofőr elindul, nyilván tartjuk, hogy elment-e már gyerek mellett, és ha már elment valaki mellett, de odaért a következőhöz, akkor felveszi. Addig megy a sofőr, amíg van gyerek, a végén kilép a ciklus és egy változóban benne lesz az utoljára felvett gyerek. Amellet hogy ez az algoritmus elég lassú, csak 170 karakterig sikerült tömöríteni.

Smart

Itt már nem minden lépését követjük a sofőrnek, hanem minden körét. Ugyanis a kör kezdéséből, és hogy hányadik, meg lehet mondani, hogy a legnagyobb sorszámú megmaradt gyereket veszi fel, vagy a közvetlen előtte levőt. Majd mehet a következő kör.

Legyen a mindenkori legnagyobb szám: L.

Legyen a mindenkori darabszám: C.

Legyen M az, amekkora lépésközök a számok között vannak (Két szomszédos szám különbsége).

Legyen D az a bool érték, hogy az adott körben az első elemmel kezdünk-e.

Az algoritmus:

C=N, L=N, M=1, D=true
While 1 < C:
Ha ((D==true && (C%2)!=0) || (D==false && (C%2)==0))
Ekkor el fogjuk távolítani a legnagyobbat (L)
L=L-M, newD=false
Különben:
Ekkor nem fogjuk eltávolítani a legnagyobbat (L)
newD=true
Ha (D==true || (C%2)==0)
Ekkor a számok fele marad meg el
C=C/2
Különben
Ekkor a számok felénél 1-gyel több darab marad meg
C=C/2+1
M=2*M
D=newD
A végén L tartalmazza a legutolsó felvett gyerek számát.

Ezt az algoritmust már 118 karakterig sikerült összenyomni, de még a többi csapat pontszámából láttuk, hogy van hova továbbfejlődni.

Josephus

Ezen linkből (https://en.wikipedia.org/wiki/Josephus_problem#k.3D2) kiindulva azt találtuk ki, hogy a megoldás: 2*N-h, ahol h az a legkisebb kettő hatvány, ami nagyobb (N-1)-nél. Ez valójában a következő algoritmus tömör változata:

Ha N kettő hatvány
a megoldás N
Különben
a megoldás 2*N-h, ahol h az a legkisebb kettő hatvány, ami nagyobb N-nél.

vagyis ekkor N-nek a legfelső 1-es bitjét 0-ra kell változtatni, majd az egészet shiftelni 1-gyel balra

Sajnos h kiszámolásához egy ciklusra volt szükségünk.

Ez lett a végső megoldásunk, 78 karakterig sikerült lemenni.

Float

A Josephus algoritmusra csak 98 pontot kaptuk, volt csapat, aki 99-et, és olyan, aki 100-at is bezsebelt. Ebből láttuk, hogy legalább 2 karaktert lehet még javítani. A Josephus algoritmus már annyira tömörnek tűnt, hogy teljesen új megközelítést láttunk szükségesnek.

Arra gondoltunk, hogy a Josephusban szükség van az (N-1)-nél nagyobb, de legkisebb 2-hatványra. Ha (N-1)-et egy float változóban tároljuk, akkor (int*)-gal ránézve shifteléssel kiszedhető az exponens, amiből egy újabb shifteléssel előállítható a szükséges 2-hatvány. Ez túl sok karakterrel sikerült csak.

Log2

A float-hoz hasonlóan szintén h értékét akartuk meghatározni, csak log2() függvényekkel. Sajnos ezekhez még egy include kellett, ami már megint túl sok lett.

Egyéb

A végső verziónkban #include

<iostream> szerepel, std::cin >> N; a beolvasás, valamint std::cout << 2*N-h; a kiírás.

Próbáltunk tömöríteni úgy, hogy valami olyan dolgot include-olni, ami rövidebb, mint az iostream, de berántja azt is. Ilyet nem találtunk.

Printf() használata is szóba került, de az is hosszabb a formátumsztring miatt.

Forrás letöltése

Mazeshetek megoldása

A feladat megoldásához először írtunk egy naiv megoldást, amelynek csak az volt a célja, hogy valamilyen mintát felfedezzünk a megoldások között. Miután már láttuk a mintát (azaz, hogy 1 esetén a válasz is 1, 2-től kezdve pedig 2-ről indulva kettesével növekedik az eredmény, de minden kettő hatvány után újra visszaugrik 2-re) a megoldásokban, a feladattól függetlenül olyan kódot próbáltunk írni, amely a mintának megfelelően ad eredményt.

Először megírtuk a kódot, ami megkereste az adott számnál nem kisebb kettő hatványt, majd az eredeti szám kétszereséből kivonva éppen az eredményt adta. Ezután az interneten kerestünk további tippeket, hogy hogyan lehetne rövidíteni. Utánanéztünk a C++ szabványoknak és magának a g++ fordítónak is, hogy mi megengedett és mi nem. Így jöttünk rá, hogy elhagyható a main függvény elől az int kulcsszó, vagy #include helyett kompaktabb a #import-ot használni. Így jutottunk el végül a 77 karakteres kódig.

Forrás letöltése

asdf megoldása

Papíron felirtuk az első 20 bemenetre az eredményt és abból már látszódott a minta. Írtunk egy iterativ verziót az első 10000 értékre, és megírtuk az első változatot a képletes megoldásra és egybevetettük a kimeneteket. Később a neten is megtaláltuk ezt a problémát. Ezután már csak a kód lerövidítése volt hátra, ebben segítettek a neten fellelhető c++-os code golf tippek.

Syntax Error Team megoldása

Tópart

Adatstruktúra

Két osztályt használunk. Az Edge a gráf egy élét írja le (hossz, kiinduló- és cél város pointer, komp-e), a Node pedig egy várost (név és Edge vector, ami az innen induló utakat tartalmazza). Egy Node első Edge-e mindig a bringautat tartalmazza.

A Node-okból egy tömböt tárolunk, ezen oldja meg a feladatot az algoritmus.

Beolvasás

A beolvasás során városnevek alapján meg kell találni a megfelelő Node-ot. Ehhez egy segéd std::map-ot használunk, mert a for ciklusos módszer nagyon lassú volt.

A beolvasás végén a kiindulási Node-ot szétszedjük egy start és egy stop Node-ra. A start Node-ra nem mutat él, és a stop Node-ból nem indul ki él. Ezáltal a gráf irányított kör mentessé válik.

Az algoritmus

Igazából nagyon sokat próbálgattuk, mire összeállt a jónak tűnő megoldás. A felépített gráfon egy teljes mélységi keresést (DFS) hajtunk végre úgy, hogy közben próbáljuk leszűkíteni a bejárandó utak számát. Az algoritmus nyugodtan lehet rekurzív, mert worst case 10000 szintig kell lemenni, és az még elfér a stack-en.

A “magic” nevű rekurzív függvénynek 3 bemenete van:

Node* from: itt van épp Pisti
int remaining: Pisti maradék rendelkezésre álló ideje
int currValue: az eddig bringázással eltöltött percek száma

Azért, hogy ne használjunk sok stack-et, minden egyéb, az algoritmus által használt változó globális.

Az algoritmus működése:

Kezdetben a start Node-ból indulunk.
Ha épp a cél Node-ban járunk, megnézzük, hogy a mostani út értéke (currValue) jobb-e, mint az eddigi legjobb. Ha igen, akkor elmentjük az utat.
Ezután végigmegyünk az aktuális Node-ból induló éleken.
Ha ez az él komp, akkor megnézzük, hogy a kompra szállva van-e még esélyünk arra, hogy jobb eredményt érjünk el az eddigi legjobbnál. Ha van, akkor meghívjuk a “magic” függvényt frissített paraméterekkel. Ez a feltétel nagyon sokat gyorsít a kód működésén.
Ha az él kerékpárút, akkor megnézzük, van-e még rá elég idő. Csak akkor megyünk tovább, ha van.
Ha végeztünk az élek bejárásával, akkor visszatérünk.

A megoldás azért tud viszonylag hatékony lenni, mert amint találunk egy jó útvonalat, a lehetséges útvonalak száma drasztikusan lecsökken.

Kiírás

Amikor a teljes rekurzív algoritmus visszatér, kiírjuk a legjobb útvonalat.

Eleinte megoldottuk, hogy a program egy új szálat indítson induláskor, ami 9.8 másodperc elteltével szól a fő szálnak, hogy álljon le és írja ki az aktuálisan legjobb megoldást. Végül erre a trükkre nem volt szükség.

Forrás letöltése

Mazeshetek megoldása

Ez a feladat okozta a legtöbb kihívást. Először a dinamikus programozás módszerére gondoltunk, de ezt elvetettük, mert a városok nagy száma és az idők lehetséges értékei miatt láttuk, hogy a memórialimitbe nem férnénk bele. Így első próbálkozásnak a mohó stratégiával igyekeztünk megoldani a problémát, több rendezési szempontot is kipróbáltunk, de ez nem váltotta be a hozzáfűzött reményeket.

Visszetértünk tehát az eredeti gondolatunkhoz, a dinamikus programozáshoz, annak reményében, hogy ugyan nem fog tudni a legnagyobb tesztesetekre megoldást adni, de amikre lefut, azokra optimális megoldást ad.

Első lépésben eltároltuk, hogy Graphivárosba 0 idő alatt, 0 percet biciklizve tudunk eljutni, majd minden onnan kiinduló utat illetve kompot megvizsgáltunk, a célvárosba eltároltuk hogy mennyi utazási idővel, mennyit tudunk biciklin tölteni.

Ezt ismételve mentünk végig sorban minden városon. Mivel tudtuk, hogy a használt memória mennyisége lesz a legnagyobb akadály, ezért mindent megtettünk ennek csökkentése érdekében.

A dinamikus programozásban gyakran használt táblázat helyett map-ben tároltuk a teljes utazási idő, út információ párokat, hogy az olyan időpontok, melyeknél nem lenne fontos információ, ne foglalják feleslegesen a memóriát.

A városok bejárása közben arra is figyeltünk, hogy csak olyan utakat tároljunk, melyek értéke nem kisebb a rövidebb idő alatt elérhetőeknél. Ilyen útból ugyanis jobb megoldás biztosan nem születhet.

A legjobb út megtalálásához megnéztük az összes tárolt utat Graphivárosba, kiválasztottuk a legnagyobb értékűt és lépésenként visszafele megkerestük az odavezető utat.

Forrás letöltése

asdf megoldása

Először egy rekurzív megoldást implementáltunk, ami 250 kompnál már problémákba ütközött. Ezután készitettünk egy 10000 városból és 10000 komp útból álló inputot (véletlen értékekkel), és próbáltunk olyan algoritmust keresni, ami 1 ásodpercen belül lefut erre az inputra és lehetőleg minél jobb eredményt ad. Mindenképpen akartunk megoldást találni, ezért az első algoritmusunk egy mohó útkereső algoritmus volt. Ez gyorsan lefutott és meglepően jó eredményeket adott. A mohó algoritmusunknak 2 stratégiája volt:

1. az út elején kizárólag csak biciklizek, és csak akkor térek át kompra, amikor már máshogy nem lehet időben elérni a célállomást.

2. az elején minél többet kompozok, és ha már elegendő időt spóroltam a komppal, akkor már csak biciklizek a célállomásig.

Ezután még probálkoztunk egyéb stratégiákkal illetve a mohó algoritmus finomításával, de nem hoztak jobb eredményt, így a végső megoldásunk maradt az előbb emlitett mohó algoritmus.

Syntax Error Team megoldása

Egybevágoság

A feladat nem annyira nehéz, a következő lépéseket csinálja a kód:

Épületek beolvasása
Bounding box meghatározása a csúcsok koordinátánkénti minimumából és maximumából.
Referenciaépület origóba mozgatása (bounding box minimum kivonása minden csúcsból).
Ezeknek a téglatesteknek az izomorfsága szükséges feltétele a két épület izomorfságának, így itt már lehet is szórni.
43 forgatás lehetséges, ezeket a következő módon intézi

Bounding box forgatása, majd ellenőrzése egyezésre.
Épület forgatása. Ez jelentősen le tud egyszerűsödni, miután a tengelyek mentén történő n*90 fokos forgatások kígyókkal (gyakorlatilag csak előjeles permutációmátrixszal) való szorzássá válnak. Végighalad a csúcsokon és elvégzi a műveletet. A többi elem (élek, oldalak, lyukak) csak ezekre a csúcsokra hivatkoznak, azokkal nincs dolog.
Épület egymásra mozgatása (bounding box minimum kivonása minden csúcsból, ahol figyelni kell, mert forgatás szerint a min-max fel is cserélődhet).
Csúcsok, élek, oldalak (bennük a lyukak) összehasonlítása.

Izomorf épületek indexének kiírása

Forrás letöltése

Mazeshetek megoldása

Az egybevágóság feladatnál hamar eldöntöttük, hogy mivel tökéletes megoldást nagyon nehéz lenne elkészíteni, megpróbálkozunk egy olyannal, amely a tesztek nagy részében jó megoldást fog adni.

Minden beolvasott háznak kipróbáltuk a 24 lehetséges térbeli elforgatását. A csúcsok forgatását mátrixszorzásokkal valósítottuk meg. Az eltolás problémáját úgy oldottuk meg, hogy minden házat eltoltunk az első térnyolcadba (minden csúcs minden koordinátája nemnegatív) úgy, hogy a tengelyek által meghatározott mindhárom síkon legyen csúcs. Minden ház egyértelműen eltolható így.

A csúcsok egybevágóságához a házak csúcsait rendeztük. A rendezés először az x, y majd z koordináták alapján, végül a csúcsból kiinduló élek száma alapján történt. Az éppen vizsgált két ház csúcsain sorban végigmentünk és ezeket a tulajdonságaikat összehasonlítottuk.

Ha minden csúcsnak volt megfelelője, akkor vizsgáltuk az oldalakat és a rajtuk lévő lyukakat. Az oldalak rendezésére az őket meghatározó élek számát, a lyukak számát, a konkrét csúcsokat (az előbb leírt összehasonlítással) és lyukakat használtuk. Két lyuk összehasonlítására is az őket meghatározó csúcsok összehasonlítását használtuk.

Az élek összehasonlítására nem került sor, mindössze a csúcsokból kiinduló élek számára figyeltünk, emiatt ez a módszer nem tökéletes, előfordulhat, hogy két épületet egybevágónak talál annak ellenére hogy apró eltérés van köztük és a sok egyedi hasonlítás, rendezés miatt a futási ideje is elég nagy, de elég jó megoldásnak bizonyult.

Forrás letöltése

asdf megoldása

Felismertük, hogy egy testet 90 fokos elforgatásokkal 24 különböző helyzetbe tudjuk forgatni. Ezért a megoldásunk az volt, hogy elforgatjuk ezekbe a helyzetekbe az első házat és így hasonlítjuk a többi házhoz. Két ház összehasonlításánál először eltoltuk az első házat a két ház középpontjának különbség vektorával, ezáltal a csúcsok pontosan egybeestek egybevágó esetben. Majd sorbarendeztük a csúcsokat a koordinátájuk alapján, majd az éleket a már sorbarendezett csúcsok alapján, majd az éllistákat az élek alapján, végül az oldalakat az éllisták alapján. Ezután a két házat egybevágónak tekintettünk, ha minden listájuk megegyezett (csúcs koordinátákra visszavezetve). Ez a verzió nem kezelte a duplán megadott csúcsokat/éleket/oldalakat. Ennek részleges megoldására elkezdtük számlálni, hogy egy csúcsra, hány él hivatkozik és egy él mennyi éllistában szerepel. Ezt az információt felhasználtuk a rendezésnél és a listák összehasonlításánál. Akármit csináltunk nem tudtunk elmozdulni a 15-ös teszt eredményről, végül rájöttünk hogy az eredmény kiiratását rontottuk el.

Syntax Error Team megoldása