Uusi putkapostitehtävä on vihdoin ilmestynyt:
https://www.ohjelmointiputka.net/postit/tehtava.
Tähän mennessä Putkapostin tehtävät ovat olleet lähinnä toinen toistaan vaikeampia. Tämä lipputehtävä on kuitenkin hieman helpompi. Tarkoitushan ei ole, että tehtävät ovat vain muutaman edistyneen kävijän ratkaistavissa.
Tietotekniikan olympialaiset olivat viime vuonna Puolassa. Silloin harjoitustehtävien joukossa oli tehtävä, jossa kolme lasta kokosi Puolan lippua palikoista. Siitä sain idean tähän tehtävään.
Tuntuu siltä, että tein kaiken oikein, ja esimerkistä tuleekin oikea vastaus. Kaikki varsinaiset tehtävät menevät kuitenkin pieleen. Joten, pari varmistuskysymystä.
Lipun korkeus kasvanee samaa tahtia kuin pituuskin? Eli esim. ykköstehtävässä, jossa leveys on 36, korkeus on 22?
Jos meillä on vaikka tällainen tilanne (M on Maijan palikka, L Laurin, piste tarkoittaa tyhjää tilaa):
MM. M.. ..L
Seuraavalla vuorolla tilanne on tällainen:
MMM MML MLL
Mutta pitääkö nyt edelleen seuraavalla vuorolla vielä tarkistaa, josko vaikkapa tuo ylin Laurin laittamista palikoista kuuluisi Maijalle, koska se on sinisen palikan paikka?
Toisella tavalla ilmaistuna: tarkistetaanko "kohtaamistilanteet", joissa sekä Maija ja Lauri haluavat laittaa palikan johonkin kohtaan, myös silloin kun siinä kohdassa on jo palikka, vai onko ensin paikalle ehtinyt se, joka saa palikkansa sille paikalle?
Näin hirveästi ajattelematta arvelisin, että jos näin ei ole, hyvin moni aloitustilanne johtaa vain siihen, että Maija vie kaikki siniset paikat ja Lauri kaikki valkoiset.
Itse tein niin, että ensimmäinen omistaa paikan, ja systeemihän ei vastauksiani hyväksy.
EDIT: Toisaalta, kun saan kerran esimerkistä oikean vastauksen, lienen päätellyt oikein ja virhe on jossain muualla? Vai onko tuo arveluni vain tyystin pielessä?
Itsekin epäilen, että tehtävän tarkistuksessa on jotain häikkää.
Minun ohjelmaani oli jäänyt virhe, jonka takia vastaukset olivat hieman pielessä. Nyt tarkistus on korjattu, ja voitte kokeilla lähettää vastauksia uudestaan. Eipä olisi kannattanut mainita tehtävää helpoksi!
Toivottavasti tarkistus nyt toimii oikein. Putkapostin tarkistuksen soisi kuitenkin olevan virheetön, kun omissa ohjelmissa on helposti todellisiakin virheitä.
hmm, taisin joskus tehdä ton polish flagin. noh katsotaan
... ja olihan se helppo, kunhan oli tarkka.
p.s olinpa hidas
Löytyihän sieltä vielä yksi bugi, joka korjasi puuttuvat vastaukset. Tuntuikin kummalta kun 14 20:stä olivat oikein, ja väärinmenneillä ei vaikuttanut olevan mitään erityistä yhteistä.
tylsää, vaikka sain ekana 20 niin olen silti toisena listassa :/
Jos monella on yhtä hyvä tulos, tuo menee kai aakkosjärjestyksessä.
Ne taitaa tulla siihen siinä järjestyksessä kenellä oli ensimmäisenä jokin tulos. Taisin olla ensimmäinen, joka lähetti bugisen vastauksen.
Jep. Tuosta on valitettu aikaisemminkin. Mutta eipä sillä minusta suuremmin väliä ole.
Tällä kertaa oli niin helppo tehtävä, että siitä selvisi ihan omin avuin! Nuo 20 tehtävää oli vähän tyhmästi valittu. Brute Forcella sain 3 ratkaistua. Jos oikean tyylin löytää, on edessä aikamoinen copy paste urakka, jotta saa kaikki koordinaatit välitettyä ohjelmaan.
äh, tein pienen perl-pätkän joka teki 20 inputtiedostoa, ja sit vaan shelliskiptalla inputtiin inputtitiedostot :)
Touho kirjoitti:
Jos oikean tyylin löytää, on edessä aikamoinen copy paste urakka, jotta saa kaikki koordinaatit välitettyä ohjelmaan.
Itse etsin viimeistä bugia aika kauan ennen kuin huomasin, että olin typottanut yhden tehtävän alkukoordinaatit.
Minä puolestani tein ohjelmaani pätkän joka lukee alkutiedot erillisestä tiedostosta. Sitten vain tehtävänannon alkutiedoista kopio siihen.
Itse olen kuitenkin hiukan sitä mieltä, että näin monta tehtävää näin pienillä vaikeuseroilla on vähän turhaa. Jos tehtäviä on monta, pitäisi niiden vaikeustasot olla sen verran suuria, että olisi edes pieni mahdollisuus erojen syntymiseen ratkaisujen välillä. Nyt noissa tehtävissä on mielestäni vain yksi vaikeusporras: ensimmäisen (käsin ratkaistavan) ja loppujen välillä. Parin viimeisen tehtävän ratkaisussa saattaa kyllä tietyissä ratkaisuissa olla jotain pieniä muisti tai nopeusongelemia, mutta itse olisin mielellään nähnyt tehtävän, jossa lipun leveys olisi ollut 100008, jolloin olisi oikeasti joutunut miettimään parempaa ratkaisua. Toisaalta ymmärrän, että Antti ei voi laittaa haastetta, johon ei itsellä ei ole mallivastausta.
Toki monta samantasoista tehtävää varmistaa ratkaisujen oikeellisuuden, kuten tämänkin tehtävän ratkaisuista huomattiin (yllättäin alle puolella tehtävisssä oli merkitystä samanaikaisesti asetettavien palojen säännöllä).
Jaa-a, mikä lie FooBatin ratkaisu? Itselleni ei tullut mieleenkään lähteä tuohon muulla tavalla kuin sillä, että muistinkäyttö on vakio ja ajankäyttökin riippumaton lipun koosta (eli samat laskelmat ovat mahdollisia sekä isolla että pienellä lipulla). Ajanpuutteestahan se on kiinni, että en ole vielä ratkaisua saanut aikaiseksi; lähes puolet laskelmista on vielä tekemättä. Ylivoimaista ei olisi testisyötteitäkään laskea paperilla, ilman laskintakin onnistuisi.
Taulukon formaatti tuskin tekee monellekaan todellista ongelmaa. Itselläni ainakin onnistui muokkaus alle minuutissa: copy-pastella tuosta koko taulukko tekstieditoriin ja korvaustoiminnolla ja regexpeillä sopivaan muotoon. Ja helpostikos sitä tekee vaikka ohjelman, joka poistaa tekstistä kaikki paitsi välit ja numerot ja printtaa sitten numerot halutussa järjestyksessä pilkkujen ja muiden kanssa.
oma ratkaisuni käyttää muistia lipun koon verran (leveys*korkeus) plus jotain pientä, aikakompleksisuutta en jaksa nyt pohtia.
mutta jos tän lähtee ratkaisemman helpolla tavalla (voi tehdä vaikeankin joka ei käytä niin paljon muistia).
niin tulee aika nopeasti muistirajotus vastaan. itse sain ajettua omalla koneella noin 20000 palikan levyisiä lippuja, jolloin meni vain minuutti aikaa.
p.s. pitääpä kokeilla tehdä tämän ei niin muistisyöpöksi. se on hankalaa muttei mahdotonta
p.p.s. niin tai voi olla fiksu ja laskee geometrisesti jolloin ehkä saiskin vakioajan.
Minulla kesti 45s leveydeltään 20196 (3505,1824) (16662,8814) ratkaisemisessa. Enkä käytä ohjelmassani yhtään taulukoita ja muuttujia tarvitaan 6 kpl.
EDIT: Ihan pikkusella optimoinnilla sain ajan tiputettua 13s. AMD 2000+
Tehtävään pitäisi olla olemassa ainakin O(n3)-, O(n2)-, O(n)- ja O(1)-algoritmeja.
Tällä kertaa syötteet eivät vaadi tehokkainta algoritmia, mutta tietysti sitä voi koettaa miettiä siitä huolimatta. Jälkeenpäin ajateltuna tehtävässä olisi kyllä voinut olla pari suurempaa syötettä tähän kannustamiseksi.
Mutta FooBat on harmittavan oikeassa:
FooBat kirjoitti:
Toisaalta ymmärrän, että Antti ei voi laittaa haastetta, johon ei itsellä ei ole mallivastausta.
On totta, että syötteiden siirto omaan ohjelmaan käy varsinkin tässä tehtävässä työstä. Asiaan tulee parannus.
Metabolix kirjoitti:
Jaa-a, mikä lie FooBatin ratkaisu? Itselleni ei tullut mieleenkään lähteä tuohon muulla tavalla kuin sillä, että muistinkäyttö on vakio ja ajankäyttökin riippumaton lipun koosta (eli samat laskelmat ovat mahdollisia sekä isolla että pienellä lipulla).
Oma ratkaisuni on yksinkertainen haku lipun kokoisessa taulukossa. Tämä lähinnä siksi, että se oli yksinkertaisin ja nopein toteuttaa ja varsin riittävä halutuille tehtäville. Tätä koodatessa tuli kuitenkin jo mieleen, että nopeamman ratkaisun, joka toimisi vakiomuistisssa saisi helposti aikaan tarkastelemalla vain paloja, jotka ovat yhtä kaukana lähtöpisteistä. Ajatus 100008 kokoisen lipun taustalla onkin se, että muistipuskurissa tapahtuva haku ei enää olisi mielekäs, vaan pitäisi toteuttaa kehittyneenpi tapa.
Tällä kertaa menin siitä, missä aita on matalin. Puhtaasta bruteforcesta vain vähän kehittyneempi versio laski suurimman lipun 90 sekunnissa. Jälleen kerran kielenä oli Python ja koneena 700 MHz Athlon.
Aihe on jo aika vanha, joten et voi enää vastata siihen.