Zadanie LAN

Łańcuch kolorowy – Finał XX OI

Zadanie “Łańcuch Kolorowy” polega na sprawdzeniu ile jest jest “idealnych” spójnych podciągów danego ciągu koralików. Idealny podciąg to taki, który posiada dokładnie li koralików koloru ci.

Rozwiązanie brutalne

Pierwszym pomysłem jest zatem zaimplementowanie dokładnie tego o co nas proszą:

  • zapamiętujemy ilość koralików każdego koloru w idealnym ciągu oraz jego długość;
  • bierzemy każdy spójny podciąg, o długości idealnego ciągu, naszej tablicy koralików i sprawdzamy czy liczba każdego z kolorów się zgadza, gdy tak jest powiększamy wynik o 1;

Takie rozwiązanie wymaga jednak od nas ciągłego przechodzenia po tablicy kolorów co sprawia, że za takie rozwiązanie dostaniemy ok 50pkt.

 

Przykładowa implementacja:

/*
sumColors - długość idealnego ciągu
idealSequence - tablica ilości każdego koloru w idealnym ciągu
amountColors, colors - ilość i rodzaj danego koloru(z wejscia)
sequenceColors - tablica ilości każdego koloru w sprawdzanym podciągu
sequence - ciąg koralików
*/
int sumColors = 0;
for(int i = 0;i < m;++i)
{
    idealSquence[colors[i]] = amountColors[i];
    sumColors += amountColors[i];
}
for(int i = 0;i < sumColors-1;++i)
    ++sequenceColors[sequence[i]];

for(int i = sumColors-1;i < n;++i)
{
    bool ideal = true;
    ++sequenceColors[sequence[i]];
    for(int j = 0;j < m;++j)
    {
        if(idealSequence[colors[j]] != sequenceColors[colors[j]])
            ideal = false;
    }
    if(ideal)
        ++result;
    --sequenceColors[sequence[i-sumColors+1]];
}

Rozwiązanie wzorcowe

Rozwiązanie wzorcowe polega na zastosowaniu techniki haszowania, która pozwala w czasie stałym sprawdzać czy dany podciąg jest idealny.

Haszowanie pozwala nam zapisać dany ciąg jako liczba, która dzięki zastosowaniu potęg dużej liczby pierwszej modulo inna liczba pierwsza, prawie na pewno będzie unikalna i nie pojawi się przy innym ciągu.

long long fixMod(long long n)
{
    return ((n%mod)+mod)%mod;
}
long long hashC(vector<int> &idealSequence)
{
    long long hash = 0;
    for(int i = 0;i < idealSequence.size();++i)
    {
        hash += powers[idealSequence[i]];
        hash  = fixMod(hash);
    }
    return hash;
}
 

Powyższy kod sumuje potęgi liczby pierwszej, której wykładnikami są kolejne kolory idealnego ciągu, a potem wykonuje “magiczne” modulo 😉

Funkcja fixMod ma zwrócić wartość z przedziału od 0 do mod. Rozważając 2 możliwe przypadki dla ‘n'(ujemne lub nieujemne) można zauważyć, że zwracana wartość zawsze będzie z chcianego przedziału.

Teraz możemy wykorzystać tę samą technikę do sprawdzania czy nasz podciąg jest “idealny”. Haszujemy podsłowo długości naszego wzorca i sprawdzamy czy jest identyczne. Potem przesuwamy się w prawo odejmując kolor z początku i dodając nowy na koniec. Całe rozwiązanie działa w czasie O(n) i daje 100pkt za to zadanie.


Podsumowanie

Zachęcam do zgłębienia tematu haszowania i szerszego zapoznania się z możliwościami tej techniki oraz zadawania pytań w komentarzach. Pełen kod z rozwiązaniem zadania znajduję się na GitHubie.

2 thoughts on “Łańcuch kolorowy – Finał XX OI

  1. Hej, fajny sobie coś przypomnieć o zadankach z OI ;).

    Masz tutaj trochę niegramatyczne zdanie: “Haszowanie pozwala nam zapisać dany ciąg jako liczba, która z dzięki zastosowaniu potęg dużej liczby pierwszej modulo inna liczba pierwsza, prawie na pewno będzie unikalna i nie pojawi się przy innym ciągu.” (która z dzięki)

    Wydaje mi się, że kod rozwiązania w O(n) można nieco poprawić:
    1. co to jest niezdeklarowana zmienna “hasz” (w pętli for)
    2. ((n%mod)+mod)%mod; nie jest przypadkiem tym równoważne n%mod? Chyba wypadałoby mieć tu dwie różne liczby pierwsze, bo inaczej to łatwiej o kolizje.

    1. Hejka, dzięki za komentarz.

      Ad1. Literówka(już poprawione), w kodzie na githubie jest zmienna “hasz”.
      Ad2. Różnica jest taka, że dla ujemnego n(i mod będącego dużą liczbą pierwszą) modulo da wynik ujemny, więc gdy podczas usuwania danego koralika hasz będzie mniejszy niż potęga dla danego koloru to zejdzie na ujemne i przez to nie wyłapie Ci wszystkich wystąpień idealnego łańcuszka.

      Dzięki za wyłapanie błędów składniowych, które często mi umykają 😉

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *