A - Ruudukko

Ruudukko kannattaa muodostaa rivi kerrallaan ylhäältä alas.

Kullekin ruudulle (i, j) voidaan muodostaa joukko luvuista, jotka voisivat olla pienimpiä kelvollisia lukuja ruutuun. Suurin luku, joka voi esiintyä ratkaisussa tehtävän rajoilla on 128, mutta esimerkiksi arvio 1 \dots 200 toimii hyvin. Tämän jälkeen poistetaan joukosta kaikki luvut, jotka esiintyvät jo rivillä i tai sarakkeella j ja asetetaan ruutuun (i, j) pienin luku, joka joukossa on jäljellä.

Tehokkaampi, konstruktiivinen ratkaisu on asettaa kuhunkin ruutuun (i, j) luku (i \oplus j) + 1, missä \oplus kuvaa lukujen xor-summaa.

B - Merkkijonot

Osatehtävä 2

Toisessa osatehtävässä n \leq 5000, joten voidaan käydä kaikki merkkijonoparit läpi ja laskea yksitellen, moniko pareista on harmonisia. Algoritmin aikavaativuus on O(n^2).

Osatehtävä 3

Kolmannessa osatehtävässä n \leq 10^5, 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 \frac{x \cdot (x-1)}{2} tavalla, missä x on ryhmän koko.

Algoritmin aikavaativuus on O(n).

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 0 tai 1. Algoritmin aikavaativuus on O(n \cdot b_{max}).

Osatehtävä 2

Toisessa osatehtävässä n, b_{max} \leq 10^5, joten jokaisessa kyselyssä ei voida enää käydä kaikkia välin lukuja läpi.

Välin [0, b_{max}] voi kuitenkin käydä kerran läpi ja esilaskea jokaiselle i, moniko kokonaisluvuista \leq i on halutunlainen. Jos arvot on tallennettu taulukkoon count(i), saadaan vastaus mielivaltaiseen kyselyyn vakioajassa laskemalla count(b) - count(a-1). Algoritmin aikavaativuus on O(n + b_{max}).

Osatehtävä 3

Kolmannessa osatehtävässä b_{max} \leq 10^{18}, joten välin kaikkia lukuja ei ole enää mahdollista käydä läpi.

Välin luvuissa on enintään 18 numeroa (poikkeuksena 19-numeroinen 10^{18}), joten mahdollisia lukuja, joissa ei ole muita numeroita kuin 0 ja 1 on saman verran kuin 18-bittisiä binäärilukuja, eli 2^{18} kappaletta. Kun poikkeus 10^{18} huomioidaan, mahdollisia lukuja on 2^{18} + 1 = 262145 kappaletta.

Voidaan luoda aluksi lista kaikista kelvollisista luvuista välillä 0 \dots 10^{18} ja binäärihakea jokaiselle kyselylle listasta pienimmän ja suurimman kyselyn välillä olevan luvun indeksit. Lukujen määrä välillä on i_{max} - i_{min} + 1 tai 0, jos saadut indeksit eivät ole välillä.

Algoritmin aikavaativuus on O(n \log b_{max}).

D - Mastot

Osatehtävä 1

Ensimmäisessä osatehtävässä 2 \leq n \leq 20, joten osajoukkojen läpikäynti on mahdollista. Yritetään korjata kaikki mahdolliset mastojen osajoukot ja valitaan edullisin osajoukko, jolla signaali saavuttaa vastaanottimen. Osajoukkoja on 2^n kappaletta ja kunkin osajoukon kelvollisuus voidaan tarkistaa ajassa O(n), joten algoritmin aikavaativuus on O(2^n \cdot n).

Osatehtävä 2

Toisessa osatehtävässä 2 \leq n \leq 5000, joten osajoukkojen läpikäynti ei ole enää mahdollista. Ratkaistaan tehtävä dynaamisella ohjelmoinnilla.

Olkoon dp(i) pienin hinta, jolla signaali saadaan välitettyä etäisyydelle i. Koko tehtävän ratkaisu on dp(n). Alussa dp(0) = 0 ja dp(1 \dots n) = \infty.

Signaalia ei koskaan kannata lähettää taaksepäin. Käydään mastot läpi järjestyksessä 0 \dots n-1. Kun masto i tulee käsittelyyn, sen optimiratkaisu on jo tiedossa. Päivitetään kaikkien maston i kantamalla olevien mastojen ratkaisuja: dp(i+j) = min(dp(i+j), dp(i) +c_i) kaikille j \leq d_i.

Koska kunkin maston kantama voi kattaa kaikki loput mastot, yksi dp-tilasiirtymä vie aikaa O(n) ja algoritmin aikavaativuus on O(n^2).

Osatehtävä 3

Tehtävään on useita tehokkaita ratkaisuja, tässä on kuvattu yksi vaihtoehto.

Kolmannessa osatehtävässä 2 \leq n \leq 2 \cdot 10^5, joten toisen osatehtävän O(n^2)-algoritmi on liian hidas. Yritetään nopeuttaa yksittäistä dp-tilasiirtymää.

Tilasiirtymässä dp(i+j) = min(dp(i+j), dp(i) +c_i) kaikille j \leq d_i halutaan minimoida dp-taulukon välin [i, i+d_i] kukin luku valitsemalla joko alkion nykyinen arvo tai dp(i) + c_i, kumpi onkaan pienempi.

Tällainen päivitys on mahdollista tehdä ajassa O(\log n) 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 O(n \log n).

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.