TDDI16 Datastrukturer och algoritmer

Kattis

KATTIS

Kattis är en så kallad onlinedomare, ett verktyg som automatiskt rättar lösningar på algoritmiska problem. Vektyg som Kattis används ofta för att automaträtta problemen i programmeringstävlingar.

För att komma till kursens sida i Kattis, använd direktlänken i menyn till vänster. Logga sedan in med LiU-id, och välj länken I am attending this course för att berätta för Kattis att ni deltar i kursen. Detta gör att vi kan se era resultat så att ni kan få bonuspoäng senare.

När ni har gjort det, så kan ni ge er i kast med att lösa problem i Kattis. De flesta föreläsningar har två problem i Kattis som relaterar till det som togs upp på föreläsningen, ett lite lättare och ett lite svårare. Se föreläsningssidan för vilka problem som hör ihop med vilka problem. Det är självklart okej att lösa flera problem i Kattis om ni vill, även om dessa inte ger bonus i kursen. Hör av er om ni vill ha fler förslag på lämpliga problem.

När ni har löst ett problem, skickar ni in källkoden till Kattis genom att klicka på submit-knappen och ladda upp er källkod. Det finns också ett script för att enkelt ladda upp kod direkt ifrån terminalen om ni tycker att det är smidigare. Det finns beskrivet här. När ni har skickat in ett problem kan ni efter ett tag se resultatet genom att ladda om sidan eller klicka på my submissions. Då kommer Kattis antingen säga Accepted om lösningen är godkänd, eller ett annat meddelande som indikerar att något har gått fel. Notera att Kattis i allmänhet bara säger att något gick fel, inte varför det gick fel. Det är upp till er att hitta det eller de specifika fallen som fick ert program att misslyckas eller krascha!

Tips för snabbare program

För vissa problem med stor mängd indata (exempelvis union-find) så kan inläsningen av data ta så pass mycket tid att det inte finns någon tid att lösa problemet. Det visar sig att cin är relativt långsam i C++ som standard. Det finns ett par saker man kan göra åt saken:

• Anledningen till att cin (och till viss del cout) är långsamma är att de måste hålla koll på motsvarigheterna i C, då det går att blanda inläsning med cin och motsvarigheterna i C++. Eftersom att vi vet att vi inte använder C-funktionerna så kan vi säga åt standardbiblioteket att det inte behöver hålla koll på detta genom att köra följande kod någon stans tidigt i vårt program:

  std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

• Det andra alternativet är helt enkelt att använda C-funktionerna för inläsning. För den typ av indata som oftast finns i Kattis passar scanf ofta bra. Den kan användas som nedan:

  int a;
int b;
int num_ok = scanf("%d%d");
// num_ok innehåller hur många tal som scanf lyckades läsa in

IMPA

Om ni tycker att Kattis-problemen var roliga, kan det vara värt att titta närmare på IMPA - IDA-Mästerskapet i Programmering och Algoritmer. IMPA anordnar tävlingar i samma stil som Kattis-problemen under terminerna. Tävlingarna delas in i olika omgångar, där varje omgång pågår i ungefär fyra veckor. Topp 10 i varje omgång får ett pris i form av presentkort på valfritt ställe. I och med att studenter med olika erfarenhet deltar i IMPA så tar poängsystemet hänsyn till detta, så att alla ska ha en chans att placera sig bra. Läs mer om det här.

Sidansvarig: Filip Strömbäck
Senast uppdaterad: 2023-08-09