Keskustelu: Ohjelmointiputka: Putka Open 2025 kierros 5

Putka Open 2025 kierros 5 alkaa pian:

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

Kierros 5 alkaa pe 28.11. klo 18:00 ja päättyy su 30.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!

Hienoja tehtäviä.

A, Lukujono. Jos X MOD 3 = 2, tästä muodostuva 2*X+1 MOD 3 = 2 ja tällöin lukujono ei ratkea. (Tämä pitää tarkistaa joka askeleella, koska tähän tilaan voidaan päätyä myös jakolaskun tuloksena.) Ellei päädytä tuohon tilaan, lukujono pienenee nopeasti ja sen pituuden voi vain laskea silmukassa.

B, Ruudukko. Sen sijaan, että tehtäisiin muutokset ruudukkoon koko alueelle, riittää merkitä ruudukkoon muutosalueiden kulmat. Aina kun ylitetään muutoksen reuna, pitää vaihtaa tulostettavaa merkkiä. (Kaksi päällekkäistä reunaa kumoavat toisensa, joten reunat kannattaa alunperinkin merkitä XORilla, jotta joka ruudussa on 0 tai 1.) Näin jokaisen rivin voi tuottaa järjestyksessä. Edellisen rivin reunat voi XORilla liittää seuraavalle riville, ja muutosalueen alareunassa on taas uudet ykköset, jotka kumoavat tämän XORin.

        | t[r]    | t[r][i]   |
        | XOR     | XOR       |
kulmat  | t[r-1]  | t[r][i-1] | tulos
....... | ....... | 0------   | .......
..1..1. | ..1..1. | 0-1--0-   | ..###..
....... | ..1..1. | 0-1--0-   | ..###..
....... | ..1..1. | 0-1--0-   | ..###..
..1..1. | ..0..0. | 0------   | .......
....... | ....... | 0------   | .......

C, Lisäykset. Nopeaan ratkaisuun auttaa kaksi kikkaa. Ensinnäkin ryhmitellään samanarvoiset luvut tietueiksi, joissa on alkukohta ja määrä. Tällöin suurempi määrä lukuja voidaan muuttaa vain yhtä tietuetta muuttamalla. Jos muutosalue päättyy keskellä tietuetta, tietuetta pitää pienentää sopivasti ja korotetut luvut pitää lisätä sen perään. Peräkkäiset yhtäsuuret alueet (joita voi olla enintään 1 ennen ja 1 jälkeen muutoskohdan) kannattaa taas yhdistää toisiinsa, jotta myöhemmät samanarvoisten halkaisut toimivat oikein. Toinen nopeutus on, että tietueissa ei ilmoiteta absoluuttista lukuarvoa vaan korotus verrattuna edelliseen tietueeseen. Tällöin muutosalueen sisällä olevia tietueita ei tarvitse muokata ollenkaan, vaan riittää, että muutoksen alkuun merkitään +1 ja alkuun -1.

D, Yhdistelmät. Tapaus n <= 20 ratkeaa voimalla, koska eri kombinaatioita on vain miljoona ja toteutuvat yhdistelmät on nopea tarkistaa, kun ne ilmaisee bittijoukkoina. Tapaus d = 1 (eli yhdistelmässä on vain yksi esine) ratkeaa triviaalisti, koska jokainen esine voidaan käsitellä erikseen ja sen palkkio joko ylittää hinnan tai sitten ei. Tapaus d=2 ratkeaa näköjään tuurilla sisäkkäisiä silmukoita sekoittamalla, minkä tein nyt aiemmasta kierroksesta oppineena, kun en keksinyt oikeaa ratkaisua. Yleinen tapaus on näköjään ratkennut monella yllättävän helposti ja joku voi varmaan selittää, miten se ratkeaa noin helposti.

D ratkeaa maksimivirtauksella. Muodostetaan virtausverkko, jossa on solmut kaikille esineille ja yhdistelmille, ja seuraavat kaaret:
- Lähtösolmusta kaari jokaiseen yhdistelmään, kapasiteetti=yhdistelmän arvo.
- Jokaisesta esineestä kaari loppusolmuun, kapasiteetti=esineen hinta.
- Jokaisesta yhdistelmästä kaaret siihen kuuluviin esineisiin, kapasiteetti=ääretön.

Virtauksesta saatavan minimileikkauksen voi tulkita ratkaisuna niin, että ostetaan kaikki esineet joiden kaari loppusolmuun kuuluu leikkaukseen. Intuitiivisesti tämä tarkoittaa, että esineen hinta on pienempi kuin sen tuoma arvo yhdistelmiin. Ratkaisun arvo saadaan laskettua erotuksena (kaikkien yhdistelmien arvot)-(virtaus)=(jäännösverkon kapasiteetit alkusolmusta).

Näin saatava ratkaisu on optimaalinen, koska minkä tahansa ratkaisun perusteella voi muodostaa virtausverkon leikkauksen: Jokaisen esineen kohdalla joko ostetaan esine (eli leikataan esine-loppusolmu) tai sitten jätetään saamatta sen sisältämät yhdistelmät (eli leikataan alkusolmu-yhdistelmät). Koska jokaisen ratkaisun voi kuvata leikkauksena ja vastaus on sitä parempi mitä pienempi leikkaus, antaa minimileikkaus parhaan mahdollisen ratkaisun.

D. Suhteessa ihannetilanteeseen (jossa saadaan kaikki palkinnot ostamatta mitään esinettä) tulee kahdenlaisia tappioita: joistakin esineistä maksetaan ja joitakin palkintoja ei saada. Tämä tappio halutaan minimoida. Halutaan jotenkin mallintaa sitä, että palkinnon saaminen pakottaa esineiden oston.

Tehdään virtauslaskentainstanssi, jossa jokaisesta palkinnosta on kaari palkintoon liittyviin esineisiin rajattomalla kapasiteetilla. Alkusolmusta menee kaaret palkintoihin palkinnon suuruutta vastaavalla kapasiteetilla. Lopuksi lisätään esineistä kaaret loppusolmuun hintaa vastaavalla kapasiteetilla. Jos alku- ja loppusolmu halutaan erottaa toisistaan, on poistettava jokin joukko kaaria, ja jos palkintoon menevää kaarta ei poisteta, on poistettava kaikkien siihen liittyvien esineiden loppusolmuun menevät kaaret (koska palkinnoista esineisiin olevissa kaarissa on rajaton kapasiteetti). Ongelma palautuu edeltävän kuvauksen perusteella minimileikkaukseen, joka ratkeaa maksimivirtauksella.

En keksinyt D:hen tuota virtausverkkoratkaisua, mutta onneksi syöte oli armollisen pieni ja lineaarinen optimointikin toimi riittävän nopeasti.

Yhdistelmille on muuttujat 0≤y_i, i=1..m ja esineille muuttujat 0≤e_j≤1, j=1..n. Lisäksi on rajoite y_i≤e_j jos yhdistelmä i sisältää esineen j.

Maksimoidaan palkkioiden ja hintojen erotus eli sum_i(y_ix_i) - sum_j(e_jp_j).

Jotta vastauksessa olisi ainoastaan kokonaislukuja, vähensin jokaisesta hinnasta p_j epsilonin verran alennusta.

C-ongelmassa on mielenkiintoista, että operaatiot voi järjestää vaikuttamatta lopputulokseen. Tätä havaintoa käyttämällä tehtävän voi ratkaista halutessaan lineaarisessa ajassa.

Kiitokset kaikille osallistujille ja laitoin äsken sähköpostitse tietoa top 10:lle t-paidoista ja loppukilpailusta.

jhuun, tiedossani ei ole tapaa saada sinuun yhteyttä. Voit lähettää viestin osoitteeseen ahslaaks@cs.helsinki.fi ja lähetän viestin myös sinulle.

Hei Antti ja kiitos loistavasta kisasta! Tällä tunnuksella on ajantasainen sähköpostiosoite, saisitkohan sen tätä kautta? T: jhuun

Hyvä, löytyi osoite ja välitin viestin sinulle.