Välkommen till IDA-Mästerskapet i Programmering och Algoritmer (IMPA). Tävlingen riktar sig till studenter på alla nivåer vid Linköpings universitet som är intresserade av algoritmer, programmering och problemlösning.

Vårens IMPA-tävling består av 6 omgångar som var och en omfattar 3 veckor. Varje omgång är en egen tävling med 3000kr i vinster.
Första omgången börjar måndag 15 januari och sista omgången slutar söndag 19 maj 2024.

Syftet med IMPA är att studenter vid Linköpings universitet ska bli bättre på programmering, algoritmer och problemlösning. Målet är dels att LiU ska placera sig bättre i nationella och internationella programmeringstävlingar och dels att studenter som deltar ska bli mer eftertraktade på arbetsmarknaden tack vare sin dokumenterade kompetens.

Förutom värdefulla meriter som många företag sätter stort värde vid, delar våra sponsorer Axis, MindRoad och Opera Software ut generösa priser till duktiga deltagare. Priserna delas ut i form av presentkort enligt överenskommelse mellan tävlingsledaren och respektive vinnare. Eventuell vinstskatt betalas av vinnaren.

Avancerad kurs i Algoritmisk Problemlösning

På våren ges kursen i Algoritmisk Problemlösning som en vanlig avancerad teknologkurs. Fokus är på datastrukturer, algoritmer och problemlösning av samma typ som IMPA. Kursen är ett bra komplement till och ungefär på samma nivå som kursen i Konstruktion och Analys av Algoritmer. Kursen föreläsningar är öppna för alla.

Gå med i IMPAs Facebook-grupp

OmgångarPriser i varje omgång
Omgång 1: 15 jan -  4 feb1:a pris1000kr
Omgång 2:  5 feb - 25 feb2:a pris 600kr
Omgång 3: 26 feb - 17 mar3:e pris 400kr
Omgång 4: 18 mar -  7 apr4-6:e pris 200kr
Omgång 5:  8 apr - 28 apr7-10:e pris 100kr
Omgång 6: 29 apr - 19 maj

Att komma igång

Vi tycker att det är roligt att du vill prova på tävlingsprogrammering! Den här sidan innehåller information om de olika steg som behöver tas för att komma igång rent praktiskt. Du får också hjälp med att lösa din första uppgift!

Registrera dig på UVA

Vi använder ett egenutvecklat system (IMPA) för att hålla reda på vilka uppgifter du har klarat av. IMPA har en stor problemdatabas där uppgifter av olika svårighetsgrad kan hämtas. För närvarande använder sig IMPA av en onlinedomare som heter "UVA Online Judge". Den här domaren tillhandahålls av Universidad de Valladolid och det är dit du kommer att skicka dina lösningar för att få dem rättade. Därför behöver du ett konto på UVA.
UVAs webbsida finns på http://uva.onlinejudge.org. Där registrerar du dig. Efter det kan du välja "browse problems"-länken på vänster kant av huvudsidan. Därifrån kan du leta dig fram till problemet du vill lösa.

Registrera dig i IMPA-systemet

Välj fliken "Logga in/Registrera" ovan. Där loggar du in med ditt liuid och registrerar dig. Du behöver bland annat ange ditt användarnamn på UVA för att systemet ska kunna kontrollera hur det går för dig med uppgifterna.

Programmeringsspråk

Godkända programmeringsspråk är C, C++, Java och Python. UVA stödjer även Pascal, men vi rekommenderar att du håller dig till de tre förstnämnda språken. I den här guiden kommer vi huvudsakligen att använda oss av Java, men visar också ett exempel i C och C++.

Här finns en jämförelse mellan Java och C, en Java-tutorial och dokumentation av Javas omfattande klassbibliotek, som tillhandahåller mycket funktionalitet. Det finns också en jämförelse mellan Java och C++, lite dokumentation för C++ och dokumentation av SGI:s STL för C++. I den här guiden visar vi inte hur du installerar kompilatorer och IDE:er på din dator. Behöver du hjälp med det kan du titta här för C++ och C och här för Java.

Uppgifterna

De här uppgifterna har vi tänkt att du ska försöka lösa. Svårighetsgraden är från väldigt enkla, där syftet är att du ska vänja dig vid att använda UVA, till lite klurigare.

Lös din första uppgift

Vi startar genom att ge oss i kast med problemet Relational Operators.

Börja med att läsa problemlydelsen. Var säker på att du förstått specifikationen av in- och utdata. När du skickar in din kod kommer domaren att kompilera den och köra den på sitt eget indata baserat på indataspecifikationen och förväntar sig att utdata följer specifikationen i problembeskrivningen.

Nu är det dags att börja koda din lösning. Du ska läsa indata från standard input och skriva utdata till standard output. UVA kommer att kompilera din kod med en kompilator som stödjer JDK 1.6. All kod måste finnas i samma fil och innehålla klassen Main, med en main-metod. Så här skulle en mall för kod som löser en typisk uppgift på UVA kunna se ut:

  import java.util.Scanner;
  
  class Main {
     public static void main(String[] args) {
       new Main().solveProblem();
     }
  
     public void solveProblem() {
       final Scanner scanner = new Scanner(System.in);
       while (scanner.hasNextInt()) {
         int input = scanner.nextInt();
         int solution = solveCase(input);
         System.out.println(solution);
       }
       scanner.close();
     }
  
     public int solveCase(int number) {
       int solution = number + number;
       return solution;
     }
  }

Ibland har ett UVA-problem väldigt mycket indata. Då kan det vara lämpligt att använda en BufferedReader istället:

  Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));

I problemet vi försöker lösa kommer indata börja med ett heltal t<15 som anger hur många testfall indata innehåller. Precis som i exempelkoden kan vi använda en Scanner för att läsa in en int från System.in på det här viset:

  final Scanner scanner = new Scanner(System.in);
  int testcases = scanner.nextInt();

En Scanner delar upp indata i "tokens" genom att matcha mot ett mönster som per default är alla sorts blanktecken och mellanrum. Sedan kan man få ett "token" i taget genom att anropa de olika next-metoderna. Du kan läsa mer om Scanner-klassen här.

Enligt problembeskrivningen kommer varje testfall att bestå av två heltal vars absolutbelopp är strikt mindre än 1000000001. Den informationen är viktig för att vi ska kunna välja variabeltyp för lagring av de två heltalen. Eftersom en vanlig int i Java kan representera värden mellan -2147483648 och 2147483647 räcker det bra med två sådana i det här fallet. För att lösa problemet behöver vi sedan bara jämföra de två heltalen och skriva ut resultatet av jämförelsen. Sammantaget skulle det kunna se ut så här:

  import java.util.Scanner;
  
  class Main {
     public static void main(String[] args) {
       new Main().solveProblem();
     }
  
     public void solveProblem() {
       final Scanner scanner = new Scanner(System.in);

       int testcases = scanner.nextInt();
    
       while (testcases != 0) {
         int a = scanner.nextInt();
         int b = scanner.nextInt();
         char solution = solveCase(a, b);
         System.out.println(solution);
         testcases--;
       }
       scanner.close();
     }
  
     public char solveCase(int a, int b) {
        if (a < b)
          return '<';
        else if (a > b)
          return '>';
        else
          return '=';
     }
   }

En lösning i C finns här och en i C++ här.

För att testa programmet, skapa en textfil "in.txt" med indataexemplet från problembeskrivningen och exekvera:

  > javac Main.java
  > java Main < in.txt

Fungerar det? Bra! Du är nu redo att försöka skicka in problemet till UVAs automatiska domare. I övre högra hörnet på problembeskrivningssidan finns en Submit-länk. Om du klickar på den kommer du till inskickningssidan för det problemet. Välj språket du löst problemet i och ladda upp din kod med uppladdningsverktyget (eller klistra in den i rutan). Det går också bra att välja "Quick Submit"-länken på vänstra kanten av sidan för att komma till inskickningssidan, med skillnaden att du behöver fylla i uppgiftens ID-nummer. När du är klar är det bara att klicka på submit och hålla tummarna.

Du kan kontrollera statusen för din inskickning genom att välja "My Submissions"-länken på vänstra kanten av sidan. Under rubriken "Verdict" får du reda på om uppgiften har accepterats som löst eller om det blev något problem (t.e.x. fel svar, för lång exekveringstid, programmet kraschade, för mycket minne användes, kompileringsfel, etc.). Om din kod har orsakat ett kompileringfel finns också en länk till felmeddelandet. Här finns en sida med de olika svaren domaren kan ge: http://online-judge.uva.es/board/viewtopic.php?t=7430.

Förhoppningsvis har nu din lösning av Relational operators fått "Accepted" på UVA. Strax kommer IMPA-systemet upptäcka det och då har du klarat av din första uppgift, grattis! Nu föreslår vi att du själv tar tag i den andra uppgiften i listan -- problemet Hashmat the Brave Warrior.

När du löst en uppgift är du välkommen till oss för att hämta ett fint litet pris.

Lär dig mer!

Lösning i C till Relational Operators

  #include <stdio.h>

  int main(void) {
    long int testcases, a, b;

    scanf("%ld", &testcases);

    while(testcases != 0) {
      scanf("%ld%ld", &a, &b);

      if (a < b)
        printf("<\n");
      else if (a > b)
        printf(">\n");
      else
        printf("=\n");

      testcases--;
    }
  
    return 0;
  }
  

Lösning i C++ till Relational Operators

  #include <iostream>

  using namespace std;

  int main(void) {
    long int testcases, a, b;

    cin >> testcases;
  
    while(testcases != 0) {
      cin >> a >> b;

      if (a < b)
        cout << "<" << endl;
      else if (a > b)
        cout << ">" << endl;
      else
        cout << "=" << endl;
    
      testcases--;
    }

    return 0;
  }