viikko12.html

---
layout: material
title: Viikko 12
---
<p>Viikon aiheena on pienimmät virittävät puut ja union find. Pienimmän virittävän puun löydät esimerkiksi Kruskalin algoritmilla.</p>
<div class="exercise" id="t1">

	<header>
		<h1>Tehtävä 1</h1>
	</header>

	<div>
		<p>Tehtäväsi on pitää kirjaa ystäväverkostosta, johon ilmestyy uusia suhteita.</p>

		<h2>Toteutus</h2>

		<p>Toteuta luokka <code>Ystavat</code>, joka tarjoaa seuraavat metodit:</p>

		<ul class="compact">
			<li>
				<code>Ystavat(int n)</code>: konstruktorille annetaan henkilöiden määrä (kokonaisluku välillä 1..10<sup>5</sup>)
			</li>
			<li>
				<code>void lisaaYstavyys(int a, int b)</code>: henkilöt <em>a</em> ja <em>b</em> ystävystyvät
			</li>
			<li>
				<code>int suurinRyhma()</code>: metodin tulee palauttaa, kuinka suuri on sillä hetkellä suurin ryhmä henkilöitä, jotka kytkeytyvät toisiinsa ystävyyssuhteiden välityksellä
			</li>
		</ul>

		<p>
			Aluksi kukaan ei ole ystävä kenenkään kanssa. Testauksessa metodeita kutsutaan enintään 10<sup>5</sup> kertaa.
		</p>

		<h2>Esimerkit</h2>

		<p>Seuraava koodi testaa luokkaa:</p>
		{% highlight java %}
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());
		{% endhighlight %}
		<p>Koodin tulostuksen tulisi olla seuraava:</p>
		{% highlight text %}
1
2
2
4
		{% endhighlight %}
	</div>
</div>
<div class="exercise" id="t2">

	<header>
		<h1>Tehtävä 2</h1>
	</header>

	<div>

		<p>
			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.
		</p>

		<h2>Toteutus</h2>

		<p>
			Toteuta metodi:
			<code>long kunnostus(int n, int[] mista, int[] minne, int[] hinta)</code>
		</p>

		<p>
			Parametri <code>n</code> on kaupunkien määrä, kokonaisluku välillä 1..10<sup>5</sup>. Kaupungit on numeroitu tuttuun tapaan kokonaisluvuin 1..n.
		</p>

		<p>
			Taulukot <code>mista</code>, <code>minne</code> ja <code>hinta</code> kuvaavat tieverkoston tiet. Taulukko <code>mista</code> kertoo, mistä kaupungista tie alkaa, ja taulukko <code>minne</code> kertoo, mihin kaupunkiin tie päättyy. Kaikki tiet ovat kaksisuuntaisia, ja niiden määrä on välillä 0..10<sup>5</sup>. Lisäksi taulukko <code>hinta</code> kertoo, paljonko tien kunnostaminen maksaisi. Jokainen <code>hinta</code> on kokonaisluku välillä 1..10<sup>9</sup>.
		</p>
		<p>
			Metodin tulee palauttaa pienin kokonaiskustannus, jolla teitä saadaan korjattua siinä määrin, että minkä tahansa kaupunkiparin välillä pääsee kulkemaan korjattujen teiden kautta.
		</p>

		<h2>Esimerkit</h2>

		<table>
			<thead>
				<tr>
					<th>#</th>
					<th>metodin kutsu</th>
					<th>haluttu palautusarvo</th>
				</tr>
			</thead>
			<tbody>
				<tr>
					<td>1</td>
					<td>
						<code>kunnostus(3, new int[] {1, 2}, new int[] {2, 3}, new int[] {7, 4})</code>
					</td>
					<td>
						<code>11</code>
					</td>
				</tr>
				<tr>
					<td>2</td>
					<td>
						<code>kunnostus(3, new int[] {1, 2, 1}, new int[] {2, 3, 3}, new int[] {7, 4, 5})</code>
					</td>
					<td>
						<code>9</code>
					</td>
				</tr>
				<tr>
					<td>3</td>
					<td>
						<code>kunnostus(3, new int[] {1, 2, 1}, new int[] {2, 3, 3}, new int[] {2, 2, 2})</code>
					</td>
					<td>
						<code>4</code>
					</td>
				</tr>
			</tbody>
		</table>
	</div>
</div>
<div class="exercise" id="t3">

	<header>
		<h1>Tehtävä 3</h1>
	</header>

	<div>

		<p>
			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.
		</p>

		<p>
			Oletetaan esimerkiksi, että palveluksessa ovat seuraavat kääntäjät:
		</p>

		<table>
			<thead>
				<tr>
					<th>kääntäjä</th>
					<th>kielipari</th>
					<th>palkka</th>
				</tr>
			</thead>
			<tbody>
				
				<tr>
					<td>1</td>
					<td>saksa–suomi</td>
					<td>5000</td>
				</tr>
				<tr>
					<td>2</td>
					<td>ruotsi–suomi</td>
					<td>9000</td>
				</tr>
				<tr>
					<td>3</td>
					<td>kiina–saksa</td>
					<td>2500</td>
				</tr>
				<tr>
					<td>4</td>
					<td>suomi–kiina</td>
					<td>2000</td>
				</tr>
			</tbody>
		</table>

		<p>
			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.
		</p>

		<h2>Toteutus</h2>

		<p>
			Toteuta metodi:
			<code>long kaannokset(String[] mista, String[] minne, int[] hinta)</code>
		</p>

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

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

		<h2>Esimerkit</h2>

		<table>
			<thead>
				<tr>
					<th>#</th>
					<th>metodin kutsu</th>
					<th>haluttu palautusarvo</th>
				</tr>
			</thead>
			<tbody>
				<tr>
					<td>1</td>
					<td>
						<code>kaannokset(new String[] {"suomi", "ruotsi"}, new String[] {"ruotsi", "englanti"}, new int[] {7, 4}</code>
					</td>
					<td>
						<code>11</code>
					</td>
				</tr>
				<tr>
					<td>2</td>
					<td>
						<code>kaannokset(new String[] {"suomi", "ruotsi"}, new String[] {"saksa", "englanti"}, new int[] {5, 5}</code>
					</td>
					<td>
						<code>10</code>
					</td>
				</tr>
				<tr>
					<td>3</td>
					<td>
						<code>kaannokset(new String[] {"suomi", "ruotsi", "suomi"}, new String[] {"ruotsi", "englanti", "englanti"}, new int[] {7, 4, 5}</code>
					</td>
					<td>
						<code>9</code>
					</td>
				</tr>
				<tr>
					<td>4</td>
					<td>
						<code>kaannokset(new String[] {"suomi", "suomi"}, new String[] {"ruotsi", "ruotsi"}, new int[] {2, 3}</code>
					</td>
					<td>
						<code>2</code>
					</td>
				</tr>
			</tbody>
		</table>
	</div>
</div>
<div class="exercise" id="t4">

	<header>
		<h1>Tehtävä 4</h1>
	</header>

	<div>

		<p>
			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ä?
		</p>

		<h2>Toteutus</h2>

		<p>
			Toteuta metodi:
			<code>int suurinJuna(int n, int[] mista, int[] minne, int[] raja)</code>
		</p>

		<p>
			Parametri <code>n</code> on kaupunkien määrä, kokonaisluku välillä 1..10<sup>5</sup>. Kaupungit on numeroitu tavalliseen tapaan kokonaisluvuin 1..n.
		</p>
		<p>
			Taulukot <code>mista</code> ja <code>minne</code> kuvaavat yhteydet kaupunkien välillä. Taulukko <code>raja</code> kertoo jokaisesta yhteydestä junan maksimipainon. Yhteyksien määrä on välillä 0..10<sup>5</sup>.
		</p>
		<p>
			Metodin tulee palauttaa raskain juna, jolla pystyy ajamaan minkä tahansa kaupunkiparin välillä. Voit olettaa, että rataverkko kattaa kaikki kaupungit.
		</p>
		<h2>Esimerkit</h2>

		<table>
			<thead>
				<tr>
					<th>#</th>
					<th>metodin kutsu</th>
					<th>haluttu palautusarvo</th>
				</tr>
			</thead>
			<tbody>
				<tr>
					<td>1</td>
					<td>
						<code>suurinJuna(3, new int[] {1, 2}, new int[] {2, 3}, new int[] {7, 4})</code>
					</td>
					<td>
						<code>4</code>
					</td>
				</tr>
				<tr>
					<td>2</td>
					<td>
						<code>suurinJuna(3, new int[] {1, 2}, new int[] {2, 3}, new int[] {2, 2})</code>
					</td>
					<td>
						<code>2</code>
					</td>
				</tr>
				<tr>
					<td>3</td>
					<td>
						<code>suurinJuna(3, new int[] {1, 2, 1}, new int[] {2, 3, 3}, new int[] {7, 4, 5})</code>
					</td>
					<td>
						<code>5</code>
					</td>
				</tr>
			</tbody>
		</table>
	</div>
</div>
<div class="exercise" id="t5">

	<header>
		<h1>Tehtävä 5</h1>
	</header>

	<div>

		<p>
			Jatkoa viikon 10 tehtävään 1:
		</p>

		<p>
			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.
		</p>

		<h2>Toteutus</h2>

		<p>Toteuta luokka <code>Ystavat</code>, joka tarjoaa seuraavat metodit:</p>

		<ul class="compact">
			<li>
				<code>Ystavat(int n)</code>: konstruktorille annetaan Uolevin ystävien määrä (välillä 1..10<sup>5</sup>)
			</li>
			<li>
				<code>void lisaaYstavyys(int a, int b)</code>: henkilöt a ja b tutustuvat toisiinsa</li>
			<li>
				<code>boolean lahjajako()</code>: metodin tulee kertoa, onko tällä hetkellä mahdollista jakaa lahjat
			</li>
		</ul>
		<p>
			Aluksi kukaan ei tunne vielä toisiaan. Testauksessa metodeita kutsutaan korkeintaan 10<sup>5</sup> kertaa.
		</p>
		<h2>Esimerkit</h2>

		<p>Seuraava koodi testaa luokkaa:</p>
		{% highlight java %}
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()); 
		{% endhighlight %}
		<p>Koodin tulostuksen tulisi olla seuraava:</p>
		{% highlight text %}
true
true
true
false
		{% endhighlight %}
	</div>
</div>