Tehtävä A: Suklaalevy
Kun suklaalevy on n\times m -kokoinen, suurimman mahdollisen neliön muotoisen palan sivun pituus on k=\min(n,m). Palan syömisen jälkeen suuremmasta mitasta vähennetään k ja syöminen jatkuu samalla tavalla, kunnes koko suklaalevy on syöty loppuun.
Tehtävä B: Numerolukko
Operaatioiden järjestyksellä ei ole väliä, koska lopputulokseen vaikuttaa vain se, kuinka paljon kutakin kiekkoa on käännetty yhteensä. Optimaalinen ratkaisu on mahdollista rakentaa niin, että ensin suoritetaan kaikki B-operaatiot ja sen jälkeen kaikki A-operaatiot.
Tehtävä ratkeaa käymällä läpi kaikki 10 tapaa valita B-operaatioiden määrä ja laskemalla joka kerta myös vaadittavien A-operaatioiden määrän. Yksittäistä kiekkoa tarkasteltaessa kahden numeron a ja b pienin etäisyys on \min(|a-b|, 10-|a-b|), koska kiekkoa voi pyörittää molempiin suuntiin. Tämä ratkaisu voidaan toteuttaa niin, että aikavaativuus on O(n).
Tehtävä C: Osajonot
Helppo ratkaisu tehtävään on käydä läpi kaikki merkkijonon osajonot ja tarkastaa jokaisesta osajonosta, muodostuuko se toistamalla kahta merkkijonoja. Ratkaisun aikavaativuus on O(n^3), koska merkkijonossa on O(n^2) osajonoa ja jokaisen osajonon kohdalla tarkastus vie aikaa O(n). Tätä ratkaisua voi tehostaa käyttämällä merkkijonohajautusta, jolloin voidaan tarkastaa ajassa O(1), ovatko merkkijonon kaksi osajonoa samat. Tehostetun ratkaisun aikavaativuus on O(n^2).
Toinen lähestymistapa tehtävään on käydä läpi yksi kerrallaan jokainen mahdollinen toistuvan osajonon pituus. Osajonojen määrä voidaan laskea tietylle pituudelle k ajassa O(n) käymällä merkkijono läpi vasemmalta oikealle ja vertaamalla merkkejä, jotka ovat k:n päässä toisistaan. Tämä on toinen tapa saada aikaan ratkaisu, jonka aikavaativuus on O(n^2).
Äskeistä ratkaisua voi tehostaa seuraavan havainnon avulla: pituuden k käsittelyssä merkkejä voidaan vertailla 2^b merkin paloissa, missä 2^b on suurin pituus, joka on enintään k/2. Jos merkkijonossa on toistuva k merkin pituinen osajono, niin sen sisälle osuu aina jokin 2^b merkin pituinen pala. Tämän ansiosta merkkijonon läpikäynti voidaan toteuttaa tehokkaammin esimerkiksi merkkijonohajautuksen ja binäärihaun avulla. Ratkaisun aikavaativuus voi olla O(n \log n) tai O(n \log^2 n) riippuen toteutuksesta.
Tehtävä D: Esineet
Esineen muoto voidaan esittää listana, joka sisältää esineeseen kuuluvien ruutujen koordinaatit. Tässä on hyödyllistä siirtää koordinaatteja niin, että pienin x- ja y-koordinaatti on 0, sekä lisäksi järjestää koordinaatit listalla. Tällöin kaksi esinettä ovat samanmuotoisia ja samassa asennossa tarkalleen silloin, kun niiden listaesitys on sama.
Koska tehtävässä on sallittua peilata ja kääntää esineitä, tämän voi ottaa huomioon valitsemalla esitystavaksi kaikista mahdollisista asennoista (yhteensä enintään 8 asentoa) se, jossa lista on leksikografisesti pienin mahdollinen. Tällöin kaksi esinettä ovat samanmuotoisia asennosta riippumatta, kun niiden listaesitys on sama.
Yllä olevan esitystavan avulla saadaan aikaan tehokas ratkaisu muodostamalla kaikkien esineiden listaesitykset esimerkiksi syvyyshaun avulla ja tutkimalla, mikä esine puuttuu jälkimmäisestä ruudukosta.
Tehtävä E: Korttitemppu
Operaatio A pyörittää korttipakan alkua a kortin verran, mutta kaikki pyöritykset eivät onnistu yhdellä operaatiolla. Kahdella A-operaatiolla mikä tahansa pyöritys x kortin verran on kuitenkin mahdollinen. Jos x > \lceil 2n/3 \rceil, tehdään operaatiot a=\lceil x/2 \rceil ja a=\lfloor x/2 \rfloor. Jos taas x < \lfloor n/3 \rfloor, niin tehdään operaatiot a=\lceil (x+n)/2 \rceil ja a=\lfloor (x+n)/2 \rfloor.
B-operaatioiden avulla on mahdollista siirtää yksittäistä korttia vaikuttamatta muiden korttien järjestykseen. Esimerkiksi jos n=12, operaatiot B a=8 b=4 ja B a=7 b=3 siirtävät pakan alimman kortin viidenneksi ylimmäksi. Tässäkään tapauksessa kaikki siirrot eivät ole mahdollisia, mutta pyörityksiä ja yhden kortin siirtoja yhdistelemällä kortin voi siirtää mihin tahansa kohtaan O(n) operaatiolla.
Korttipakka saadaan järjestettyä siirtämällä kortit numerojärjestyksessä paikoilleen: ensin kortti 2 siirretään kortin 1 alle, sitten kortti 3 kortin 2 alle, ja niin edelleen. Lopuksi kortti 1 pyöritetään pakan päälle A-operaatioilla. Ratkaisu tekee yhteensä O(n^2) operaatiota.
Kortin siirto haluttuun kohtaan onnistuu myös vakiomäärällä operaatiota. Yksi tapa toteuttaa tämä on esilaskea, mitkä siirrot pohjalta keskelle ja toisin päin ovat mahdollisia kahdella B-operaatiolla. Näiden perusteella voidaan määrittää optimaalinen operaatioiden sarja mille tahansa siirrolle dynaamisen ohjelmoinnin avulla. Operaatioiden kokonaismäärä on tällöin O(n).
Tehtävä F: Merkkijono
Kun k=2, ratkaisu on olemassa vain, kun n \le 3. Sen sijaan kun k \ge 3, jolloin käytössä on merkit a, b ja c, ratkaisu on olemassa mille tahansa pituudelle n.
Ehdot täyttävää merkkijonoa kutsutaan neliövapaaksi. Merkkijonon muodostamiseen on useita tapoja. Eräs tapa perustuu uudelleenkirjoitussääntöihin, joissa jokainen merkki korvataan jollakin toisella merkkijonolla. Esimerkiksi säännöstö a \mapsto abacabc, b \mapsto acbabc, c \mapsto bacbc tuottaa neliövapaan merkkijonon, mikäli alkuperäinen merkkijono oli myös neliövapaa. Samalla merkkijono pitenee, eli uudelleenkirjoitusta toistamalla saadaan aikaan mielivaltaisen pitkä merkkijono.
Yksinkertaisempi säännöstö a \mapsto abc, b \mapsto ac, c \mapsto b ei säilytä neliövapautta kaikissa tilanteissa. Esimerkiksi aba \mapsto ab\bm{caca}bc. Kuitenkin toistamalla uudelleenkirjoitusta alkutilanteesta a syntyy sopiva merkkijono abcacbabcbac\ldots. Monet kilpailun osallistujat löysivätkin tämän ratkaisun.
Toinen yleisesti tunnettu tapa tuottaa neliövapaita merkkijonoja perustuu Thue–Morsen jonoon 01101001\ldots ja sen peräkkäisten merkkien vertailuun. Osoittautuu, että tämä menetelmä tuottaa saman merkkijonon, kuin yllä mainittu säännöstö a \mapsto abc, b \mapsto ac, c \mapsto b.
