Tävlingsprogrammering/Uppgifter/Wikipediaspråk

Wikipediaspråk

Om jag säger "Sortera orden [zebra, anka, duva]!" så svarar du snabbt [anka, duva, zebra]. Lätt, va? Det gäller även om du inte känner igen ordens innebörd eller alla tecken i språket, typ [fünf, como estás, désolé]. Vi kan ju svenska och engelska och vet att troligen är svaret [como estás, désolé, fünf]. Ännu inte så svårt. Men troligen finns det få programmeringsolympiaddeltagare som kan sortera sådana ordlistor så fort kinesiska, persiska och andra icke-latinska tecken är inblandade i ordlistorna. Hur skulle du jämföra ett engelskt ord med ett persiskt ord? En av problemförfattarna vet visserligen hur persiska ord ska uttalas, men utan den kunskapen blir det svårt.

Antag nu att vi vill sammanställa en sorterad lista av ord. Till vår hjälp har vi ett antal personer som vardera känner igen ett antal ord och vet deras inbördes ordning. Vi behöver inte ta med alla ord i vår ordlista, men vi vill vara helt säkra på att de ord vi tar med är rätt sorterade. Skriv ett program som beräknar det maximala antalet ord vi kan ha med i ordlistan, och skriver ut en giltig ordlista med detta antal ord.

Indata

För enkelhets skull behöver du inte läsa in själva orden, utan varje ord representeras istället av ett index mellan 0 och N−1. På första raden av indatan står två heltal N (1≤N≤130000) och P (1≤P≤105), där N är antalet ord och P är antalet personer. Därefter följer P rader som vardera anger ordningen på de ord som en viss person känner till. Varje sådan rad börjar med ett heltal 2≤p_i≤25 som beskriver hur många ord personen i fråga känner till den inbördes sorteringen för. Sedan följer p_i heltal i intervallet 0 till N−1, indexen för de ord personen känner till i den ordning de ska sorteras. Det är inte säkert att alla de N orden finns med på någon lista, och ett ord kan givetvis förekomma på flera listor. Det kommer inte att finnas motsägelser i indatan.

Delpoäng: För 30% av poängen gäller att N≤30.

Utdata

På första raden ska programmet skriva ut det maximala antalet ord M i en garanterat korrekt sorterad ordlista. Därefter ska programmet skriva ut en rad med en sådan sorterad ordlista innehållandes de M ordindexen. Om det finns flera tänkbara sådana ordlistor kan programmet skriva vilken som helst av dem.

Exempel 1

ska ge utdatan

4
0 2 1 3

Exempel 2

ska ge utdatan

6
4 8 2 5 7 9

Lösning

Vi låter orden utgöra noder i en riktad graf och de kända relationerna mellan orden utgöra bågar mellan noderna. Problemet kan då formuleras som att hitta den längsta vägen i en directed acyclic graph (DAG). Det får räknas som ett standardproblem inom algoritmteori och kan lösas på linjär tid, O(E), där E är antalet bågar i grafen, d.v.s. antalet relationer mellan två ord.

Det finns flera sätt att lösa problemet. Ett sätt är att först göra en topologisk sortering av noderna. Sen går man igenom noderna i denna ordning och sparar för varje nod v det största antalet deltagande noder M(v) i en väg fram till v. Detta beräknas som 1 + max(M(u)) där u går över alla noder som har en båge till v.

Ett annat sätt är att skippa det första steget och istället ta noderna i godtycklig ordning. Samma formel gäller förstås fortfarande, men nu är M(u) inte längre garanterat uträknad när man behöver den, utan man får vid behov göra ett rekursivt anrop för att räkna ut M(u). Så fort man har räknat ut ett värde för M bör man naturligtvis spara det i en tabell för att undvika att göra om samma beräkning flera gånger. Ett exempel på denna algoritm visas nedan. Dessa två varianter motsvarar bottom-up respektive top-down dynamisk programmering, som du kan läsa mer om på vår intro-sida till tävlingsprogrammering.

Ett tredje sätt är att se problemet som ett kortaste-vägen-problem i den graf som uppstår om man låter alla vikter vara -1 (och för enkelhets skull binder ihop alla noderna med en startpunkt och en slutpunkt). Den längsta vägen i ursprungsgrafen motsvarar ju då den kortaste i den negerade grafen, och denna kan hittas med exempelvis Bellman-Ford's algoritm. Observera att om det hade funnits cykler i grafen hade dessa blivit negativa cykler i den negerade grafen och algoritmen hade inte fungerat. I själva verket är detta problem NP-komplett, se Longest path problem.

Lösning i C++ (attr: Johan Sannemo)

#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

vector<int> edges[130000];
int longest[130000];

int dp(int nod){
    if(longest[nod] != -1) return longest[nod];          //Redan uträknat, plocka svaret från tabellen 
    if(edges[nod].empty()) return longest[nod] = 1;    //Basfallet att noden inte har några utgående bågar 
    int mx = 0;
    for(int i = 0; i<edges[nod].size(); i++){
        mx = max(mx, dp(edges[nod][i]));         //Rekursera ! 
    }
    return longest[nod] = mx+1;
}

int main(){
    memset(longest, -1, sizeof(longest));
    int n, p;
    scanf("%d%d", &n, &p);
    for(int i = 0; i<p; i++){
        int px;
        scanf("%d", &px);
        int prv;
        scanf("%d", &prv);
        for(int j = 1; j<px; j++){
            int nxt;
            scanf("%d", &nxt);
            edges[prv].push_back(nxt);
            prv = nxt;
        }
    }
    int best = -1;
    int max = 0;
    for(int i = 0; i<n; i++){
        int res = dp(i);         //Räknar ut svaret för denna nod samt alla som den beror på
        if(res > max){
            best = i;       //Spara noden som ger det bästa värdet, den blir förstanod i längsta vägen
            max = res;
        }
    }
    printf("%d\n", max);
    printf("%d ", best);
    //Nu vandrar vi tillbaka genom grafen genom att välja noder som är kvar på den optimala vägen
    for(int i = max-1; i>=1; i--){
        for(int j = 0; j<edges[best].size(); j++){
            int v = edges[best][j];
            if(longest[v] == i){        //Välj en nod vars longest-värde är exakt ett mindre än föregående.
                printf("%d ", v);
                best = v;
                break;
            }
        }
    }
    printf("\n");
    return 0;
}