Keskustelu: Yleinen keskustelu: Datatähti 2010

Tänään alkaa Datatähti 2010 -kilpailu:

http://www.cs.uta.fi/datatahti/

Datatähti on ohjelmointikilpailu, johon voivat osallistua lukion ja peruskoulun oppilaat. Alkukilpailu on 27.10.–10.11.2009, ja sen vastaukset palautetaan sähköpostitse. Alkukilpailun perusteella valitaan osallistujat loppukilpailuun, joka pidetään 28.1.2010 Helsingin yliopistolla.

Suosittelen lämpimästi osallistumista Datatähteen, jos algoritmien ohjelmointi kiinnostaa ja haluaa oppia niistä enemmän. Lisäksi kilpailussa oppii tuntemaan ohjelmoinnista kiinnostuneita nuoria ympäri Suomen.

Kilpailun parhaille on tiedossa ohjelmointialan kirjallisuutta ja oikeus osallistua ohjelmointileireille yliopistossa. Kilpailijoiden joukosta valitaan myös Suomen joukkueet kansainvälisiin ohjelmoinnin olympialaisiin (BOI ja IOI), jotka pidetään vuonna 2010 Virossa ja Kanadassa.

Tervetuloa mukaan Datatähteen!

Hyviä tehtäviä taas kerran! Ensimmäinen vaatii melko yksinkertaista logiikkaa ja toinen on tyypillinen kombinaatiotehtävä. Kolmas taitaa olla taas Heikki Hyyrön käsialaa: rajat ovat todella tiukat sekä muistin että ajan puolesta.

Muut tehtävät ratkesivat hyvinkin lyhyillä ohjelmilla, viimeinen vei kymmenkertaisesti tilaa.

Liukumäkitehtävässä kerrosten numerointi on jokseenkin epälooginen. :)

Onko tää Uolevi muuten joku sisäpiirijuttu kun tuntuu esiintyvän putkan tehtävien lisäksi tuolla datatähden tehtävissäkin?

Uolevi on vähän samanlainen hahmo tehtävissä kuin Pikku-Kalle on vitseissä. Vastaavasti englannin kielessä Farmer John on yleinen tehtävän henkilö.

Tänä vuonna kysymykset tuntuvat huomattavasti helpommailta kuin aikaisempina, liekö syynä oma kehitys vain :)

Jaah, aikalailla epäselvät sivut, enkä löydä mistään millä kielellä pitäisi koodaukset tehdä...

Ohjelmointitehtävien seitsemännellä sivullahan nuo lukevat.

lainaus:

Kunkin ohjelmointitehtävän vastauksessa sallitut ohjelmointikielet ovat C, C++ ja Pascal.

Hakoulinen kirjoitti:

Tänä vuonna kysymykset tuntuvat huomattavasti helpommailta kuin aikaisempina, liekö syynä oma kehitys vain :)

Mutta ei nuo tänä vuonnakaan helppoja ole, koska vaikea tehdä tarpeeksi nopea ohjelma (varsinkin viimeiseen tehtävään). Ensimmäinen tehtävä on helpoin (ainakin luulisin, että on oikea logiikka).

Hauskoja tehtäviä, mutta tuntuvat selvästi helpommilta kuin viimevuotiset. Ei siinä mitään, mutta veikkaan että on saatava kovat pisteet esseetehtävästä pärjätäkseen..

Nyt pitää vain keksiä mihin käyttäisi 60 000 ylimääräistä mikrosekuntia kakosessa..

Mustikka-tehtävän korkeasta rajasta näkee, että yksinkertainen O(n)-luokan ratkaisu ei tule kyseeseen, jos aikoo saada täydet pisteet. (Huvikseni kokeilin optimoida tällaista ratkaisua. Sain sen optimoitua omalla koneellani C:llä 3,5 sekuntiin ja Assemblylla tasan kolmeen.) Yleensä O(n)-ratkaisua nopeampi ratkaisu on joko O(1)-aikainen eli käytännössä yksi lauseke tai O(log n)-aikainen eli algoritmi, joka puolittaa (tai muuten jakaa) tutkittavan aineiston (tässä mustikoiden määrän) joka kierroksella. Kummassakin tapauksessa aikaa kuluu erittäin vähän.

Liukumäki-tehtävässä ratkaisuni käyttää noin puolet annetusta ajasta selvästi kilpailukonetta hitaammalla koneella, kun syötteessä on 1000 kerrosta ja 1000000 mäkeä (eli kaksi mäkeä jokaisella kerrosvälillä).

Eristys-tehtävässä ratkaisuni vie enimmillään puolisen sekuntia (löytämilläni testisyötteillä). Testauksessa hyviä erikoistapauksia ovat vinoneliö ja ristikko. Nämä on melko helppo luoda omalla ohjelmalla.

...1... | .1.1.1.
..121.. | 1212121
.12321. | .1.1.1.
..121.. | 1212121
...1... | .1.1.1.

Suurin tällainen vinoneliö sisältää 31992001 ja ristikko 12004000 päällystettyä ruutua, joista mitkään vierekkäiset eivät ole päällysteeltään yhtä paksuja. Melkoisista määristä siis puhutaan.

Ohjelmien ajoajat antavat jonkinlaisen näkymän, millaiseen tulokseen hyvällä algoritmilla voi päästä. Missään tehtävässä itse algoritmia ei tarvitse erityisesti viritellä, jos vain keksii oikean idean. (Liukumäki-tehtävässä kuitenkin syötteen luku nopeasti on jo aivan oma tehtävänsä.)

Kannattaa silti muistaa, että pisteitä jaetaan myös hitaammille algoritmeille. Usein tehtävissä on pari väliporrasta: hitaalla mutta oikealla perusalgoritmilla (esim. täyttämällä seinää 1000*1000-kokoiseen lukutaulukkoon) voi saada vaikkapa 30 pistettä ja nopeammalla muttei parhaalla algoritmilla suunnilleen 70 pistettä. (Joskus tällainen hitaampi algoritmi riittää jopa täysiin pisteisiin, jos sen onnistuu optimoimaan hyvin.)

Tällaisia vinkkejä tänä vuonna. Onnea kilpailuun kaikille kilpailuikäisille!

Kun lukee näitä viestejä tulee tosi noob olo. Itsellä on ensimmäiseen tehtävään O(1) ratkaisu. Muut tehtävät on liian hitaita. Liukumäki tehtävän olen ratkaissut rekursiolla, mikä on aivan liian hidas ratkaisu =/ Algoritmia vaan etsimään. En näillä ratkaisuilla ainakaan viitsi osallistua kilpailuun. Saisi hävetä silmät päästä =)

Olenkohan nyt ymmärtänyt jotain noissa tehtävissä ihan väärin, kun minusta näyttäisi, että 2. tehtävä on hankalampi ja koodina pitempi kuin 3., ei kymmenen kertaa lyhyempi? Mietiskelen ehtiikö ohjelma edes lukea tiedostosta miljoonan liukumäen dataa 0,1 sekunnissa, miljonallahan tuossa uhattiin. Ja että mustikkatehtävässä tarvitaan vain yksi simppeli lauseke, jotta selviää kumpi voittaa, mutta sille on annettu aikaa kymmenen kertaa enemmän kuin 2. tehtävälle.

No ei se 2.tehtävä ollutkaan niin vaikea kuin aluksi luulin. Keksin O(n^2) ratkaisun ja se on tarpeeksi nopea pahimmillakin syötteillä. Pitää vielä koittaa keksiä nopeampi ratkaisu viimeiseen tehtävään.

hk kirjoitti:

Olenkohan nyt ymmärtänyt jotain noissa tehtävissä ihan väärin, kun minusta näyttäisi, että 2. tehtävä on hankalampi ja koodina pitempi kuin 3., ei kymmenen kertaa lyhyempi?

Omassa ratkaisussani 2. tehtävään on suunnilleen 10-15 mielenkiintoista riviä. Idea on aika yleinen algoritmikilpailuissa ja minusta todella yksinkertainen, ei ollenkaan hankala. Kolmatta en ole ratkaissut, mutta kyllä se selvästi vaikeammalta näyttää kuin kaksi ensimmäistä.

Saako aikuislukiossa opiskeleva osallistua?

funktio kirjoitti:

Saako aikuislukiossa opiskeleva osallistua?

Tässä ei pitäisi olla ongelmaa, mutta voisit vielä varmistaa asian Heikki Hyyröltä. Lähinnä oleellista on, että ei ole liian vanha (korkeintaan 20-vuotias) ja on kirjoilla jossain yliopistoa alemmassa oppilaitoksessa.

Tuntuu kyllä käsittämättömän vähältä tuo 2. tehtävän aikaraja. Etenkin jos sitä vertaa esim. ensimmäisen tehtävän aikarajaan. Omalla c++ ohjelmallani menee n. 400ms pelkän tiedoston lukemiseen jossa on 1 000 000 liukumäen data. Kyseinen tiedostohan on n. 8Mt kooltaan ja nykyisillä kiintolevynopeuksilla ei tuommoista jöötiä kyllä lueta millään alle 100ms, saatikka sitten kun laskun suorittamiseen kuluva aika pitäisi lisätä tuohon.

Noh kaipa testikokoonpanossa on ssd-kovoja raidissa tai jotain...

Käsittääkseni kiintolevyn odottamista ei lueta käyttäjän aikaan.

Mitenkäs tuota muistin ja ajankäyttöä voi mitata? Olen itse saanut kaikki kolme koodia suurin piirtein valmiiksi, mutta epäilen, että yhdessä saattaa mennä koodi uusiksi ajankäytön takia.

Liinuksissa ajat vaan "time ./ohjelman_nimi"

Ja näinhän minä tuota lukuaikaa mittasinkin, kyllä sitä aikaa vaan menee kun tuo jööti sinne muistiin luetaan.

Murzka kirjoitti:

Liinuksissa ajat vaan "time ./ohjelman_nimi"

Ja näinhän minä tuota lukuaikaa mittasinkin, kyllä sitä aikaa vaan menee kun tuo jööti sinne muistiin luetaan.

Itse en käytä linuxia. Voiko sitä mitata muulla tavalla?

Yksi tapa arvioida aikaa on käyttää funktiota clock:

...
#include <time.h>
...
clock_t alku, loppu
...
alku = clock();   // ohjelman alussa
...
loppu = clock();  // ohjelman lopussa
...
printf("Aika: %lf\n", (double)(loppu - alku) / CLOCKS_PER_SEC);
...

Antti Laaksonen kirjoitti:

Yksi tapa arvioida aikaa on käyttää funktiota clock:

...
#include <time.h>
...
clock_t alku, loppu
...
alku = clock();   // ohjelman alussa
...
loppu = clock();  // ohjelman lopussa
...
printf("Aika: %lf\n", (double)(loppu - alku) / CLOCKS_PER_SEC);
...

Pistin alku = clock(); main() funktion alkuun ja loppu = clock(); loppuun sitten pistin sen kirjoittamaan tuloksen erilliselle tiedostolle file2 << (loppu - alku) / CLOCKS_PER_SEC << endl;. Tiedostossa oli pyöreä nolla. Mikä meni vikaan?

Vikaan meni luultavamminkin se, että tulos tulkittiin kokonaisluvuksi. Tee siis vielä tuo doubleksi muunnos, kuten Antti tuossa koodissaankin.

Teuro kirjoitti:

Vikaan meni luultavamminkin se, että tulos tulkittiin kokonaisluvuksi. Tee siis vielä tuo doubleksi muunnos, kuten Antti tuossa koodissaankin.

Kuinka tuo doubleksi muunnos sitten tehdään, jossei käytetä printf() funktiota?

Otat ihan suoran kopion tuosta Antin koodista (double)(loppu - alku)

Teuro kirjoitti:

Otat ihan suoran kopion tuosta Antin koodista (double)(loppu - alku)

Kokeilin jo aikaisemmin kirjoittaa file2 << (double)(loppu - alku) / CLOCKS_PER_SEC << endl;. Tulos pysyi samana. Pitäisikö se kirjoittaa eri tavalla?

Onko noiden kahden koodirivin välissä mitään suoritettavaa? Nykyinen tietokone vaatii tuohon väliin nimittäin aika raskasta laskentaa, jotta saisit luvuksi jotain muuta kuin nollan. Joku raskas laskuoperaatio tai ison tiedoston lukeminen voisi olla tarpeeksi hidasta.

Liukumäkitehtävän syöte täytyy käytännössä lukea tiedostosta isompina paloina tekstimuodossa ja muuttaa luvuiksi vasta ohjelmassa, jotta toteutuksesta saisi tarpeeksi nopean. Omalla koneellani syötteen luku kestää muuten (sekä C:llä että C++:lla) reilusti yli aikarajan verran.

Teuro kirjoitti:

Onko noiden kahden koodirivin välissä mitään suoritettavaa? Nykyinen tietokone vaatii tuohon väliin nimittäin aika raskasta laskentaa, jotta saisit luvuksi jotain muuta kuin nollan. Joku raskas laskuoperaatio tai ison tiedoston lukeminen voisi olla tarpeeksi hidasta.

Se näyttää jotain muuta kuin nollaa :o . Aikamoinen laskentaurakka siihen pitikin laittaa väliin.

Arvaisin että kun jaat CLOCKS_PER_SEC:llä niin double-tyyppi häviää ja syntyy joku intti. Kokeileppa näin:

file2 << (double)(loppu - alku) / (double)CLOCKS_PER_SEC << endl;

Deffi, ei noin voi tapahtua. Laskun tuloksena on aina tyypeistä tarkempi, siis intin ja doublen tapauksessa double.

Liukumäkitehtävässä C++:n virtoja syötteen lukemiseen käyttävien kannattaa muistaa poistaa käytöstä yhteistoiminta C:n funktioiden kanssa ohjelman alussa seuraavasti:

std::ios_base::sync_with_stdio(false);

Tämä nopeuttaa syötteen lukua std::cin-virrasta merkittävästi. Omalla koneellani vie liukumäkitehtävän syötteen luku ilman tuota rivia Metabolixin tavoin yli sekunnin, mutta sen kanssa jää aika selvästi alle.

Sisuaski, syöte luetaan tiedostosta (liukumaki.in), joten tuo ei vaikuta. Sitä paitsi kokeideni perusteella aikaa kuluu sekä C:n että C++:n lukutavoilla suunnilleen yhtä kauan, moninkertaisesti aikarajaan nähden. Huomaathan, että tehtävän aikaraja on 0,1 sekuntia. (FAQ:ssa vahvistetaan, että kyseessä ei ole kirjoitusvirhe.)

En usko, että tämä on ollut tehtävän tarkoitus. Katsotaan, mitä järjestäjät päättävät tehdä asialle.

Okei, jäivät nämä kaksi asiaa huomioimatta eli aiemmin sanomani voidaan unohtaa. On taas Hyyrö ollut vauhdissa aikarajojensa kanssa näemmä sitten.

FAQ-sivulta:

http://www.cs.uta.fi/datatahti/faq.html:

Aikaraja 0,1 sekuntia määritettiin suurimman pisteytyksessä käytettävän testisyötteen viemän suoritusajan perusteella. Valitettavasti vasta nyt tehtävien julkaisun jälkeen kävi ilmi, ettei tehtävän laatijan suurinkaan testisyöte sisälläkään läheskään tehtävänannossa mainittua ylärajaa eli miljoonaa liukumäkeä. Voit olettaa, että liukumäkiä on korkeintaan 100000 ja että tavallinen syötteenluku (esim. fscanf-funktiolla) riittää maksimipisteisiin.

Höh, ihan tyhmää kun rajoja laskettiin. Minusta tuo syötteen lukeminen riittävän nopeasti toi muuten niin helppoon tehtävään edes vähän lisää haastetta.

Käytännössähän rajaa ei laskettu. Eli jos asiasta ei olisi ilmoitettu niin jotkut olisi vaan turhaan nysvänneet riittävän nopeaa käsittelijää aineistolle, jota testissä ei kuitenkaan käytetä.

Tehtävät eivät selvästikään ole kaikille helppoja: osallistujia ei yleensä ole kuin joitakin kymmeniä. Alkukilpailussa on tarkoitus erottaa parhaat 20 muusta joukosta, ja veikkaan, että ainakin viimeinen tehtävä tuo tätä varten tarpeeksi eroja, jos syötteet on laadittu huolellisesti.

Esseetehtävä on tänä vuonna melko tylsä. Viime vuonna oli paljon parempi.

Olisi kiinnostavaa nähdä, millaisia ratkaisuja muut keksivät eristys-tehtävään. Minulla oli joitain ideoita, mutta toteutin vain tylsän O(ABN)-aikaa vievän bruteforcen.

Suunniteltiin, että tehtävistä julkaistaisiin vielä virallisemminkin malliratkaisut, jotta ensi vuonna osallistumista harkitsevat löytäisivät ne ja näkisivät, millaisia ratkaisuja suunnilleen voi olla. Tässä on kuitenkin muutama lyhyt selostus.

Mustikat

Ratkaisu toimii vakioajassa (O(1)), nimittäin pelissä toistuu nollasta mustikasta alkaen seitsemän merkin sykli "TATAAAA". Tämän voi löytää päättelemällä tai vaikka laskemalla jollain hitaammalla menetelmällä ensimmäiset sata tapausta. Tehtävä ratkeaa siis mustikoiden määrän jakojäännöksestä.

#include <fstream>
std::ifstream syote("mustikat.in");
std::ofstream tuloste("mustikat.out");

int main() {
	unsigned int mustikoita;
	syote >> mustikoita;
	tuloste << "TATAAAA"[mustikoita % 7] << std::endl;
}

Liukumäkitalo

Algoritmin vaativuus on O(N²), missä N on kerrosten määrä. Jos kerrokseen A on kolme tapaa tulla ja siitä on kaksi tapaa jatkaa kerrokseen B, on kaikkiaan kuusi tapaa, joissa mennään ylhäältä A:n kautta B:hen. Ratkaisun voi toteuttaa alhaalta ylös tai ylhäältä alas, mutta joka tapauksessa vaatimuksena on, että ylhäältä tullessa A tai alhaalta tullessa B on käsitelty loppuun.

Tehtävä ratkeaisi rekursiivisesti, jos lisäksi pidettäisiin jo lasketut tulokset muistissa, mutta myöskään iteraatio ei ole tällä kertaa kovin hankala. Seuraava ratkaisu on tehty alhaalta ylös, eli aina loppuun johtavat reitit tunnetaan (alimmasta kerroksesta on yksi reitti, koska ollaan jo perillä).

#include <fstream>
std::ifstream syote("liukumaki.in");
std::ofstream tuloste("liukumaki.out");

// Mäkien määrä kerrosten välillä.
int makia[1002][1002];

// Reittien määrä kustakin kerroksesta loppuun.
long long int tulos[1002];

int main() {
	int kerroksia, makia_yhteensa;
	syote >> kerroksia >> makia_yhteensa;
	for (int i = 0; i < makia_yhteensa; ++i) {
		int a, b;
		syote >> a >> b;
		++makia[a][b];
		++makia[b][a];
	}
	// Alimmassa kerroksessa on yksi tapa: on oltava liikkumatta.
	tulos[kerroksia] = 1;

	// Muissa kerroksissa...
	for (int i = kerroksia - 1; i > 0; --i) {
		// ...voidaan laskea johonkin alemmista kerroksista...
		for (int j = kerroksia; j > i; --j) {
			// ...(makia[i][j]) eri liukumäkeä ja sieltä
			// jatkaa loppuun (tulos[j]) eri reittiä.
			tulos[i] += makia[i][j] * tulos[j];
		}
	}
	tuloste << tulos[1] << std::endl;
}

Jos tehtävän syötteen koko olisi pidetty miljoonassa, olisi täytynyt toteuttaa ifstream-luokan tilalle (tai lisäksi) oma syötteenluku. Riittää, kun lukee tiedostoa muutaman kilotavun paloina ja muuttaa tekstin luvuiksi itse silmukassa.

Eristys

Tehtävään voi olla muutamakin erilainen ratkaisu, mutta aivan helpolla siinä ei pääse. 20000² eli 400000000 ruutua iso ruudukko ei tule kysymykseenkään, koska se ei mahdu edes millään kokonaan muistiin. Ruudukon saa pienennettyä 8000² eli 64000000 ruutuun, kun huomaa, että on 4000 levystä tulee enintään 8000 reunaa. Tämä ei valitettavasti paljon lohduta, koska pahin tapaus ei taaskaan mahdu muistiin sellaisenaan.

Omassa ratkaisussani on kaksi kekoa (prioriteettijonoa). Yhdessä ovat levyt, joita ei ole käsitelty, ja ensimmäisenä ulos tulee se, jonka pienempi y-koordinaatti on pienin eli joka alkaa ylimpänä. Toisessa ovat levyt, joita käsitellään tällä hetkellä, ja ensimmäisenä ulos tulee se, jonka suurempi y-koordinaatti on pienin eli joka loppuu ylimpänä. Lisäksi on kartta, jossa kerrotaan x-suunnassa paksuuden muutokset: jos kohdasta x = 3 alkavat 5 ruutua ja 6 ruutua leveät levyt, kartassa on kohdassa 3 luku 2, kohdassa 8 luku -1 ja kohdassa 9 luku -1. Kartta sisältää vain juuri käsiteltävien levyjen tiedot.

Aluksi kaikki levyt ovat käsittelemättömiä. Kun levyjä on jäljellä, haetaan seuraava y-koordinaatti, jossa niitä alkaa tai loppuu. Sitten lasketaan kartan perusteella eristyksen paksuus eri kohdissa x-suunnassa edellisen y-koordinaatin ja seuraavan y-koordinaatin välillä. Lopuksi siirretään kaikki seuraavan y-koordinaatin kohdalla alkavat levyt käsiteltävien joukkoon ja loppuvat levyt pois. Siirtelyn yhteydessä päivitetään karttaa, eli jokaisen käsiteltäväksi tulevan levyn alkukohtaan lisätään yksi ja loppukohdasta vähennetään yksi, poistettavilla levyillä päinvastoin.

Algoritmin aikavaativuus on pahimmassa tapauksessa luokkaa O(N²) levyjen määrän suhteen. Pahimpia tapauksia ovat ristikko ja timantti, jotka mainitsin aiemmin. Parhaassa tapauksessa (kaikki levyt identtisiä) ajoaika on O(N log N), joka tulee kekojen ja paksuuskartan kanssa kikkailusta; loppu algoritmista (se O(N²)-vaativuuden aiheuttava osuus) vie parhaimmillaan ajan O(1).

Koodi on noihin muihin verrattuna aika pitkä, joten en laita sitä tähän.

Mitä muut ovat eristykseen keksineet?

Itsellä oli ensimmäisessä tehtävässä tietenkin sama idea kuin Metabolix:lla. Toinenkin tehtävä on ratkaistu samalla tavalla, itsellä vain on toteutus nopeampi ;D (ainakin kun kokeilin MONILLA eri syötteillä, niin oli lähes aina noin 0,005-0,02 sekuntia nopeampi). Viimeiseen tehtävään on niin huono ratkaisu, etten viitsi edes sanoa sitä.

Oma eristysratkaisuni on tällainen:

Tallennetaan taulukkoon jokaisen suorakulmion pystysuuntainen sivu ja järjestetään ne. (eli x-koordinaatti, alku- ja loppupiste y-akselilla, sekä onko vasen vai oikea reuna). n * log(n) aikaa.

Lähes sama homma y-akselilla, tosin nyt tarvitsee vain tallettaa pelkkä y-koordinaatti JA jokainen vain kerran. Bittitaulukon avulla hoituu jälkimmäinen, sorttaamiseen taas n * log(n) aikaa.

Y-akselin pisteistä tehdään binääripuu, jossa säilytetään paksuutta y-akselin eri väleillä. n * log(n) aikaa ja tilaa.

Lopuksi käydään läpi tuo x-taulukko. Vasen reuna kohdattaessa kasvatetaan kyseistä y-akselin välin paksuutta binääripuussa. Oikea reuna kohdattaessa vastaavasti vähennetään (korkeintaan log(n) aikaa). Haetaan sieltä puusta niiden y-välien, joiden paksuus >= P, summa (aika vaihtelee aika paljon, olisiko jotain luokkaa log(n) keskimäärin?) ja kerrotaan etäisyydellä edelliseen x-hommeliin ja lisätään tuo pinta-ala laskuriin. And that's it. Tästä selityksestä saikin hyvin selvää.

Randomgeneroiduilla testisyötteillä keskimäärin 0.04 s (kun N=4000). P:n, X:n, ja Y:n arvoilla ei juurikaan ole merkitystä. Pahin tapaus (mitä keksin) on juurikin tuo ruudukko, suurimmalla sellaisella kestää ~0.55 s. Oma intuitio sanoopi, että silloin aikaa kuluisi yht. O(n^2 * log(n)) (koska silloin jokainen hakuoperaatio puussa käy koko puun läpi, eli n*log(n)). Mutta silti näkyy pärjäävän yllättäen hyvin, odotin paljon hitaampaa tuossa tilanteessa.

Ja liukumäkitehtävässä mielestäni hitautta syötteen luvussa aiheuttaa eniten standardikirjastojen thread-safety: tein oman syötteenlukijan käyttäen niitä ei-threadsafe versioita. Ero getchar:in ja getchar_unlocked:in välillä oli noin 100x!

Kuvauksesi vastaa kai suunnilleen omaani, olet vain toteuttanut sen eri tietorakenteilla (ja eri akseleilla): kekojen sijaan olet käyttänyt järjestettyjä taulukoita (aikavaativuus sama), ja ilman parempaa tietoa veikkaan, että C++:n map on toteutettu binaaripuulla, koska yksittäisen lisäyksen aikavaativuudeksi luvataan siinäkin log(n). Binaaripuun voi käydä läpi lineaarisessa ajassa, joten algoritmisi aikavaativuus on ehkä sama O(n^2) kuin minullakin.

Pahin tapaus tällaiselle algoritmille on se, jossa on paljon eri x- ja y-koordinaatteja, koska joka y-koordinaatilla täytyy käydä läpi kaikki sillä korkeudella esiintyvät x-koordinaatit, joissa paksuus muuttuu. Ristikossa ja vinoneliössä on juuri maksimoitu näitä.

Liukumäkitehtävässä alustin tuloksen tyypiksi int...
Paikallisen lukion oppilaat koodasivat varjotuomarit datatähteen, sisäverkkoon.
Liukumäestä 25 mokan takia, 100 long long intillä. 50 eristyksestä. Taitaa jäädä loppukilpailu seuraavaan vuoteen.

Liukumäki tehtävän ratkaisuni oli erittäin yksinkertainen. Luin datan, sorttasin sen aloituspisteen mukaan. Sitten vain lasketaan mäkiä järjestyksessä __for(int i=0;i<maet;i++)__ loopilla.

Millonkohan tiedot finaaliin päässeistä sitten ilmoitetaan? Olisi kiva ettei tarvitsisi jännätä kovin pitkää aikaa.

Aika lähelle joulua menee, eli joudut jännäämään melko kauan. Oiskohan joskus 20.12 tulokset selvillä.

Itse käytin jo tuotantovaiheessa pientä tuomarikoodia jolla tarkistin että tulokset olivat oikeita ja että suoritus tapahtui aikarajan sisällä.

Trainerikoodi on osoitteessa http://sipuli.net/joonas/trainer.cpp . Koodin kääntäminen vaatii myös timer.h tiedoston joka löytyy samasta osoitteesta. Windowsilaiset saavat vaihtaa rivin system(((std::string("./")+filename).c_str()));

riviksi

system((filename+".exe").c_str()));

Muistakaa myös laittaa samaan kansioon käännetyt versiot vastauksistanne. Ohjelma tuottaa minimi, maksimi ja keskiarvo suoritusajat ohjelmista ja esim. eristystehtävää varten vertailee vastauksesi tuloksia naiivin ratkaisun tuloksiin (jotka on helpompi saada oikein)

Hauska juttu, mikkisoftan kääntäjältä loppuu muisti noissa mun makropelleilyissä. GCC suositeltu.

Olisi kiva, jos tuo antaisi pisteetkin =)

Mitenkäs putkalaiset pärjäsivät tässä kilpailussa. Itselle tuli kirje postilaatikkoon :D

{Koodasin viimeisillä minuuteilla verta nenästä valuen ja ES:ää hörppien. En ehtinyt tarkastaa ja palautin tehtävät n. 23:30.}
-> päätelmäsi

Tännepäin ei ole kukaan ilmoittanut mitään kilpailussa finaaliin päässeistä. Tuleeko siitä johonkin jonkinlainen lista tai lappunen vai pitääkö vain veikata?

Yleensä tuonne http://www.maol.fi/index.php?id=63 on tullut lista, mutta jostain syystä ei ole tänä vuonna tullut.

Uinutin: Viime perjantaina MAOLilta tuli postissa loppukilpailukutsut ja tuloslista. Ihme hommaa kyllä kun eivät nettiin ole vaivautunut laittamaan.

Omassa sijoituksessani ei kyllä ole valittamista... Ehkä hieman yllätyin omista esseepisteistä, eivät tosiaankaan vastanneet nykyistä äikän numeroa :).

Kiva muuten nähdä, että tänä vuonna on enemmän tyyppejä ympäri Suomea, viimeksi taisi olla melkein puolet Päivölästä... Nyt oma koulu tasoissa niiden kanssa, woohoo!

Tulokset:

Jos jollain on jotain listan julkistamista vastaan, voin poistaa sen.

Minulla oli kolmas ohjelmointitehtävä ja esseetehtävä kokonaan ratkaisematta vielä 3 tuntia ennen deadlineä, tiukalle meni. :]

Tuomas Tynkkynen kirjoitti:

Ehkä hieman yllätyin omista esseepisteistä, eivät tosiaankaan vastanneet nykyistä äikän numeroa :).

Datatähden esseissä ei arvostella kielitaitoa tai luovuutta, vaan pääosassa ovat tiedon määrä ja laatu sekä sen looginen esittäminen. Äidinkielessä tiedon määrä ja laatu ovat usein sivuseikka. ;)

Onnea vain kaikille osallistujille, osalle vielä parempaa onnea ensi vuonna. Harjoittelemalla tuollakin parhaiten pärjää.

Onko tuo lista jatkoon päässeistä, kahdenkymmenen kärjestä vai kaikista osallistujista?

Jatkoon päässeistä eli kahdenkymmenen kärjestä. Se oli kirjeessä joka tuli MAOLilta.

Hienoa että mode teki tuon taulukon vaikken sitä ennen tuota nähnytkään mutta harvalla palstalla tuntuu modet ns ymmärtävän yskän. Tarkoitan siis huolehtiä tehtävistään ja pitää palstan luettavuutta yllä.

Loppukilpailun tulokset:

Kaksikko funktio ja Sharph karkasi siis kauas muista. Moni muukin voi olla ylpeä suorituksesta – tehtävät olivat jälleen kerran todella haastavia.