Keskustelu: Ohjelmointiputka: Putka Open 2025 kierros 2

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 10⁷ 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ä.