Op dinsdag 28 april 2015 organiseerde de opleiding Informatica van
de Universiteit Leiden een programmeerwedstrijd voor de eerstejaars
studenten Informatica. De wedstrijd vond plaats in het kader van het
vak Challenges in Computer Science Seminar, voorjaar 2015.
De studenten werkten
in teams van twee personen en de programmeertaal was C++.
Voor de wedstrijd vond er vanaf 13:45 een korte introductie plaats.
de volgende plaatjes in de opgaven hebben we van anderen overgenomen:
Compact disc,
van Arun Kulshreshtha (opgave B)
Gas pipeline,
van chazelles.info (opgave E)
een korte bespreking van de opgaven:
A: vereist dynamisch programmeren. Het aantal mogelijke
routes voor (N,E) is in principe het aantal mogelijke routes voor
(N-1,E) plus het aantal mogelijke routes voor (N,E-1).
Sla deze waardes op in een array. Let er wel op dat je een array van
1001x1001 integers nodig hebt (of een array van 1001 integers, als je
het slim doet). Een recursief algoritme zonder opslag van berekende
waardes duurt veel te lang.
B: rechttoe-rechtaan optellen van tijden en vergelijken met de speeltijd
van de CD. Alleen het lezen van de invoer en het wegschrijven van
de uitvoer is een beetje vervelend.
C: puzzelopgave, waarvoor een gretig algoritme geschikt is. Houd
een lijst met beschikbare opgaven bij, dat wil zeggen: opgaven waarvan
je de oplossing al hebt bedacht, maar die je nog niet (helemaal) hebt
ge-implementeerd. Sorteer deze lijst op resterende implementatietijd
(kortste tijd eerst), en werk ze in principe in die volgorde af.
Zodra er een nieuwe opgave beschikbaar komt (dwz: je hebt zijn oplossing
bedacht), wordt die met zijn totale implementatietijd aan de lijst
met beschikbare opgaven toegevoegd, waarna je weer de opgave met
de kleinste (resterende) tijd kiest om aan verder te werken.
D: brute-force. In principe bouw je alle mogelijke rijtjes met
dobbelstenen op. Al tijdens het opbouwen van zo'n rijtje, controleer
je of er soms al een verboden deelrijtje in zit. Zo ja, dan breid je
hem niet verder uit.
Van tevoren moet je nog even de waardes op de dobbelsteen filteren,
zodat je elke mogelijke waarde maar 1 keer overhoudt.
E: bepaal het aantal samenhangende componenten van de graaf,
gevormd door de landen en de gasbuizen. Dat kan met een herhaalde
depth-first-search (weinig code, als je weet hoe het werkt),
een herhaalde breadth-first search (meer code) of met union-find
(het elegantst, omdat je dan de graaf niet hoeft op te slaan).
Als je je wilt voorbereiden op een programmeerwedstrijd,
dan kun je oefenen met de opgaven van eerdere programmeerwedstrijden.
Er zijn veel sites van zulke wedstrijden. We noemen er hier drie:
Universidad de Valladolid
(een grote database met opgaven, en automatische, online jurering;
je zult wel een account moeten aanmaken)
Vragen en opmerkingen kunt u sturen naar:
Rudy van Vliet;
rvvliet(at)liacs(dot)nl
Laatste wijziging: 5 mei 2015
- http://www.liacs.leidenuniv.nl/~rvvliet/ccss2015/index.html
