Pociąg towarowy

Na XXX Olimpiadzie Informatycznej zawodnicy mierzyli się z zadaniem “Pociąg towarowy”. Pełną treść zadania można znaleźć na oficjalnej stronie Olimpiady. W dużym skrócie w zadaniu mieliśmy dany ciąg oraz jego podciąg. Niestety – mając takie dane nie jesteśmy w stanie określić które dokładnie elementy zostały wybrane do podciągu. Dla przykładu: jeśli ciągiem jest 1 3 2 1 2 3 1 3 2, a jego podciągiem jest 1 3 1 2, to podciąg mógł zostać wybrany z następujących elementów:

1 3 2 1 2 3 1 3 2
1 3 2 1 2 3 1 3 2
1 3 2 1 2 3 1 3 2
1 3 2 1 2 3 1 3 2
1 3 2 1 2 3 1 3 2

W zadaniu należało podać dla ciągu oryginalnego, który z jego elementów mógł zostać wybrany do podciągu, a który nie. Dla naszego przykładu poprawną odpowiedzią jest 1 1 0 1 1 1 1 0 1.

Zadanie można było rozwiązać na wiele sposobów. Ja zdecydowałem się na policzenie dwóch tablic:

• prefix[i] = największy index j, taki że ciąg[i] = podciąg[j] oraz podciąg[1..j-1] jest podciągiem ciągu ciąg[1..i].
• sufix[i] = najmniejszy index j, taki że podciąg[j..m] jest podciągiem ciągu ciąg[i..n], gdzie m to długość podciągu, a n długość ciągu.

Mając te dwie tablice, możemy sprawdzić czy ciąg[i] mógł zostać wybrany do podciągu sprawdzając czy prefix[i] + sufix[i+1] >= m. Pozostaje jedynie policzyć tablice prefix[i] oraz sufix[i].

Aby utworzyć tablicę prefix[i] utworzymy przy okazji tablicę lastcolor[k]. Będziemy w niej trzymać ostatni index j taki, że podciąg[j] = k oraz podciąg[1..j] jest podciągiem ciągu ciąg[1..i]. Poniżej prezentuję kod, który oblicza tablicę prefix[i].

    int j = 1;
    int lastcolor[MAX];
    int prefix[MAX];

    for (int i = 1; i <= k; i++)
        lastcolor[i] = -1;

    for (int i = 1; i <= n; i++)
    {
        if (j <= m and ciag[i] == podciag[j])
        {
            lastcolor[podciag[j]] = j;
            j++;
        }
        prefix[i] = lastcolor[ciag[i]];
    }

Tablicę sufix[i] można obliczyć jeszcze prościej. Aby obliczyć sufix[i] wystarczy skopiować wartość sufix[i+1] a następnie sprawdzić czy da się go powiększyć o kolejny element:

    int sufix[MAX+1];

    sufix[n+1] = 0;
    for (int i = n; i >= 1; i--)
    {
        sufix[i] = sufix[i+1];
        if (sufix[i] <= m and ciag[i] == podciag[m-sufix[i]])
            sufix[i]++;
    }

Daje nam to rozwiązanie naszego zadania w czasie liniowym. Pełny kod rozwiązania można znaleźć na moim githubie.