A - Ruudukko
Ruudukko kannattaa muodostaa rivi kerrallaan ylhäältä alas.
Kullekin ruudulle voidaan muodostaa joukko luvuista, jotka voisivat olla pienimpiä kelvollisia lukuja ruutuun. Suurin luku, joka voi esiintyä ratkaisussa tehtävän rajoilla on , mutta esimerkiksi arvio toimii hyvin. Tämän jälkeen poistetaan joukosta kaikki luvut, jotka esiintyvät jo rivillä tai sarakkeella ja asetetaan ruutuun pienin luku, joka joukossa on jäljellä.
Tehokkaampi, konstruktiivinen ratkaisu on asettaa kuhunkin ruutuun luku , missä kuvaa lukujen xor-summaa.
B - Merkkijonot
Osatehtävä 2
Toisessa osatehtävässä , joten voidaan käydä kaikki merkkijonoparit läpi ja laskea yksitellen, moniko pareista on harmonisia. Algoritmin aikavaativuus on .
Osatehtävä 3
Kolmannessa osatehtävässä , joten kaikkia merkkijonopareja ei voi enää käydä läpi.
Pyritään jakamaan merkkijonot ryhmiin siten, että yhden ryhmän sisällä kaikki merkkijonot ovat keskenään harmonisia ja ryhmien välillä mitkään merkkijonot eivät ole harmonisia.
Muutetaan merkkijonot kanoniseen muotoon korvaamalla kaikki ensimmäisenä esiintyvän kirjaimen esiintymät kirjaimella A, toisena esiintyvän kirjaimen esiintymät kirjaimella B ja niin edelleen. Tällöin kaikki keskenään harmoniset merkkijonot ovat samoja ja ne voidaan asettaa samaan ryhmään.
Kustakin ryhmästä voidaan valita kaksi merkkijonoa tavalla, missä on ryhmän koko.
Algoritmin aikavaativuus on .
Vastaus ja välitulokset eivät mahdu välttämättä 32-bittiseen kokonaislukuun, vaan laskenta pitää tehdä vähintään 64-bittisillä kokonaisluvuilla.
C - Lukuvälit
Osatehtävä 1
Ensimmäisessä osatehtävässä voidaan esimerkiksi käydä jokaisessa kyselyssä kaikki välin luvut läpi, muuttaa ne merkkijonoiksi ja tutkia jokaisesta merkkijonosta, onko siinä muita merkkejä kuin tai . Algoritmin aikavaativuus on .
Osatehtävä 2
Toisessa osatehtävässä , joten jokaisessa kyselyssä ei voida enää käydä kaikkia välin lukuja läpi.
Välin voi kuitenkin käydä kerran läpi ja esilaskea jokaiselle , moniko kokonaisluvuista on halutunlainen. Jos arvot on tallennettu taulukkoon , saadaan vastaus mielivaltaiseen kyselyyn vakioajassa laskemalla . Algoritmin aikavaativuus on .
Osatehtävä 3
Kolmannessa osatehtävässä , joten välin kaikkia lukuja ei ole enää mahdollista käydä läpi.
Välin luvuissa on enintään 18 numeroa (poikkeuksena 19-numeroinen ), joten mahdollisia lukuja, joissa ei ole muita numeroita kuin 0 ja 1 on saman verran kuin -bittisiä binäärilukuja, eli kappaletta. Kun poikkeus huomioidaan, mahdollisia lukuja on kappaletta.
Voidaan luoda aluksi lista kaikista kelvollisista luvuista välillä ja binäärihakea jokaiselle kyselylle listasta pienimmän ja suurimman kyselyn välillä olevan luvun indeksit. Lukujen määrä välillä on tai , jos saadut indeksit eivät ole välillä.
Algoritmin aikavaativuus on .
D - Mastot
Osatehtävä 1
Ensimmäisessä osatehtävässä , joten osajoukkojen läpikäynti on mahdollista. Yritetään korjata kaikki mahdolliset mastojen osajoukot ja valitaan edullisin osajoukko, jolla signaali saavuttaa vastaanottimen. Osajoukkoja on kappaletta ja kunkin osajoukon kelvollisuus voidaan tarkistaa ajassa , joten algoritmin aikavaativuus on .
Osatehtävä 2
Toisessa osatehtävässä , joten osajoukkojen läpikäynti ei ole enää mahdollista. Ratkaistaan tehtävä dynaamisella ohjelmoinnilla.
Olkoon pienin hinta, jolla signaali saadaan välitettyä etäisyydelle . Koko tehtävän ratkaisu on . Alussa ja .
Signaalia ei koskaan kannata lähettää taaksepäin. Käydään mastot läpi järjestyksessä . Kun masto tulee käsittelyyn, sen optimiratkaisu on jo tiedossa. Päivitetään kaikkien maston kantamalla olevien mastojen ratkaisuja: kaikille .
Koska kunkin maston kantama voi kattaa kaikki loput mastot, yksi dp-tilasiirtymä vie aikaa ja algoritmin aikavaativuus on .
Osatehtävä 3
Tehtävään on useita tehokkaita ratkaisuja, tässä on kuvattu yksi vaihtoehto.
Kolmannessa osatehtävässä , joten toisen osatehtävän -algoritmi on liian hidas. Yritetään nopeuttaa yksittäistä dp-tilasiirtymää.
Tilasiirtymässä kaikille halutaan minimoida dp-taulukon välin kukin luku valitsemalla joko alkion nykyinen arvo tai , kumpi onkaan pienempi.
Tällainen päivitys on mahdollista tehdä ajassa laiskalla segmenttipuulla (Competitive Programmer's Handbook - Chapter 28). Ratkaistaan tehtävä muuten samoin kuin osatehtävässä 2, mutta tallennetaan dp-taulukko segmenttipuuhun ja tehdään kukin tilasiirtymä logaritmisessa ajassa. Algoritmin aikavaativuus on tällöin .
E - Ketjupeli
Ketjupeli tunnetaan nimellä Morpion, tarkemmin sen 5T-versio. Pelin optimaalista ratkaisua ei vielä tunneta, tämänhetkinen paras ratkaisu on 178 siirron pituinen.