Kirjautuminen
Tehtävät
Kilpailu
3. kierros:
17.10. klo 18 – 19.10. klo 23
Putka Open 2025 kierros 2 alkaa pian:
https://cses.fi/putka-open-2025/
Kierros 2 alkaa pe 26.9. klo 18:00 ja päättyy su 28.9. 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!
A Ruudukko, C++ O(nm)
Kovakoodasin muutaman pienen tapauksen ja täytin muut tällaisella kuviolla:
1 17 2 18 3 19 4 5 20 6 21 7 22 8 9 23 10 24 11 25 12 13 26 14 27 15 28 16
B Leimasin, C++ O(n+m+k)
Muodostan ratkaisun vasemmalta oikealle merkki kerrallaan ja säilytän aktiivisia leimauksia jonossa.
C Alkuluvut, C++ O(t)
Erilaisia syötteitä on vain 1023, joten kaikki vastaukset voi laskea etukäteen ja kopioida lähdekoodiin. Generoin vastaukset käymällä alkulukuja läpi, kunnes uusia numeroyhdistelmiä ei enää tullut.
D Ryhmät, C++ O(n log n + sum(m) log n) tjsp
Tehtävä on minulle tutumpi eri tavalla muotoiltuna: k:n kokoinen ryhmä on työtehtävä, joka täytyy suorittaa ajanhetkellä k (ja vaatii k työntekijää). Lapsi on työntekijä, joka on käytettävissä korkeintaan yhteen työtehtävään aikavälillä L-R. Riittääkö kaikkiin työtehtäviin vaadittava määrä työntekijöitä?
(Sivuhuomio: ei ole oleellista, että ajanhetkellä k suoritettava työtehtävä sattuu vaatimaan tasan k työntekijää. Jos työtehtävät olisivat pareja (ajanhetki, tarvittava_työvoima), koodista ei tarvitsisi muuttaa muuta kuin syötteen lukeminen.)
Ratkaisuidea on ahne algoritmi. Työtehtävät käydään läpi nousevassa järjestyksessä k:n mukaan ja kuhunkin valitaan yhteensopivat työntekijät, joiden R on mahdollisimman pieni.
Jos testitapauksia olisi vain yksi eli t=1, voitaisiin käydä läpi kaikki työntekijät aikavaativuudella O(n log n). Testejä on kuitenkin useita ja syötteen kokoon sopiva aikavaativuus on O(m log n) per testi.
Tarvitaan tietorakenne, josta voi tarkistaa tehokkaasti, löytyykö annettuun työtehtävään riittävästi vapaita työntekijöitä. Minulle tuli ensimmäisenä mieleen persistentti segmenttipuu, jota olen tottunut käyttänyt samantapaisiin intervallikyselyihin.
Lisäys: Tavallinenkin segmenttipuu olisi näköjään riittänyt.
Itse kopioin ruudukossa kuvion 3 1 4 2 5 .. jos pituus > 3. Sama toistuu alaspäin lisättynä pituudella. Jos korkeus > 3 niin sama kuvio kääntäen pystyyn. Pienet ruudukot valmiiksi ratkaistuna.
---
Javalle pitäisi sallia kaksinkertainen ajankäyttö C:n suhteen, sillä se on puolet hitaampi. :(
TapaniS kirjoitti:
Javalle pitäisi sallia kaksinkertainen ajankäyttö C:n suhteen, sillä se on puolet hitaampi. :(
Kukin saa itse valita, mitä kieltä käyttää. Mutta omat ratkaisuni veivät 0.00s, 0.08s, 0.00s, 0.29s, joten ensimmäisissä tehtävissä edes 10x hitaampi kieli ei olisi haitannut.
Aikarajoissa on yleensä sen verran löysää, että suoraviivainen C++-toteutus oikeasta algoritmista ilman mitään erikoisia optimointeja vie korkeintaan 0.5s. Ainakin CSES:n ongelmakokoelmassa tämä pitää useimmissa tehtävissä paikkansa.
Kiinnitin tosin huomiota, että B-tehtävässä muutamassa 100 pisteen ratkaisussa on ylimääräinen logaritmikerroin ja ajoaika hyvin lähellä sekuntia. Javalla tämä ei välttämättä olisi onnistunut yhtä helposti.
TapaniS kirjoitti:
Javalle pitäisi sallia kaksinkertainen ajankäyttö C:n suhteen, sillä se on puolet hitaampi. :(
Tämä riippuu myös paljon siitä, millainen koodi on kyseessä. Testasin laskea alkulukujen määrän rajaan 107 asti C:llä ja Javalla:
#include <stdio.h>
#define N 10000000
int sieve[N+1];
int main(void) {
int count = 0;
for (int i = 2; i <= N; i++) {
if (sieve[i]) continue;
count++;
for (int j = 2*i; j <= N; j += i) {
sieve[j] = 1;
}
}
printf("%d\n", count);
return 0;
}public class Primes {
public static void main(String[] args) {
final int N = 10000000;
boolean[] sieve = new boolean[N+1];
int count = 0;
for (int i = 2; i <= N; i++) {
if (sieve[i]) continue;
count++;
for (int j = 2*i; j <= N; j += i) {
sieve[j] = true;
}
}
System.out.println(count);
}
}Omalla koneellani C-koodin suoritus vie aikaa 0.154 s mutta Java-koodin suoritus vie aikaa 0.092 s, eli tässä tapauksessa Java-koodi onkin nopeampi.
Yleisemmin oman kokemukseni perusteella Java-koodikin voi olla nopeaa, jos sen koodaa C-kielen tyylisesti ja erityisesti välttää olioiden käyttämistä (taulukkoa lukuun ottamatta).
Kierroksen 2 aikana yksi osallistuja sai C-tehtävässä CSES:ssä oudon virheilmoituksen INTERNAL ERROR. Tämä on ratkaisun arvosteluun liittyvä CSES:n sisäinen virhetilanne, jota ei tulisi tapahtua.
Syynä virheeseen oli, että tehtävän tarkastimessa käytetty alkulukutesti ylitti CSES:n sisäisen aikarajan, kun kilpailijan ratkaisu tuotti paljon suuria alkulukuja. Korjasin ongelman ottamalla käyttöön Laakerin Miller-Rabin-toteutuksen, jolla voi tarkastaa tehokkaasti mistä tahansa 64-bittisestä luvusta, onko se alkuluku.
Antti Laaksonen kirjoitti:
Omalla koneellani C-koodin suoritus vie aikaa 0.154 s mutta Java-koodin suoritus vie aikaa 0.092 s, eli tässä tapauksessa Java-koodi onkin nopeampi.
Jos vaihdat sieve-taulukon tyypiksi int8_t, onko Java edelleen nopeampi?
Käsittääkseni Javan boolean on yhden tavun kokoinen.
jlaire kirjoitti:
Jos vaihdat sieve-taulukon tyypiksi int8_t, onko Java edelleen nopeampi?
Hyvä kommentti, tällä muutoksella C-koodi vie aikaa vain 0.052 s. Testissä en koettanut erityisesti optimoida kumpaakaan toteutusta vaan kirjoitin luontevalta tuntuvan koodin molemmilla kielillä.
Hi, sorry for writing here in english. I have spend quite some time, unsuccessfully, trying to find a fast solution for task D. I am wondering if I maybe have a misunderstanding and someone here could help me clear it up.
This is a testcase I came up with with when thinking about the problem:
8 1 1 5 2 2 2 2 2 2 5 5 5 5 5 5 5 5 3 1 2 5
I expected the answer to be NO, as it is necessary to take the interval [1, 5] to form the group of size 1 and then it is not possible to form a group of size 5 anymore. However multiple codes that got 100pts output YES on this particular input.
Is the input maybe invalid in some way that I did not consider?
I think you're correct and the solutions printing YES are wrong.
When my solution is processing group 5, it only considers two questions:
1) How many intervals contain 5?
2) How many of these intervals were used in the previous group of size 2?
The fact that [1,5] was used in group 1 is forgotten.
This seems fixable without too big changes. I'll think about it later if I have time and I can write a more detailed explanation of the solution.
EDIT: After taking a look at the code, I actually did try to account for this. But something in the logic is wrong. Nice test case.
Thanks for checking, I thought I was loosing my mind :D
Voisiko joku 100 p henkilö, joka selviää myös antonH:n testitapauksesta (täydennettynä vielä toisella kyselyllä, jossa muodostetaan vain ryhmät 2 ja 5 ja vastaus on YES), selittää ratkaisunsa toiminnan selvästi, eli mitä puuhun tallennetaan ja miten sitä päivitetään? Tehtävä näytti siltä, että siinä pitäisi käyttää segmenttipuun tapaista rakennetta jotenkin, mutta juuri tuollaisen tapauksen takia en keksinyt, miten saisin segmenttipuulla oikean tuloksen, ja siksi en tehnyt segmenttipuuta käyttävää ratkaisua.
Edit. Ilmeisesti vain ArktinenKarpalo on ratkaissut tehtävän oikein, mutta hänen ratkaisunsa näihin isoihin tapauksiin onkin jotain aivan muuta kuin muilla. Kaikki muut 100 p ratkaisut antavat yllä olevasta tapauksesta väärän tuloksen. Ihmekös kun en niitä lukemalla ymmärtänyt ideaa.
Metabolix kirjoitti:
Ilmeisesti vain ArktinenKarpalo on ratkaissut tehtävän oikein
Sinänsähän tämän tyyppisissä kilpailussa jos on saanut täydet pisteet, niin on ratkaissu tehtävän "oikein". :p
Grez kirjoitti:
Sinänsähän tämän tyyppisissä kilpailussa jos on saanut täydet pisteet, niin on ratkaissu tehtävän "oikein".
Toki näinkin, toisaalta tehtävän laatijalla on jonkinlainen vastuu tuottaa kattava testiaineisto. Olisihan aika ikävää, jos vaikean tehtävän vastaukseksi riittäisi huonon aineiston takia vaikka puts("NO").
Tuotin nyt tehtävään ”tehokkaan ratkaisun”, joka perustuu jälkikäteen nähtäviin testidatan erityispiirteiden hyväksikäyttöön. Pohjalla on sinänsä oikea ratkaisu, jossa käydään läpi ryhmäkokoja järjestyksessä ja pidetään yllä jokaisen testitapauksen kohdalla joukkoa vapaista lapsista ja yhteisesti joukkoa nykyiseen ryhmäkokoon sopivista lapsista. Ratkaisu on aikavaativuudeltaan aivan liian hidas tavallisten joukkojen avulla, joten nopeutta on optimoitu 512 bitin pätkiin viipaloiduilla bittijoukoilla. Koska edes tämä ei riittänyt pariin testitapaukseen, alussa muodostetaan perinteinen summataulukko lasten määrästä joka ryhmäkoolla ja siivotaan tämän avulla pois ne triviaalit testitapaukset, joissa muodostetaan vain yhtä ryhmäkokoa.
https://cses.fi/595/result/14808541/
Viitsiikö Antti valaista, mitä ratkaisua tehtävässä haettiin?
Metabolix kirjoitti:
Voisiko joku 100 p henkilö, joka selviää myös antonH:n testitapauksesta (täydennettynä vielä toisella kyselyllä, jossa muodostetaan vain ryhmät 2 ja 5 ja vastaus on YES), selittää ratkaisunsa toiminnan selvästi, eli mitä puuhun tallennetaan ja miten sitä päivitetään?
Ilmeisesti minun ensimmäinen 100p ratkaisuni https://cses.fi/595/result/D/14689662/ käsittelee tuon tapauksen oikein.
Ratkaisussa on kaksi haaraa: yksinkertainen ratkaisu, joka ratkoo osatehtävät 1 ja 2, ja tämän optimoitu versio, joka ratkoo osatehtävän 3. Pelkkä optimoitu ratkaisu ei ratkaise osatehtävää 2, koska sen aikavaativuus riippuu m-arvojen summasta, joka on maksimissaan 10^5 osatehtävässä 3, mutta jopa 10^6 osatehtävässä 2. Tarkistin, että myös optimoitu ratkaisu ratkaisee tuon antonH:n tapauksen oikein.
Yksinkertaisessa ratkaisussa käydään ryhmäkoot k läpi suuruusjärjestyksessä, ja samalla täytetään toiveita (x, y) järjestettynä minimiryhmäkoon a mukaan. Apuna käytetään prioriteettijonoa, joka sisältää niiden toiveiden (x, y), joille pätee x <= k <= y, loppupäät y. Jokaista ryhmäkokoa k kohti poistetaan prioriteettijonosta k pienintä alkiota; jos ne loppuvat kesken, vastaus on NO, muuten se on YES.
Optimoidussa ratkaisussa käytetään hyödyksi 2D-segmenttipuurakennetta, jonka alkio (x, y) sisältää toiveiden (x, y) lukumäärän. Segmenttipuu tukee summakyselyitä mielivaltaisten suorakulmioiden [x_1, x_2] x [y_1, y_2] alueilta. Segmenttipuu rakennetaan aluksi, eikä sitä tarvitse muokata. Ratkaisun yksinkertaistamiseksi tehdään symbolinen perturbaatio, jonka takia voidaan olettaa, että millään kahdella toiveella ei ole samaa loppupäätä.
Optimoitu ratkaisu seuraa yksinkertaisen ratkaisun ideaa, mutta se välttää käsittelemästä jokaista lasta erikseen esittämällä prioriteettijonon yhdisteenä suorakulmion muotoisista alueista 2D-segmenttipuussa. Nämä suorakulmiot muodostavat aina porrasrakenteen: joillekin 0 = x_0 < x_1 < x_2 < ... < x_s ja y_1 > y_2 > ... > y_s prioriteettijono sisältää ne toiveet (x, y), jotka ovat suorakulmioissa ]x_(i-1), x_i] x [y_i, oo[ jollekin i.
Kun yksinkertaisessa ratkaisussa halutaan poistaa prioriteettijonosta tietty määrä pienimpiä alkioita, tässä suorakulmiohajotelmassa se toteutetaan kutistamalla suorakulmioita alhaalta siten, että summa pienenee halutun verran. Käytännössä siis suorakulmiot muodostavat pinon, ja ensimmäiseksi nakerretaan pinon viimeistä suorakulmiota ]x_(s-1), x_s] x [y_s, oo[; jos sen alaraja y_s nousee edellisen suorakulmion alarajan tasolle, suorakulmiot yhdistetään ja jatketaan kutistamista.
Kun siirrytään ryhmäkoosta k' seuraavaan suurempaan ryhmäkokoon k, yksinkertaisessa ratkaisussa prioriteettijonoon lisätään toiveet (x, y), joiden alkupäälle pätee k' < x <= k, ja tämän jälkeen poistetaan toiveet (x, y), joiden loppupäille pätee y < k. Suorakulmiopinossa tämä tarkoittaa uuden suorakulmion lisäämistä ja tämän jälkeen koko pinon kutistamista pohjalta niin, että y_i >= k kaikille i.
Kisassa minua jäi harmittamaan, että tämä optimoitu ratkaisu on aika hidas: sen aikavaativuus on tyyliin O(M log^3 n), missä M on m-arvojen summa. Luullakseni tämän voisi teoriassa optimoida O(M log^2 n):ksi, mutta kun yritin tehdä tämän käytännössä, ratkaisu muuttui hitaammaksi, koska jouduin muuttamaan binäärihakuja puurakenteiksi. Oli myös ikävää, että osatehtävä 2 vaati erillisen ratkaisun (kuten kommentista "// eispä epäeleganssi" käy ilmi). Siksi tein tuon lopullisen ratkaisuni, joka on ilmeisesti hyvin samanlainen kuin monilla muilla, ja pääsee läpi vain testien huonon peittävyyden takia. Ihmettelinkin, miksi jälkimmäinen ratkaisu vaikutti niin paljon helpommalta; olisi varmaan kannattanut tehdä testigeneraattori ja testata, että koodit tuottavat aina saman tuloksen.
Metabolix kirjoitti:
Viitsiikö Antti valaista, mitä ratkaisua tehtävässä haettiin?
Topi kuvasikin jo yhden lähestymistavan, jolla saa oikein toimivan ratkaisun. Muitakin ratkaisutapoja on olemassa ja tästä saa itse asiassa hyvän lisähaasteen: kuinka tehdä mahdollisimman yksinkertainen toimiva ratkaisu? Tässä keskustelussa on hyvä mahdollisuus esitellä eri ratkaisutapoja.
Olen pahoillani siitä, että tehtävän testiaineisto osoittautui puutteelliseksi. En ottanut huomioon tietynlaisia virheellisiä ratkaisuja testien suunnittelussa.
En ole toteuttanut, mutta uskoisin että O(M log n) ratkaisun saa aikaan persistentillä segmenttipuulla.
Ideana on korvata Topin 2D-segmenttipuu kasalla segmenttipuita S_t jokaiselle "ajanhetkelle" t. S_t:ssä on merkitty ykkösbitti kaikille toiveille (x, y), joilla x <= t. Indeksit on järjestetty y:n mukaan. Persistenttiys tarkoittaa, että ajanhetkien t ja t+1 välillä uusia solmuja luodaan vain muuttuneille kohdille ja muut säilytetään viittauksina vanhoihin solmuihin.
Summakyselyn [x_1, x_2] x [y_1, y_2] voi toteuttaa lukemalla erotusta S_{x_2} - S_{x_1 - 1}. Käytännössä tämä tapahtuu tavallisena segmenttipuun summakyselynä, mutta saadakseen solmun arvon laskemme aina erotuksen kahden segmenttipuun vastaavien solmujen välillä.
Toinen kysely, jota rakenteelle halutaan tehdä on "etsi pienin y, jolla summa [x_1, x_2] x [1, y] on vähintään z". (Siis pienin perturboitu y.) Tämän voi myös toteuttaa summasegmenttipuuta alaspäin etenemällä ajassa O(log n), ja se toimii yhtälailla "erotussegmenttipuussa".
Eräässä klassisessa CSES-tehtävässä käytetään samoja ideoita, mutta en nyt spoilaa sitä tässä :)
Onko kellään ratkaisuideaa, joka ei perustu ahneen algoritmin simulointiin?
ollpu kirjoitti:
Toinen kysely, jota rakenteelle halutaan tehdä on "etsi pienin y, jolla summa [x_1, x_2] x [1, y] on vähintään z". (Siis pienin perturboitu y.) Tämän voi myös toteuttaa summasegmenttipuuta alaspäin etenemällä ajassa O(log n), ja se toimii yhtälailla "erotussegmenttipuussa".
Olisiko tähän jotain tarkempaa vinkkiä vielä? En oikein saa päähäni miten haku toimii puiden erotuksessa.
Summakyselyn [x_1, x_2] x [y_1, y_2] optimointiin toinen tunnettu ratkaisu on aluepuu (range tree)+fractional cascading (miten se suomennetaan?). En kuitenkaan keksi miten siinäkään saisi toisen kyselyn O(log n)-ajassa.
Sisuaski kirjoitti:
Olisiko tähän jotain tarkempaa vinkkiä vielä? En oikein saa päähäni miten haku toimii puiden erotuksessa.
Tehdään kysely erotussegmenttipuulle S_A - S_B. Alustetaan c_A ja c_B puiden S_A ja S_B juuriksi. vas(x) ja oik(x) antavat solmun lapset ja sum(x) antaa välin summan. Muuttujassa h := 0 ylläpidetään vasemmalle jäävää prefiksisummaa. Väli [l, r] = [0, N-1] kertoo tämänhetkisen solmun välin (sama molemmissa puissa), ja tätä puolitetaan tavalliseen tapaan laskeuduttaessa.
Jos h + sum(vas(c_A)) - sum(vas(c_B)) <= z, laskeudutaan vasemmalle, eli c_A = vas(c_A), c_B = vas(c_B). Muutoin laskeudutaan oikealle: h += sum(vas(c_A)) - sum(vas(c_B)), c_A = oik(c_A), c_B = oik(c_B). Kun l = r, haluttu kohta on löytynyt.
Vähän abstraktimmassa mielessä, jos segmenttipuun solmulle on määritelty funktiot vas(x), oik(x) ja sum(x) ja ne toimivat järkevästi, voidaan toteuttaa mm. välisummakysely ja "pienin y, jolla välin summa [1, y] on vähintään z"-kysely. Erotussegmenttipuun solmua esitetään parilla (a, b), ja funktiot on määritelty vas((a, b)) = (vas(a), vas(b)), oik((a, b)) = (oik(a), oik(b)), sum((a, b)) = sum(a) - sum(b). Tästä on melko helppo nähdä, että sum() on hyvinmääritelty, eli sum(x) = sum(vas(x)) + sum(oik(x)).
Minusta näyttää, että tuo logiikka toimii vain jos erotuspuun arvot ovat ei-negatiivisiä. Muuten voi käydä niin että alipuun summa on liian pieni vaikka haettu summa löytyykin jostakin sen prefiksistä. Käytetäänkö tässä jotakin tietoa syötteestä, jolla ei-negatiivisuus varmistetaan?
Jos meillä olisi käytössä vain yksi erotuspuu, niin asian voisi kai korjata jotenkin niin että lasketaan joka solmulle suurin prefiksisumma
psum(c) = max(psum(vas(c)),sum(vas(c))+psum(oik(c)))
jota sitten käytetään haussa. Ongelma on että meidän pitää pystyä tekemään kyselyjä monien puuparien erotuksille, joten esilaskenta olisi työlästä.
Aivan, mietinkin että ehkä jotain muita ominaisuuksia tarvitaan, mutta tuo ei käynyt mielessä. Arvot on ei-negatiivisia, koska bittejä lisäillään puuhun ajan t kasvaessa, mutta ei koskaan poisteta. Kyselyissä x_2 >= x_1. Toiveiden ylärajat y otetaan huomioon eri tavalla, järjestyksen perusteella.
Kiitos, tämähän selvittääkin asian.
Koodailin ollpun esittämän O(m log n)-ratkaisun katsoen osittain mallia Sharphin koodista ja käyttäen aluepuuta (koska se tuntui hauskemmalta koodata kuin persistentti segmenttipuu): https://cses.fi/595/result/14824203/
Meni läpi kaikki tapaukset ilman minkään osatehtävän erikoistapauksia tai optimointeja, joskaan suoritusajoissa ei ole paljoa juhlimista. Jos jaksaa niin olisi hauska verrata miten vakiokertoimet muuttuisi persistentillä segmenttipuulla.