Viikko 12: TMC-tehtävät

Tehtävien deadline: ma 27.4. klo 01:59

Viikon aiheena on pienimmät virittävät puut ja union find. Pienimmän virittävän puun löydät esimerkiksi Kruskalin algoritmilla.

Tehtävä 1

Tehtäväsi on pitää kirjaa ystäväverkostosta, johon ilmestyy uusia suhteita.

Toteutus

Toteuta luokka Ystavat, joka tarjoaa seuraavat metodit:

• Ystavat(int n): konstruktorille annetaan henkilöiden määrä (kokonaisluku välillä 1..10⁵)
• void lisaaYstavyys(int a, int b): henkilöt a ja b ystävystyvät
• int suurinRyhma(): metodin tulee palauttaa, kuinka suuri on sillä hetkellä suurin ryhmä henkilöitä, jotka kytkeytyvät toisiinsa ystävyyssuhteiden välityksellä

Aluksi kukaan ei ole ystävä kenenkään kanssa. Testauksessa metodeita kutsutaan enintään 10⁵ kertaa.

Esimerkki

Seuraava koodi testaa luokkaa:

Ystavat y = new Ystavat(4);
System.out.println(y.suurinRyhma());
y.lisaaYstavyys(1, 2);
System.out.println(y.suurinRyhma());
y.lisaaYstavyys(3, 4);
System.out.println(y.suurinRyhma());
y.lisaaYstavyys(1, 4);
System.out.println(y.suurinRyhma());

Koodin tulisi tuottaa seuraava tuloste:

1
2
2
4

Tehtävä 2

Tieverkosto on päässyt huonoon kuntoon, ja se tulisi kunnostaa. Rahaa on kuitenkin vähän, eikä kaikkia teitä voi korjata. Tehtäväsi on etsiä sellainen joukko teitä, että minkä tahansa kahden kaupungin välillä pystyy kulkemaan vain korjattuja teitä ja kokonaiskustannus on mahdollisimman alhainen.

Toteutus

Toteuta seuraava metodi:

long kunnostus(int n, int[] mista, int[] minne, int[] hinta)

Parametri n on kaupunkien määrä, kokonaisluku välillä 1..10⁵. Kaupungit on numeroitu tuttuun tapaan kokonaisluvuin 1..n.

Taulukot mista, minne ja hinta kuvaavat tieverkoston tiet. Taulukko mista kertoo, mistä kaupungista tie alkaa, ja taulukko minne kertoo, mihin kaupunkiin tie päättyy. Kaikki tiet ovat kaksisuuntaisia, ja niiden määrä on välillä 0..10⁵. Lisäksi taulukko hinta kertoo, paljonko tien kunnostaminen maksaisi. Jokainen hinta on kokonaisluku välillä 1..10⁹.

Metodin tulee palauttaa pienin kokonaiskustannus, jolla teitä saadaan korjattua siinä määrin, että minkä tahansa kaupunkiparin välillä pääsee kulkemaan korjattujen teiden kautta.

Esimerkit

Tehtävä 3

Myös käännöstoimistossa joudutaan tekemään säästöjä. Tällä hetkellä palveluksessa on joukko kääntäjiä, joista jokainen kääntää kahden kielen välillä. Käännöstoimisto on siitä erikoinen, että jokainen kääntäjä pystyy kääntämään kahteen suuntaan (yleensä kääntäjät kääntävät vain äidinkielelleen). Osa kääntäjistä saattaa olla kuitenkin turhia.

Oletetaan esimerkiksi, että palveluksessa ovat seuraavat kääntäjät:

Nyt kääntäjä 1 kannattaa erottaa, koska käännöksen saksan ja suomen välillä voi tehdä myös halvemmin kiinan kautta kääntäjien 3 ja 4 avulla. Kääntäjä 2 taas on korvaamaton, koska kukaan muu ei osaa ruotsia, joten hänet on pakko säilyttää palveluksessa korkeasta palkasta huolimatta.

Toteutus

Toteuta seuraava metodi:

long kaannokset(String[] mista, String[] minne, int[] hinta)

Taulukot mista ja minne kertovat, minkä kieliparin välillä kukin kääntäjä pystyy kääntämään. Taulukko hinta kertoo, paljonko kääntäjälle täytyy maksaa palkkaa. Kääntäjien määrä on välillä 1..10⁵.

Metodin tulee palauttaa pienin kokonaiskustannus, jolla käännöstoimisto pystyy kääntämään edelleen kaikkien samojen kielten välillä kuin ennenkin.

Esimerkit

Tehtävä 4

Sinulle on annettu tiedot rautaverkostosta, joka muodostuu kaupungeista ja niiden välisistä radoista. Jokaisesta rataosuudesta tiedetään myös, mikä on maksimipaino siinä ajavalle junalle. Kuinka painavan junan voit hankkia, jos haluat pystyä matkustamaan sillä minkä tahansa kaupunkiparin välillä?

Toteutus

Toteuta seuraava metodi:

int suurinJuna(int n, int[] mista, int[] minne, int[] raja)

Parametri n on kaupunkien määrä, kokonaisluku välillä 1..10⁵. Kaupungit on numeroitu tavalliseen tapaan kokonaisluvuin 1..n.

Taulukot mista ja minne kuvaavat yhteydet kaupunkien välillä. Taulukko raja kertoo jokaisesta yhteydestä junan maksimipainon. Yhteyksien määrä on välillä 0..10⁵.

Metodin tulee palauttaa raskain juna, jolla pystyy ajamaan minkä tahansa kaupunkiparin välillä. Voit olettaa, että rataverkko kattaa kaikki kaupungit.

Esimerkit

Tehtävä 5

Jatkoa viikon 10 tehtävään 1:

Uolevin ystävät saattavat tutustua toisiinsa, mikä vaikeuttaa lahjojen jakamista. Tehtäväsi on pitää yllä tehokkaasti tietoa, voiko Uolevi jakaa lahjat haluamallaan tavalla.

Toteutus

Toteuta luokka Ystavat, joka tarjoaa seuraavat metodit:

• Ystavat(int n):
  konstruktorille annetaan Uolevin ystävien määrä (välillä 1..10⁵)
• void lisaaYstavyys(int a, int b):
  henkilöt a ja b tutustuvat toisiinsa
• boolean lahjajako():
  metodin tulee kertoa, onko tällä hetkellä mahdollista jakaa lahjat

Aluksi kukaan ei tunne vielä toisiaan. Testauksessa metodeita kutsutaan korkeintaan 10⁵ kertaa.

Esimerkki

Seuraava koodi testaa luokkaa:

Ystavat y = new Ystavat(3);
System.out.println(y.lahjajako());
y.lisaaYstavyys(1, 2);
System.out.println(y.lahjajako());
y.lisaaYstavyys(2, 3);
System.out.println(y.lahjajako());
y.lisaaYstavyys(1, 3);
System.out.println(y.lahjajako()); 

Koodin tulostuksen tulisi olla seuraava:

true
true
true
false