Op 25 maart 2000 is op de universiteiten van Delft en Twente de tweede ronde van de Nederlandse Informatica Olympiade gehouden. In totaal 41 leerlingen hebben zich gebogen over twee opgaven, waarbij in totaal één tekstbestand en 12 programma’s geschreven dienden te worden. Deze 41 leerlingen bestonden uit 2 leerlingen die zich in vorige jaren al geplaatst hadden voor de derde ronde, 3 meisjes en 36 jongens voor de tweede ronde. In dit juryrapport wordt een verslag gegeven van de prestaties van al deze 41 deelnemers; bij de uitslag worden alleen de tweede ronde deelnemers genoemd, omdat de eerste tien daarvan zich plaatsen voor de scholing ter voorbereiding op de derde ronde.

Ten opzichte van de versie die je thuis hebt ontvangen zijn de scores van Roland Veen en Jelmer Vernooij aangepast; deze veranderingen zijn niet in de grafieken en gemiddeldes verwerkt.

Compensatie.

Na afloop van de wedstrijd bleken twee verschillende draaiboeken te zijn gebruikt, met als gevolg dat leerlingen in Delft vier uur de tijd hebben gehad en leerlingen in Twente vijf uur. De jury heeft besloten aan leerlingen uit Delft 20 % van hun score extra toe te kennen om dit verschil te compenseren. Deze compensatiepunten zijn verrekend in de einduitslag, niet in de score per onderdeel.

Minpunten.

Leerlingen die verkeerde bestandsnamen hebben gebruikt of hun programma’s niet of verkeerd hadden gecompileerd hebben per onderdeel waarbij de jury moest ingrijpen één punt in mindering gekregen; ook deze minpunten zijn niet in de score per onderdeel verrekend.

Gemiddelde score van alle deelnemers: 64,28 punten (maximaal 200)

Beste meisje uit de tweede ronde is Danny Oude Bos met 48 punten.

Het ging om twee omvangrijke opgaven, met veel onderdelen. Het is nooit de bedoeling geweest dat iemand alle onderdelen binnen de tijd af zou kunnen hebben; het inschatten van je eigen mogelijkheden binnen de wedstrijdtijd is nadrukkelijk onderdeel van die wedstrijd.

Bij deze opgave werden een aantal uiteenlopende zaken gevraagd bij een invoerbestand met kaarten voor een spelletje eenendertigen. De eerste twee onderdelen gingen over het lezen van de invoer, de volgende twee over het gebruik van de puntentelling en de laatste twee over het werkelijk spelen van het spel. Dat laatste bleek erg lastig.

Uit de invoer moest het aantal deelnemers worden bepaald. Dat kon je doen door het aantal kaarten te delen door drie, en dat resultaat één te verkleinen (de pot kreeg ook drie kaarten). Ook kon je het aantal symbolen uit de invoer delen door zes en dat resultaat één verkleinen.

Gemiddelde score: 8,83 punten (maximaal 10)

Om te bepalen welke kaarten niet meedoen tijdens een spelletje heb je een lijstje met alle kaarten nodig, waarin je de kaarten uit de invoer wegstreept.

Gemiddelde score: 7,71 punten (maximaal 10)

Hier moesten de punten van alle deelnemers worden geteld. Niet die van de pot geven dus! Een speler met drie kaarten van verschillende soorten krijgt toch al punten, bijvoorbeeld met schoppen 9, harten 8 en ruiten 7 kom je op 9 punten. Ook het geval van drie kaarten van gelijke hoogte (30.5) moest apart worden onderzocht!

Gemiddelde score: 9,96 punten (maximaal 15)

Ook bij het zoeken naar een combinatie van drie kaarten die de hoogst mogelijke score opleveren moest je er aan denken de mogelijkheid van 30.5 apart te onderzoeken.

Gemiddelde score: 10,93 punten (maximaal 20)

Deelnemers met 20 punten voor deze opgave:

Maks Verver (derde ronde), Johan de Ruiter, Joost Verhoog, Jappie Hoekstra, Bob Eldering, Jaap Taal, René Mulder, Berteun Damman, Maarten Löffler, Roland Veen, Jelmer Vernooij en Sander Agricola.

De reconstructie van een spel volgens de gegeven "gretige" speelwijze bleek zeer lastig. Vooral de voorwaarde dat het spel is afgelopen zodra één of meer spelers 31 punten hebben bleek vaak niet te zijn ingebouwd. Ook de deelnemers die alle spelers lieten passen konden bij deze opgave niet op punten rekenen.

Gemiddelde score: 0,15 punten (maximaal 24)

Alleen Jaap Taal behaalde 6 punten voor deze opgave.

Er zijn voor dit onderdeel geen punten gehaald. Voor de hand ligt een "breedte-eerst" zoekalgoritme, waarbij je alle mogelijke zetten bekijkt, totdat de ideale score behaald is. Dat kan echter nogal lang gaan duren, omdat je per keer 10 mogelijke zetten moet onderzoeken (drie kaarten die je elk voor drie andere kaarten kunt omruilen of passen). Een alternatief is het zoeken van de kaarten die samen die ideale score opleveren; voor elk van de mogelijke verdelingen is het gemakkelijk een scenario te bedenken dat tot de snelste oplossing leidt. Als speler A, speler B en de pot elk een kaart van de ideale combinatie hebben is de snelste route naar de beste score dat A een andere kaart met de goede kaart uit de pot ruilt, vervolgens B zijn goede kaart met een andere uit de pot omruilt, alle eventuele anderen passen en tenslotte A de laatste goede kaart uit de pot haalt. Het meest ongunstige geval is dat de drie kaarten in de pot juist tot de hoogste score leiden; in dat geval zal speler A in het derde rondje de laatste goede kaart pakken, waarbij je er op moet letten dat niet alle andere spelers in de eerste ronde al passen. Omdat er vaak meer combinaties tot de hoogste score leiden kun je voor elk van die combinaties uitrekenen hoe lang het spel duurt voordat de kaarten bij één speler kunnen zijn, en zo de snelste manier uitzoeken.

Beste scores opgave 1.

Jaap Taal 61

Maks Verver (derde ronde),

Maarten Löffler,

Berteun Damman,

Johan de Ruiter,

Jelmer Vernooij,

Bob Eldering 55

Roland Veen en

Jappie Hoekstra 52

Gerard Hoeberigs,

Wilmer van der Gaast,

Lourens Veen,

Bram Kuyvenhoven,

Sander Agricola 51

Gemiddelde score opgave 1: 37,58 punten (maximaal 100)

Gegeven was een tekst, opgebouwd uit maximaal 28 symbolen (letters, spaties en punten). Het tellen van letters in zo’n gegevens tekst bleek nog wel goed te doen. Het genereren van teksten op basis van het aangegeven voorschrift was heel lastig. Ook zorgden de grote invoerbestanden soms voor tijd- en geheugenproblemen. Het opdelen van de invoer in 3-grammen bracht ook veel problemen met zich mee, zeker ook omdat je de lijst met mogelijke 3-grammen netjes moet bijhouden.

De bedoeling van dit onderdeel was het tellen van de symbolen in de tekst; regelovergangen e.d. en het getal dat aangaf hoeveel regels er zouden volgen tellen daarbij niet mee.

Gemiddelde score: 5,17 punten (maximaal 8)

Dit onderdeel had een vergelijkbare moeilijkheidsgraad; ditmaal moesten de 28 symbolen worden geturfd en op volgorde dienden de frequenties te worden uitgevoerd.

Gemiddelde score: 7,68 punten (maximaal 12)

Veel deelnemers vonden de tekst van de opgave en de tabel van het voorbeeld erg lastig te lezen. Ook dat je bij gelijke frequentie moest kiezen voor het eerst mogelijke symbool kwam er niet altijd uit.

Gemiddelde score: 3,54 punten (maximaal 20 punten)

Tijmen Tieleman,

Lourens Veen,

Jaap Taal,

Maarten Löffler en

Bram Kuyvenhoven 20

Wilmer van der Gaast,

Johan de Ruiter,

Berteun Damman en

Maks Verver (derde ronde) 10

Sander Agricola 5

Allereerst was het een probleem alle 3-grammen in een tabel onder te brengen en te turven. Vervolgens moest voor ieder symbool worden bekeken in welk driegram dat symbool het vaakst voorkwam. Aan het voorbeeld was al te zien dat als een symbool niet voorkwam zoals de "y", dat je dan "aay 0" moest uitvoeren. Het kiezen van het eerste 3-gram uit de alfabetische ordening bleek nog een probleem op zich.

Gemiddelde score: 1,95 punten (maximaal 16 punten)

Wilmer van der Gaast,

Roland Veen,

Berteun Damman en

Lourens Veen 16

Bram Kuyvenhoven 12

Johan de Ruiter en

Maks Verver (derde ronde) 8

Vincent Groenhuis (derde ronde) 4

Gemiddelde score: 2,78 punten (maximaal 12 punten)

Wilmer van der Gaast,

Roland Veen,

Lourens Veen,

Berteun Damman,

Nick Matthijssen en

Jappie Hoekstra 12

Bram Kuyvenhoven 9

Vincent Groenhuis (derde ronde),

Maks Verver (derde ronde),

Johan de Ruiter en

Maarten Löffler 6

Danny Oude Bos,

Robert van Harten en

Bouke van Meeteren 3

Ook dit onderdeel leverde niemand punten op. Het is van belang je te bedenken dat in iedere situatie er al een begin is van het volgende 3-gram, namelijk de laatste twee symbolen van de gemaakte tekst. Je kunt dus kiezen uit 28 mogelijke 3-grammen, en alleen over die 28 hoef je te kijken hoe het is met de verschillen tussen de relatieve frequenties ervan in het origineel en de nu gemaakte tekst. Bij gelijke verschillen kies je voor het eerste symbool. Deze observatie is ook de sleutel tot het antwoord op onderdeel 2G.

Enkele deelnemers hielden stellig vol dat hun programma het te verklaren verschijnsel niet vertoonde. Dat had wellicht te maken met de wijze van uitrekenen van de onderlinge verschillen; als je dat niet doet zoals in het voorbeeld, maar met afgeronde getallen, zou e.e.a. wel eens heel anders kunnen uitkomen.

In de uitleg van Vincent Groenhuis werd duidelijk wat de hele serie a’s in de gemaakte tekst verklaarde:

Het zit zo: na 60 tekens eindigt de 'zin' op: eaa

Het programma kan nu kiezen uit 'aaa', 'aab', 'aac' enzovoort.

De rel. freq. van alle 'aa_' in deze zin is hoger dan die rel. freq. in de

oorspronkelijke tekst, dus het programma gebruikt nu een 'aa_' die nog niet

in de oorspronkelijke tekst voorkwam. Het laagste is dan 'aaa'. Enzovoort.

De andere oplossing die alle punten van de jury kreeg is die van Lourens Veen:

Zodra de relatieve frequenties van de brontekst en de doeltekst gelijk zijn

levert elke nieuwe "zet" niets nieuws op; alles is dus even goed, het

programma kiest dus de eerste in het alfabet en dat is aaa.

Nog mooier zou een combinatie van beiden zijn: Zolang de relatieve frequenties in de nieuwe tekst groter zijn dan of gelijk zijn aan die in de originele tekst, levert iedere nieuwe letter een zelfde verslechtering op, en dus kies je voor de a.

Gemiddelde score: 1,02 punten (maximaal 8 punten)

Lourens Veen en

Vincent Groenhuis (derde ronde) 8

Tijmen Tieleman 7

Elianne Faber 6

Johan de Ruiter 5

Maks Verver (derde ronde) 3

Danny Oude Bos 2

Jappie Hoekstra en

Wilmer van der Gaast 1

Beste scores opgave 2.

Lourens Veen 64

Bram Kuyvenhoven 62

Berteun Damman 58

Wilmer van der Gaast 51

Johan de Ruiter 49

Roland Veen 48

Tijmen Tieleman 47

Maarten Löffler 46

Jaap Taal 40

Vincent Groenhuis (derde ronde) 38

Maks Verver (derde ronde) 37

Gemiddelde score: 22,14 punten (maximaal 100)