Selejtező megoldások 2020

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

Numbers

Az A, B, C számokról semmit sem használtunk ki azon kívül, hogy a szorzatuk N.

Az első megfigyelésünk az volt, hogy az Erdős-Ginzburg-Ziv-tétel miatt mindig található majd N db szám megfelelő módon.

Minden számnak nyilván csak az N-es maradéka érdekel minket, a végén a kiírás miatt egy kicsit ügyeskedni kell azzal, hogy el is mentsük magukat az eredeti számokat, de ez nem olyan nehéz.

Ha választunk N-1 számot, akkor az N. szám (maradéka) már egyértelműen adódik. Tehát ha a maradék N+1 szám között van ilyen szám, akkor készen vagyunk.

Ha feltesszük, hogy ebben a maradék N+1 számban minden szám egyenletes eloszlással szerepel, akkor 1-((N-1)/N)^(N+1) eséllyel találunk megfelelő N. számot.

Ez az esély kellően nagy. Így aztán ha sokszor egymás után választunk N-1 számot és próbálunk keresni egy N.-et, akkor néhány próbálkozás után már szinte biztosan találunk megoldást.

Ugyanakkor itt most feltételeztük azt, hogy a maradék N+1 számban majd egyenletes eloszlással szerepelnek a számok.

Ez nyilván nincs mindig így, vannak elég speciális esetek.

A speciális esetekre azt találtuk ki, hogy egy kör mentén felírjuk az összes számot növekvő sorrendben (továbbra is csak az N-es maradékokat nézzük...) és minden szomszédos (N-1) darab számot megvizsgálunk. Azaz megnézzük, hogy van-e hozzájuk (nem feltétlenül szomszédos) megfelelő N. szám.

Ez nem oldja meg biztosan a feladatot, van rá ellenpélda (pl N=6 és 0, 0, 0, 0, 0, 2, 3, 3, 3, 3, 3, 5), viszont nagyon nehéz ellenpéldákat találni rá és a speciális eseteket nagyon jól megoldja. (Igen, itt ezt nem tudjuk igazán jól megindokolni, de a gyakorlatban jól működik.)

Ezt implementálni is viszonylag egyszerű (O(N) időben), hiszen lényegében csak a (majdnem) félkör elejét és végét kell egyszerre léptetgetni és a köztes részben lévő számok a kiválasztottak. (Azt is könnyű O(1) időben megmondani, hogy egy konkrét S számból van-e még a többi között.)

Utólag kiderült, hogy csupán ez a rendezéses ötlet is már elég volt a 100 ponthoz, de eredetileg az volt a tervünk, hogy ha nem találunk megoldást ezzel a rendezéssel, akkor utána a kezdetben leírt módon próbálkozunk és addig választunk random N-1 db számot, amíg nem találunk hozzá egy megfelelő N.-et (bármilyen kellően random esetben ez is nagyon jól működik, hiszen ilyenkor a maradék N+1 szám között az eloszlás jól közelíthető a teljesen egyenletessel).

Összességében szerintünk a nehézség az a speciális esetek megoldása volt, mivel random esetekben nagyon könnyű megoldást találni szinte bármilyen módon.

A konklúzió pedig az, hogy az Erdős-Ginzburg-Ziv-tételt csak bizonyítani nehéz, a gyakorlatban általában elég könnyű megoldást találni és általában sok megoldás van.

Egy megjegyzés még, hogy elvileg van O(N^2) idejű (remélem nem mondok hülyeséget) megoldás a feladatra, ami biztosan megoldja a feladatot (minden esetben, determinisztikusan).

Ez a megoldás lényegében az Erdős-Ginzburg-Ziv-tétel bizonyításán alapul, de elég komplikált megérteni, illetve implementálni.

Avocado megoldása

Crypto

Ez a feladat okozta a legkevesebb nehézséget, egyszerű algoritmust használtunk a megoldásra. Az alapja egy rekurzív kimerítő keresés volt, ami felváltva próbálkozott XOR és AND műveletekkel, amíg el nem értük a végeredményt. Azért lehet mindig felváltva használni a műveleteket, mert több egymás utáni XOR illetve több egymás utáni AND is összevonható egyetlen XOR illetve AND műveletre. Ha így esetleg a szükségesnél kevesebb lépésben találtuk meg a megoldást, akkor a megfelelő számú ADD 0-val ki lehet egészíteni. Még egy egyszerűsítést használtunk: a duplikált karakterek eldobtuk, mivel egy karakterrel ugyanazokat a műveleteket elvégezve mindig ugyanazt az eredményt kapjuk. Ilyen formában ez a megoldás 4 tesztet oldott meg a 10-ből, a többire TIMEOUT-olt.

A keresést úgy tudtuk felgyorsítani, hogy összevontuk a XOR és ADD műveletet, és minden lépésben sorba rendeztük őket egy heurisztika alapján. Ez azt jelenti, hogy mindig vettük az összes lehetséges XOR+ADD lépést, ami 256x256 lehet, és ezeket a heurisztika szerinti sorrendben próbálta felhasználni a keresés. A heurisztikánk pedig a következő volt: az adott XOR és ADD művelet végrehajtása után a kapott számoknak (karaktereknek) mekkora lesz a végeredménytől vett eltérések szórása. Ez nulla lesz, ha pont a megoldásba visz minket, de például akkor is, ha mindenki ugyanolyan messze lesz a megoldástól - ekkor egyetlen ADD már megoldja a problémát. A többi esetben nem teljesen értjük, hogy miért visz közelebb a megoldáshoz, de hát ezért heurisztika, és ezzel mind a 10 teszteset lefutott időben, úgyhogy ez lett a végleges megoldásunk.

Forrás letöltése
Tom és Gerry megoldása

Road

Ez a feladat volt a legidőigényesebb, illetve ez okozta a legtöbb nehézséget, bár nem mondanám különösen bonyoltultnak. Maga az algoritmus egyszerű, de sok kódot kellett írni hozzá, mire egyáltalán kis példákra tudott valamilyen megoldást adni. Miután megvolt a kis példákra helyesen működő változat, a végső megoldáshoz már csak minimális változtatások kellettek.

A következőt csináltuk: felvettünk minden lehetséges módot arra, ahogy egy ház körül kanyarodhat az út. Ez nagyon sok féle lehet, összesen 197 lehetőség van (ha a forgatásokat és tükrözéseket nem vesszük figyelembe, akkor 29). Például egy 2-es számú ház mellett elmehet az út úgy is, hogy egy útszakasz érinti két szomszédos mezőn, vagy két külön útszakasz érinti egy-egy szomszédos mezőn - ezek lehetnek egymással szemben, vagy egy üres mezővel a kettő között. Ez máris három különböző lehetőség, plusz a forgatások. (Ezekről a lehetséges elrendeződésekről készítettünk egy paint-es ábrát, ezt mellékelem, szerintem jól néz ki, és könnyebb vele megérteni.)

A megoldást backtrack-kel keressük, ami két szinten fut. Az első szinten a fent leírt elrendeződéseket (patcheknek hívtuk őket) próbálja lerakni a házakra, és ha sikerült neki, akkor a második szinten az utakat próbálja összekötni. Mindkét szinten fontos volt, hogy milyen sorrendben próbálkozik a keresés. A patch-eknél először a kisebb számú házakra próbál patch-et rakni, két egyforma számú ház közül pedig először arra, amelyiknek a max 2 sugarú környezetében több másik ház van. Ez azért jó, mert a kis számú házak sok környező mezőn letiltják az útépítést, és ha körülöttük vannak más házak, akkor nekik már sokkal kevesebb lehetőségük lesz a patch kiválasztására. Egy másik javítás pedig, hogy a patch-ek sorrendjét a futás elején randomizáltuk, így egymás után nem túl hasonlók lerakásával fog a keresés próbálkozni. Az útépítésnél pedig mindig olyan útvégződésből indultunk, ahol a legkevesebb lehetséges folytatás van, ezáltal a keresés gyorsan megtalálja a zsákutcákat.

Ez így meg tudta oldani a feladatot mind a 10 tesztesetre. A sorba rendezés és randomizált sorrend nélkül 3-4 tesztesetet tudott megoldani, csak a randomizálás nélkül 6-7-et. A legnagyobb nehézséget az okozta, hogy az utak lehelyezésénél helyesen kezeljük, hogy melyik mezők között marad szabad az átjárás. Elsőre nem tűnik vészesnek, de ahhoz, hogy a fenti algoritmusban hatékonyan lehessen a visszalépést kezelni, jól végig kellett gondolni, és sokat debuggolni.

Forrás letöltése
Tom és Gerry megoldása

Numbers

Fontos észrevétel, hogy a megadott számoknak csak a mod N szerinti értéke számít, a feladat szempontjából az azonos maradékosztályba esők ugyanúgy viselkednek. Először dinamikus programozással próbálkoztunk, ami megadja, hogy egy m mod N összeget ki lehet hozni egy s tagú összegből. Ha m = 0, és s = N, akkor készen vagyunk. Kezdetben üres a tömbbünk, és a megadott számokon haladunk sorban és nézzük, hogy a meglévőkhöz az adott számot hozzáadva elérhető-e egy még nem létező m, s páros, Ha igen, akkor ezt felvesszük a tömbbe. Ahhoz, hogy vissza lehessen követni, melyik számok szerepelnek az összegben, az s mellett eltároljuk azt is, hogy melyik számnál került be a tömbbe. Ez a megoldás 3 tesztet oldott meg a 10-ből.

Ezután más irányból közelítettük meg a problémát, és készítettünk egy random próbálgatós algoritmust. Kiválaszt n számot, és megnézi, ezek összege 0-e (mod N), vagy egyetlen szám cseréjével elérhető-e a 0 összeg. Ha igen, készen vagyunk, ha pedig nem, akkor valahány számot kicserélünk olyanra, ami korábban nem szerepelt az összegben. Ez az algoritmus meglepő módon 8 tesztet megoldott a 10-ből. Egy külön esettel lekezeltük még, ha bármilyen maradékosztályból van N darab, ez plusz egy esetet megoldott, amivel együtt már 9 jó a 10-ből.

Az utolsó teszthez azonban vissza kellett térni a dinamikus programozáshoz. A random próbálgatás akkor hatékony, ha viszonylag egyenletes eloszlás szerint szerepelnek a különböző maradékosztályok. Mivel 2*N szám van, amik N különböző értéket vesznek fel, átlagosan mindegyikből 2 lesz, tehát általános esetben jól teljesít a random próbálgatás. A dinamikus programozás a fent leírt formájában rosszul skálázódik nagy N-re, azonban azokban az esetekben, amikor kevés különböző szám szerepel a bemenetben, sokkal hatékonyabbá lehet tenni - tehát pont akkor, amikor a random próbálgatás rosszul teljesít. Ha két egymást követő szám megegyezik, akkor a második szám már csak azokon az összegeket tud változtatni, amiket az előző újonnan hozott be. Nem kell tehát ilyenkor a teljes tömböt bejárni, és mindent kipróbálni, elég az újonnan felvetteket tárolni és azokon végigmenni. Ezzel nagyságrendeket nyerhetünk, persze csak ha ilyen eloszlású a bemenet, és garantáljuk, hogy az azonos számok egymás után következzenek. Az előbbit a beolvasás során ellenőrizzük, és ha elég kevés különböző szám van csak, akkor sorba rendezzük őket és a dinamikus programozást futtatjuk, különben pedig a random próbálgatást. Ez már mind a 10 esetet megoldotta. (A javított dinamikus programozás önmagában 4-et tudna megoldani.)

Érdekes feladat volt, egy kicsit sajnáljuk, így egy ilyen favágó megoldás lett az, ami mindent meg tudott oldani.

Forrás letöltése
Tom és Gerry megoldása