Tävlingsprogrammering/Uppgifter/Lagtävling

Lagtävling

Vissa anser att PO borde ha en lagtävling där den bästa skolan utses baserat på de individuella resultaten. Då uppkommer naturligtvis frågan hur denna vinnande skola ska utses. Om vi har N deltagare i PO och vi antar att uppgifterna är så utslagsgivande att inga deltagare får samma resultat, så kan resultatet beskrivas som en sträng med N bokstäver, där varje bokstav representerar en skola och är ordnade så att den första bokstaven anger vinnarens skola, nästa bokstav anger den andraplacerades skola o.s.v. (vi antar i denna uppgift att högst 26 skolor deltar, så bokstäverna A-Z räcker).

Ett möjligt sätt att utse vinnande skola vore då att lägga ihop placeringssiffrorna för de K bästa eleverna från varje skola och välja den med minst placeringssiffra (skolor med mindre än K elever räknas givetvis inte). Problemet med detta system illustreras bäst med ett exempel: Antag att resultatet är AABCBBCCDDDA och att K=3. Då vinner B med placeringssumman 3+5+6=14 medan A får 1+2+12=15. Men om vi istället jämför A direkt med varje annat lag, utan att ta med deltagarna från övriga lag när vi beräknar placeringssiffrorna. Då vinner A varje sådan duell med 1+2+6=9 mot 3+4+5=12. Observera att alla A:s deltagare kan påverka placeringarna för lag B, inte bara de K första.

Ett lag som vinner alla sådana hypotetiska dueller mot övriga lag brukar kallas för en Condorcet-vinnare, och det faktum att vår första metod inte alltid utser Condorcet-vinnaren, även om en sådan finns, kan beskrivas som att metoden inte uppfyller Condorcet-kriteriet. Föga förvånande används dessa termer oftare om politiska valsystem än programmeringstävlingsresultat.

Skriv ett program som, givet en resultatlista och talet K, avgör om det finns en Condorcet-vinnare bland skolorna.

Indata

Först en rad med två heltal N och K, det totala antalet deltagare och antalet som ska räknas med för varje skola (1≤N≤1000 och 1≤K≤100). Därefter en rad med N bokstäver, valda bland A–Z. Observera att en skola med mindre än K deltagare automatiskt förlorar sina dueller.

Utdata

Programmet ska skriva ut en rad med bokstaven representerande den skola som är Condorcet-vinnare, eller strängen "Ingen" om det inte finns någon Condorcet-vinnare.

Exempel 1

12 3
FKGHGFHHGFFG

ska ge

G

Exempel 2

15 2
PAUHABPUOEXVBOH

ska ge

Ingen

Lösning

Mycket av svårigheten med denna uppgift låg i att förstå uppgiften. Bara två körningsexempel gjorde att man var tvungen att läsa texten noga för att vara säker på att få allting korrekt.

Själva algoritmen är enkel: För varje par av lag (d.v.s. bokstäver) räknar vi ut placeringssiffrorna för de lagens deltagare men med alla andra deltagare bortplockade. Vi summerar de K första placeringssiffrorna och avgör därmed om något av lagen "vunnit" duellen. Vi måste också inkludera fallet när ett lag har färre än K deltagare, då förlorar de automatiskt alla dueller. Ett lag som vunnit mot alla övriga lag är en Condorcet-vinnare.

Uppgiften är inspirerad av en essä av Stephen Szydlik: May the Best Team Win: Determining the Winner of a Cross Country Race.

Lösning i C:

#include <stdio.h>

int main() {
  char inp[1001];
  int n[26],s[26],w[26],i,j,a,b,t,N,K;
  scanf("%d %d", &N,&K);
  scanf("%s", inp);
  for(i=0;i<26;i++) w[i]=0;    // räknare som räknar antalet vinster 
  for(a=0;a<26;a++)    // Loopa över alla par (a,b)
     for(b=a+1;b<26;b++) {
        n[a]=s[a]=n[b]=s[b]=0; 
        for(i=0,j=1;i<N;i++) {
          t=inp[i]-'A';      // Översätt från bokstav till 0-baserat index
          if(t==a || t==b) {
            n[t]++;       // Öka antalet förekomster
            if(n[t]<=K) s[t]+=j;    // Summera placeringssiffran, men endast om vi högst funnit K förekomster.
            j++;    // Öka placeringssiffran  (görs endast om t=a eller t=b)
          }
        }
        if(n[a]>=K && (n[b]<K || s[a]<s[b])) w[a]++;    // a vinner duellen
        if(n[b]>=K && (n[a]<K || s[b]<s[a])) w[b]++;    // b vinner duellen
     }
  for(i=0;i<26;i++) if(w[i]==25) {
      printf("%c\n", i+'A');
      return 0;
    }
  printf("Ingen\n");
}