Keskustelu: Ohjelmointiputka: Putka Open 2020 kierros 4

Putka Open 2020 kierros 4 alkaa pian:

https://cses.fi/putka-open-2020/

Kierros 4 alkaa pe 6.11. klo 18:00 ja päättyy su 8.11. klo 23:00. Voit lähettää ratkaisuja milloin tahansa tällä aikavälillä.

Kierroksella on neljä tehtävää, jotka on jaettu osatehtäviin. Voit lähettää tehtäviin useita ratkaisuja ja paras ratkaisu jää voimaan.

Tuloslistalla järjestyksen määrittää tehtävien yhteispistemäärä. Jos kahdella osallistujalla on sama pistemäärä, ensin pistemäärän saavuttanut on parempi.

Tervetuloa kilpailuun!

Kierros on päättynyt. Tulokset löytyvät täältä: https://cses.fi/342/scores/

Seuraava eli viides kierros on 27.–29.11.

Tässä on jälleen eräitä ratkaisuja.

A, Neliöt

Kun n = a² + b², niin n - a² = b². Koska n on enintään miljardi, a ja b ovat alle 31623. Jokaisen syötteen kohdalla käydään läpi kaikki neliöt a² ja tarkastetaan, onko n - a² myös neliö. Itse laitoin neliöt Pythonin set-tietorakenteeseen, jolloin tarvitaan enää yksinkertainen silmukka ja ehtolause ratkaisuun.

B, Peli

Peli päättyy, kun toinen pelaaja saadaan ajettua päätyyn. Pelin voittaa se, joka saa siirrettyä pallot vierekkäin, koska silloin toisen pelaajan saa ajettua lopulta päätyyn, jossa ei ole mahdollista siirtoa. Huomataan, että pelin voittaja riippuu yksinkertaisesti siitä, onko pallojen etäisyys aluksi parillinen vai pariton.

C, Tekijät

Osatehtävä 1 ratkeaa käytännössä vaikka käymällä läpi kaikki lukuparit. Osatehtävä 2 ratkeaa, kun laskee taulukkoon kunkin luvun lukumäärän, jolloin eri lukupareja on jälleen hallittava määrä ja ne voi kaikki käydä läpi. Osatehtävä 3 onnistuu inkluusio–ekskluusio-tekniikkaa soveltamalla (ks. Kisakoodarin käsikirja) tai vastaavalla Möbius-funktiolla; asiaa on käsitelty englanniksi aivan vastaavan CodeChef-sivuston COPRIME3-tehtävän yhteydessä, ja onnekkaasti kyseisen sivun tiedot riittävät ratkaisun toteutukseen, vaikka ei jaksaisi perehtyä itse teoriaan.

D, Ruudukko

Osatehtävä 1 on helppo: jos päätyihin jää tyhjää tilaa, ratkaisua ei ole, ja muuten oikea ratkaisu on suora viiva.

Osatehtävä 2 on melko helppo: Kummastakin päätepisteestä vedetään lenkki yhteen päätyyn aluetta, ja sen jälkeen päät yritetään yhdistää sopivalla aaltoviivalla (esim. kirjainrivi URDR). Jos päät eivät osu yhteen, ratkaisua ei ole.

Osatehtävät 3 ja 4 ratkeavat luultavasti osatehtävä 2:n tyyliin, mutta päädyssä tehtävä lenkki on mutkikkaampi ja päiden sovittaminen yhteen on monimutkaisempaa. Kyllästyin itse erillisratkaisuihin enkä tehnyt näitä vaiheita.

Yleinen ratkaisu onnistuu ainakin seuraavasti rekursiolla: Jos alue on yli 5×5 ruutua, sitä voidaan ensin pienentää. Karsitaan alueen reunoilta kahden ruudun levyisiä tyhjiä suikaleita pois. Jos ei ole tyhjää, tiedetään, että alkupiste on 0–1 ruudun päässä alueen reunasta, ja voidaan vetää alkupisteestä sopiva S- tai C-muotoinen kiekura, jolla saadaan reunimmainen 2 ruudun suikale täytettyä eli alue pienenee taas. (Poikkeus: Jos alkupiste on kolmen levyisellä reunalla keskimmäisessä ruudussa, tehtävään ei ole ratkaisua.) Kun pienennystoimet johtavat enintään 5×5 ruudun alueeseen, haetaan loppuratkaisu yksinkertaisesti rekursiivisella syvyyshaulla ja lisätään sitten takaisin ne 2 ruudun suikaleet, jotka aiemmin karsittiin. Suikaleiden lisäys on jopa helppoa: alueen reunalla on taatusti jossain kohti suoraa viivaa, josta voidaan pyöräyttää ylimääräinen silmukka. (Poikkeus: Jos 2 ruudun sivulla sijaitsevat molemmat päätepisteet, niiden väliin ei jää viivaa. Onneksi nämä voi ratkaista erikseen osatehtävän 2 ratkaisulla.)

Alla on esimerkki tyhjän kaistaleen täytöstä ja alkupisteen siirrosta.

Tyhjän kaistaleen täyttö:
RRURRRU  <- ratkaistun alueen reuna
.......  <- tyhjää
.......  <- tyhjää
 =>
DRURRRU  <- ratkaisusta pitää päästä silmukkaan (ensimmäisen R:n sijaan D)
DULLLLL  <- silmukan viimeisestä kohdasta palataan ratkaisuun (L:n sijaan U)
RRRRRRU  <- alaosassa on siis silmukka RRRRRRULLLLLLD, joka yhdestä kohti liitetään

Alkupisteen siirto:
..a....  <- Alkupiste
.......  <- tyhjää
.......  <- tyhjää
 =>
DLLRRRD  <- kiekura
RRRUDLL  <- kiekura
....a..  <- Uusi alkupiste

Koodiin tarvitaan näistä tempuista useampia eri versioita. Suuntien ja alueiden kokojen kanssa saa olla tarkkana. Pikkuvirheitä debuggaillessa tuli eräs kuuluisa netin muumivideo mieleen.

Hienoja tehtäviä oli löytynyt tälle kierrokselle! Tuo peli näytti aika pahalta, mutta parin manuaalisen demo-harjoittelun jälkeen avautui mukavasti.

Maksimissa (4x400) enää kolme kisaajaa: Laakeri, Metabolix ja ollpu.

Epävirallisten laskujeni mukaan 19 kisaajaa on osallistunut kaikille kierroksille.

Minusta tuo tehtävä neliöt menee kivuttomasti myös seuraavalla lauseella: Positiivinen kokonaisluku n on kahden neliön summa, jos ja vain jos n=ab^2, missä a ja b ovat positiivisia kokonaislukuja ja a:lla ei ole alkutekijää muotoa p=3 mod 4. Todistus osoitteessa http://math.uga.edu/~pete/4400twosquares.pdf .

Voitko Jaska näyttää, miten tekisit tehtävän tuolla lauseella kätevästi? Neliöt on nopeaa laskea ja tarkastaa, kun taas alkutekijöiden selvittäminen on yleensä selvästi hitaampaa.

Tekijät voi käydä läpi yksinkertaisella silmukalla neliöjuureen asti. https://cses.fi/342/result/A/1225883/

Metabolix kirjoitti:

Voitko Jaska näyttää, miten tekisit tehtävän tuolla lauseella kätevästi? Neliöt on nopeaa laskea ja tarkastaa, kun taas alkutekijöiden selvittäminen on yleensä selvästi hitaampaa.

Koodi on sivulla https://www.geeksforgeeks.org/check-whether-number-can-represented-sum-two-squares/ .

Aivan, en ajatellut, että voi vain jakaa tekijöihin alkuperäisen luvun, jolloin neliöön sisältyvät ne tekijät, joita on parillinen määrä, ja loppujen pitäisi täyttää tämä ehto 3 != p mod 4. Onneksi tehtävässä lukuja oli niin vähän, että ei tarvinnut tietää tuollaista kaavaa.