Tämä kisaraportti viittaa ACM:n ICPC 2010 -ohjelmointikilpailun loppukilpailuun Kiinassa 5.2.2010. Kisatehtävät, joihin raportissa viitataan, löytyvät ICPC-kilpasivustolta.

Kisaraportin kirjoitti Mika Laitinen apunaan joukkueen muut jäsenet Mikko Sysikaski ja Aleksi Hartikainen.

Kisan alussa aloimme tavalliseen tyyliimme kukin lukemaan eri tehtäviä. Tehtävät osoittautuivat ehkä hieman odotuksia hankalammiksi, mutta noin vartin jälkeen joukkueemme alkoi keskustella tehtävästä C, joka vaikutti olevan ratkaistavissa tunnetuilla keinoilla.

Tehtävässä syötteenä oli ruudukko, johon oli asetettu yhden ruudun paksuisia vaakasuuntaisia esteitä. Ruudukossa liikkui robotti, joka pystyi kulkemaan vain ylös tai oikealle. Tehtävänä oli laskea sellaisten ruutujen määrä, joista robotti ei pääse oikeassa yläkulmassa sijaitsevaan exit-ruutuun.

Tehtävä vaikutti ensin todella helpolta: muodostetaan ruudukon kokoinen kaksiuloitteinen taulukko, ja ratkaistaan yksinkertaisella dynaamisella ohjelmoinnilla: Ruudusta pääsee pois jos ruutu ei ole seinä ja:

1. Se on exit-ruutu tai
2. Sen yläpuoleisesta ruudusta pääsee pois tai
3. Sen oikeanpuoleisesta ruudusta pääsee pois

Ongelmaksi muodostuikin ruudukon koko: ruudukon korkeus ja leveys olivat korkeintaan 10⁶. Aikaa ja muistia kuluisi siis aivan liian paljon.

Tehtävässä oli kuitenkin taattu, että seiniä on yhteensä maksimissaan tuhat. Tällöin merkityksellisten koordinaattipisteiden määrä laskee hyvin paljon, joten tehtävä ratkeaa koordinaattien pakkauksella:

1. Tehdään järjestetty taulukko kaikista kiinnostavista x-koordinaateista: näitä ovat 0,exit-ruudun x ja kaikkien seinien reunat x1 ja x2+1.
2. Tehdään vastaava taulukko y-koordinaateille
3. Muodostetaan kaksiulotteinen taulukko, jonka koot ovat koordinaattitaulukkojen koot.
4. Merkitään annetut seinät uuteen taulukkoon. Koska seiniä on korkeintaan 1000, on pakatun taulukon koko korkeintaan 2002x2002.

Nyt jokainen ruutu vastaa tiettyä aluetta alkuperäisessä ruudukossa, ja vastaus saadaan laskemalla jumitusruutujen pinta-alat yhteen.

Vaikka toimiva ratkaisuajatus olikin kohtuullisen vikkelästi selvillä, oli ratkaisun rasittavin vaihe vielä edessä. Koordinaattien pakkaus on suhteellisen rasittava ja bugialtis ohjelmoitava. Kun itse koordinaattien pakkaus oli saatu toteutettua ja ohjelma oli muuten valmis, palautimme ohjelman muutamaan otteeseen korjattuamme joitain pikkubugeja. Kuitenkaan ohjelmaa ei vielä tässä muodossa hyväksytty, vaikkemme onnistuneet löytämään ohjelmasta vikaa. Koska ongelma vaikutti kohtuullisen ihmeelliseltä, päätimme tulostaa koodin bugietsintää varten ja päästää Mikon ohjelmoimaan tehtävää G.

G-tehtävän ohjelmointi sujui vauhdikkaasti, ja hieman sen jälkeen kun Mikko oli saanut onnistuneesti palautettua G-tehtävän koodin, löysimme myös C-tehtävässä luuranneen virheen: tarkastukset tehtiin väärässä järjestyksessä ja ohjelma luuli, että exit-ruudusta pääsee pois vaikka siinä on seinää. Korjattuamme bugin ohjelma meni mukavasti läpi, ja kovin nihkeän alun jälkeen joukkueellamme oli noin kahden tunnin jälkeen kohtalaiset kaksi pistettä.

Seuraavassa Mikon selitys G-tehtävän ratkaisusta:

Tehtävässä annettiin joukko tason pisteitä ("saaria"), ja tehtävänä oli etsiä lyhin kierros, joka kulkee pistejoukon vasemmasta laidasta oikeaan laitaan ja takaisin, ja käy matkalla jokaisen annetun pisteen läpi tasan kerran. Kun ollaan menossa vasemmalta oikealle, pisteet on käytävä läpi kasvavan x-koordinaatin mukaisessa järjestyksessä ja vastaavasti oikealta vasemmalle kuljettaessa laskevan x-koordinaatin mukaisessa. Lisäksi pisteistä kaksi on erityisasemassa, ja vaaditaan, että näistä pisteistä jomman kumman läpi on käytävä oikealle kuljettaessa ja toisen pisteen läpi käytävä vasemmalle kuljettaessa.

Rajoite, että reitin pitää käydä kahdella saarista eri matkoilla ei tuntunut merkittävästi vaikuttavan tehtävän luonteeseen, joten päätin aluksi jättää sen huomioimatta ja lähdin miettimään ratkaisua yksinkertaistettuun ongelmaan, jossa tuota rajoitetta ei olisi.

Rutiininomaisesti lähdin ensimmäisenä katsomaan, sopisiko dynaaminen ohjelmointi tehtävään: Tämän tehtävän kohdalla osaongelmiksi voidaan valita lyhmmän reitin loppuosan löytäminen, kun ollaan kuljettu jokin alkuosa kierroksesta. Osaongelmia tulisi kuitenkin aivan liikaa (ainakin 2ⁿ), sillä tilaan täytyy kuulua tieto siitä, missä osajoukossa saaria on jo käyty.

Tehtävä toi lähes heti mieleen tämän vuoden Datatähden loppukilpailutehtävän(*), jossa suhteellisen identtisellä tavalla kuljettiin samassa verkossa kahteen suuntaan niin, että polut eivät osuneet samoihin solmuihin. Kyseisen tehtävän ratkaisussa oli oleellista huomata, että kahden vastakkaisiin suuntiin kulkevan polun sijaan on helpompi muodostaa kaksi rinnakkain samaan suuntaan kulkevaa polkua, jolloin on helpompi huolehtia, että kussakin pisteistä käydään vain kerran.

Samansuuntaisten polkujen idea tuntui järkevältä lähtökohdalta myös tässä tehtävässä, mutta sen soveltaminen oli hitusen mutkikkaampaa kuin Datatähtitehtävässä, sillä polut eivät muodostuneet yhtä selvästi rinnakkain. Idea toimii tässäkin tapauksessa kuitenkin melko vaivattomasti: tehtävä voidaan jakaa osaongelmiin, joissa reitit ovat viimeksi menneet saariin a ja b, ja jompi kumpi poluista on käynyt kussakin max(a,b):ssä ensimmäisessä saaressa. Osaongelmat voidaan kuvata pienemmiksi osaongelmiksi valitsemalla jompi kumpi poluista menemään seuraavaksi pisteeseen max(a,b)+1. Kun tarkastellaan osaongelmaa, jossa ollaan viimeksi menty pisteisiin a ja b, osaongelman kustannusfunktio R voidaan helposti laskea rekursiolla:

R(a,b) = min( d(a,s)+R(s,b) , d(b,s)+R(a,s) ), missä s=max(a,b)+1 ja d(p,q) on etäisyys pisteiden p ja q välillä.

Koska erilaisia pareja (a,b) on vain n² kappaletta, kaikki R:n arvot saadaan laskettua dynaamisella ohjelmoinnilla ajassa T(n²), ja varsinainen lyhin kierros voidaan muodostaa näiden arvojen avulla helposti.

Vielä oli huomioitava lisärajoite, että kahdessa saarista on käytävä eri osissa kierrosta. Tämä raja ei kuitenkaan tuota mitään merkittävää vaikeutta dynaamisen ohjelmoinnin ratkaisuun, sillä tilaan voidaan lisätä tieto siitä, onko jompi kumpi reiteistä jo kulkenut jonkin erityisasemassa olevan pisteen läpi, mikä ei oleellisesti kasvata osaongelmien määrää.

Sopivan osaongelmiin jakautumisen keksimisen jälkeen tehtävä oli käytännössä hyvin helppo dynaamisen ohjelmoinnin ongelma, jonka ratkaisun näki muutamassa sekunnissa, eikä koodauskaan tuottanut suuria vaikeuksia.

(*) Datatähden loppukilpailutehtävä tehtävä lyhesti:

Susi ja kettu lähtevät liikkeelle n*n-kokoisen (n<100) ruudukon vasemmasta ylänurkasta ja oikeasta alanurkasta. Susi siirtyy aina kerrallaan ruudun oikealle tai alas, ja kettu aina vasemmalle tai ylös. Ruudukossa osaan ruuduista ei voi kulkea.

Tehtävänä on laskea, monellako eri tavalla susi voi siirtyä ruudukon oikeaan alanurkkaan ja kettu vasempaan ylänurkkaan niin, että susi ja kettu eivät kulje minkään saman ruudun läpi.

Saatuamme ratkaistua tehtävät C ja G, vilkuilimme jonkin aikaa tulostaululle. Joukkueellamme oli vielä joitakin tehtäviä jopa lukematta, mutta siirryimme suoraan pohtimaan tehtäviä D ja J, sillä lähes kaikki kärkijoukkueet olivat ratkaisseet juuri tehtävät C, D, G ja J. Pidimme todennäköisenä, että nämä tehtävät kannattaa runnoa väkisin läpi. Keskustelimme jonkin aikaa tehtävästä J, ja mieleemme juolahti idea algoritmista, joka ratkaisisi kyllä ongelman, mutta jonka aikavaativuutta oli kovin vaikea analysoida. Mikon ollessa luottavainen J:n algoritmin toimivuudesta, alkoi Mikko toteuttaa algoritmia, muiden siirtyessä pohtimaan tehtävää D.

Seuraavassa Mikon stoori tehtävästä J.

Tehtävässä J täytyi selvittää, voidaanko XxY-palan (X,Y=100) kokoinen suklaalevy jakaa annettujen N (N=15) luvun kokoisiin suorakulmion muotoisiin osiin niin, että yhtään palaa suklaata ei jää yli. Levy voidaan jakaa pienempiin osiin taittamalla se kahteen osaan vaaka- tai pystysuunnassa. Näin saatuja suklaalevyn osia voidaan edelleen jakaa pienempiin osiin.

Tehtävästä näimme lähes heti mahdollisen jaon osaongelmiin: osaongelmana on selvittää, voidaanko lukujen osajoukko muodostaa WxH-kokoisesta palasta. Osaongelma voidaan ratkaista pienempien osaongelmien avulla kokeilemalla leikata WxH-pala kahteen pienempään palaan ja jakamalla osajoukko kahteen pienempään osajoukkoon, jotka pyritään muodostamaan pienemmistä paloista.

Naiivi analyysi tuottaa näin osaongelmien määrälle ylärajan 2^N*X*Y = 2¹⁵*10⁴, mikä ei ole mahdottoman suuri luku, mutta koska joka tilassa joudutaan suorittamaan osajoukkojen jakaminen pienempiin osajoukkoon, suoritusajasta tulee luokkaa O(2^N*2^N*W*H), mikä on vähän liian hidas. Päätimme kuitenkin, että tämä ratkaisu kannattaa koodata, sillä siihen voitaisiin myöhemmin lisätä uusia optimointeja, jotka karsivat varmasti epäonnistuvia osaongelmia tehokkaammin.

Koska odotin, että ratkaisua jouduttaisiin optimoimaan melko paljon, kirjoitin sen heti suhteellisen tehokkaaksi (esim. käyttäen bittivektoreita osajoukkojen esittämiseen). Yllätykseksemme ohjelman ensimmäinen versio oli jo riittävän nopea ja toi meille kolmannen pisteen ilman suurempaa optimointitaistelua. Vasta kilpailun jälkeen tuli mietiettyä algoritmin suoritusaikaa vähän paremmin, jolloin lopulta tajusimme, että ei suoritusajassa mitään X*Y-kerrointa ollutkaan: koska yhtään suklaata ei saa jäädä yli, tarkasteltavia osaongelmia ovat ainoastaan sellaiset, joissa W*H on osaongelmassa haluttujen suklaapalojen kokojen summa, jolloin jokaiselle osajoukolle sopivia W- ja H-kertoimia on ainoastaan osajoukon summan tekijöiden verran (ja luvulla a on O(log(a)) tekijää).

Kisa-aikaa oli jäljellä vielä puolisentoista tuntia, kun saimme ratkaisevan idean D-tehtävään. Tehtävässä annettiin syötteenä puu, jonka solmut kuvasivat linnoja ja kaaret reittejä linnojen väleillä. Jokaisessa solmussa annettiin kolme kokonaislukua, jotka kertoivat montako sotilasta linnan valloittamiseen vähintään tarvittiin, montako taisteluissa tulisi menehtymään ja montako täytyy jättää vahtimaan linnaa onnistuneen valtaamisen jälkeen.

Ensimmäisen hyökkäyskohteen saa vapaasti valita, mutta tämän jälkeen kulkeminen onnistuu vain tieverkkoa pitkin. Jokaista tietä verkossa saa käyttää vain kaksi kertaa, kerran molempiin suuntiin. Tehtävänä oli tulostaa, kuinka monta sotilasta kaikkien linnojen valtaamiseen tarvitaan. Valloitettavia linnoja on maksimissaan 100.

Aloittaessamme ratkaisemaan tehtävää huomioimme ensiksi, että ei ole tapauksia, joissa linnoja vahtimaan jätetyistä sotilaista olisi ylimääräistä hyötyä, joten totesimme, että vahdit voidaan laskea samaan kastiin kuolleiden kanssa, jolloin jokaista linnaa voi kuvata kahdella luvulla - kuinka monta sotilasta hyökkäykseen tarvitaan, ja montako sotilasta hyökkäyksessä menetetään.

Tämän jälkeen aloimme pohtia, onko linnoihin hyökättäessä tarpeen suunnitella hyökkäysjärjestystä. Yritimme siis selvittää, että joudummeko käyttämään tarpeettoman paljon sotilaita, mikäli hyökkäämme aina satunnaiseen linnaan ensiksi. Nopeasti osoittautui, että satunnaiseen linnaan hyökkääminen ei aina tuota parasta vastausta.

Ilmeni siis, että tarvitsimme järkevämmän algoritmin hyökkäysjärjestyksen määrittämiseen. Vaikutti siltä, ettei kaikkien hyökkäysvaihtoehtojen tutkiminen tulisi kysymykseen, sillä parhaimmillaankin tällaisen algoritmin aikavaatimus muotoutui eksponentiaaliseksi linnojen määrän suhteen, eikä tarvittavan hyviä optimointeja näyttänyt olevan näköpiirissä.

Kaikkien reittien tutkimisen osoittauduttua hankalaksi alkoi vaikuttaa mahdolliselta, että reittien tutkimiseen voisi käyttää jonkinlaista heuristiikkaa siitä, millainen linna valitaan ensimmäiseksi. Ensimmäisenä mieleen tullut heuristiikka, joka valitsee ensimmäiseksi tutkittavaksi aina linnan, jonka valtaamiseen vaaditaan eniten joukkoja, osoittautui virheelliseksi. Kokeilimme useita muitakin heuristiikkoja, joista monet muutkaan eivät kriittistä tarkastelua kovin hyvin kestäneet.

Useiden kokeiluiden jälkeen, juuri kun usko lähestymistapaamme alkoi murentua, keksimme heuristiikan, joka vaikutti lupaavalta: siirrytään aina ensiksi linnaan, jossa vaadittujen sotilaiden ja menetettyjen sotilaiden välinen erotus olisi mahdollisimman suuri. Emme nopeasti löytäneet tapausta, jossa uusi heuristiikkamme ei toimisi, ja koska olimme käyttäneet jo kovin paljon aikaa tämän tehtävän pohtimiseen, vaikutti järkevältä siirtyä pohtimaan muita tehtäviä ja laittaa joku koodaamaan tätä. Koodaus sujui vikkelästi, ja korjattuamme yhden hupsun bugin saimme koodin läpi, ja neljäs piste oli mukavasti plakkarissa.

Kun D-tehtävän ohjelmointi saatiin vauhtiin, luimme uudelleen joitain tehtäviä, jotka olimme jättäneet vähemmälle huomiolle. Löysimme näiden joukosta tehtävän B, joka periaatteessa oli kovin yksinkertainen tehtävä, jossa tehtävänä oli selvittää, mitä tekstiä viivakoodi esittää, kun syötteenä annettiin optisen laitteen sensoreiden lukema väriskaala. Tehtävän toteuttaminen vaikutti kuitenkin vaativan kohtuullisesti aikaa ja vaikutti bugialttiilta. Saimme 30 sekuntia ennen loppua ohjelman toimimaan esimerkkisyötteillä, mutta ohjelmasta puuttui vielä yksi tarkastus, eikä se tulostanut vastausta pyydetyssä muodossa. Tästä tehtävästä jäi siis joukkueeltamme pisteet saamatta :). Myös H-tehtävän ratkaisuhahmotelma oli joukkueellamme valmiina, mutta koodin kirjottamista emme ehtineet edes aloittaa.