Leidsch Kampioenschap Programmeren

Er zijn opgaven van 2016 en opgaven van 2018 beschikbaar.

Hoe werkt een programmeerwedstrijd?

Voorrondes

Voor studenten uit Leiden (Universiteit Leiden, Hogeschool Leiden) kent de ICPC (International Collegiate Programming Contest) in totaal vier rondes:

LKP (Leids Kampioenschap Programmeren). (Open voor alle teams van de Universiteit Leiden of de Hogeschool Leiden die aan de voorwaarden voldoen.)
BAPC (Benelux Algorithm Programming Contest). (Meestal mogen de beste drie teams van elke onderwijsinstelling meedoen aan de BAPC.)
NWERC (Northwestern European Regional Contest). (Meestal mogen de beste twee teams van elke onderwijsinstelling meedoen aan de NWERC.)
ICPC World Finals. (Meestal mogen de beste drie teams van de hele regio Noord-West Europa meedoen aan de ICPC World Finals.)

Verder geldt de volgende vuistregel: hoe verder je komt, hoe meer excursies er voor je georganiseerd worden!
Regelmatig lukt het een team uit Leiden om de laatste ronde te halen. In 2011, 2013 en 2018 waren er nog teams van de Universiteit Leiden op de ICPC World Finals.

Puntentelling

De score van een team bestaat uit twee onderdelen: het aantal opgaven opgelost en de totale tijd (de zogeheten penalty time). Per opgeloste opgave bestaat dat uit de volgende twee onderdelen:

Het aantal minuten tussen het begin van de wedstrijd en het oplossen van de opgave;
20 strafminuten voor elke foute inzending.

Een foute inzending levert alleen strafminuten op als de opgave later alsnog wordt opgelost.

De teams worden gesorteerd op aantal opgeloste opgaven. Teams met evenveel opgaven worden gesorteerd op tijd. Het laatste uur wordt het scorebord bevroren. Je hoort dan nog wel of je eigen inzendingen goed of fout zijn, maar niet welke opgaven de andere teams nog oplossen.

Tijdsschema

Hier in het kort de informatie voor de dag (28 september): het begint om 10:00. 's Ochtends is er een testsessie, gevolgd door lunch. Na de lunch begint de wedstrijd. Om 18:30 is de wedstrijd afgelopen en is er een borrel met prijsuitreiking. Het LKP vindt plaats in het Snellius (zie: https://www.deleidscheflesch.nl/p/contact).

Testsessie

Voor de wedstrijd is er een testsessie. Gebruik deze om te kijken of de wedstrijdomgeving aan al je verwachtingen voldoet. Suggesties:

Lukt het om het toetsenbord goed in te stellen?
Werkt de gewenste editor naar behoren?
Zijn er voldoende tools aanwezig voor debuggen (gdb, valgrind, etc.)?
Hoe werkt de printer?
Is inzenden in C++11 toegestaan?
Kun je __int128_t gebruiken (niet alleen op de computer maar ook bij het inzenden)?
Is er een rekenmachine op de computer (bc, python, gnome-calculator, etc.)?
Staan de samples op de computer? Of zijn ze bereikbaar via de jurynterface?
Waar staat het eten?

Tips voor tijdens de wedstrijd

(Deze tips zijn subjectief. Maak je eigen afweging.)

Het is handig om aan het begin van de wedstrijd templates in te typen (C++ bestanden met alle nuttige headers, makefile, etc.), zodat je tijdens de wedstrijd niet hoeft op te zoeken welke headers je allemaal nodig hebt.
Verdeel de opgaven over je team. Ken elkaars sterke en zwakke punten, en geef het tijdig aan als je denkt hulp nodig te hebben.
Eerst nadenken, dan programmeren. Zorg dat je niet een uur lang de computer in beslag neemt als je nog niet precies weet wat je gaat doen.
Als je nog niet bij de computer kunt, kun je alvast nadenken over complicaties bij het implementeren. Bijvoorbeeld:
- Kijk op welke plekken overflow op de loer ligt;
- Bereken of je algoritme snel genoeg is. De tijdslimiet is meestal enkele seconden op een computer met een kloksnelheid van een paar gigahertz. Dat betekent dat je hooguit in de orde van 10⁹ berekeningen kunt doen. In de praktijk kun je vaak hooguit 10⁷ of 10⁸ iteraties uitvoeren.
- Bedenk of er rare randgevallen zijn (n = 0, de lege graaf, enzovoort). Het zal je verbazen hoe vaak een inzending fout gaat op een randgeval.
Lukt het niet om de bugs snel te fixen, print dan de code uit. Leer op papier debuggen. Zo kunnen je teamgenoten ondertussen wat anders gaan doen op de computer.

Zelf oefenen

Individueel:

USACO Training pages. Uitgebreid trainingsprogramma van de informatica olympiade in de VS.
UVa Online Judge. Online judge van de Universidad de Valladolid in Madrid met een gigantisch archief aan opgaven.
- uHunt Training Series. Aardige selectie van opgaven van bovengenoemde UVa Online Judge.
- ICPC Live Archive. Onderdeel van de UVa Online Judge. Bevat heel veel opgaven van oude regional contests (niet alleen de NWERC, maar ook allerlei andere regio's).
GEPWNAGE Online Judge. Archief van opgaven bijgehouden door het dispuut GEPWNAGE van GEWIS, de studievereniging van wiskunde en informatica aan de TU/e.
Project Euler. Uitdagende problemen op het raakvlak van wiskunde en informatica. Meer gericht op probleemoplossend vermogen dan programmeren.
OpenKattis is een online judge waarop regelmatig wedstrijden worden gehost

Daarnaast kun je ook met je team een oude wedstrijd opzoeken en integraal oefenen.

Andere programmeerwedstrijden

Individuele deelname:

USACO Contests. Leuke, uitdagende wedstrijden gericht op middelbare scholieren in de VS. Andere mensen kunnen buiten mededinging meedoen om te oefenen.
Google Code Jam. Programmeerwedstrijd van Google. De beste 1000 deelnemers winnen een t-shirt. Nog grotere prijzen voor de top 25, maar dat is voor normale mensen onhaalbaar.
KTH Challenge. Leuke programmeerwedstrijd georganiseerd door de Kungliga Tekniska Högskolan in Stockholm. Mensen in andere landen (zoals Nederland) kunnen buiten mededinging meedoen via internet. Helaas maar één keer per jaar.
Facebook Hacker Cup. Programmeerwedstrijd van Facebook. Concept vermoedelijk gebaseerd op Google Code Jam. Een stuk lastiger om een t-shirt te winnen.

Deelname in team:

Internet Problem Solving Contest. Interessante wedstrijd met onconventionele opgaven. Deelname in teams van drie, ditmaal met één computer per persoon.