21030. Liczby podzielne przez 3 [FR_02_15]

Zadanie:
https://spoj.com/FRAKTAL/problems/FR_02_15
https://pl.spoj.com/problems/FR_02_15

Skrócony opis problemu:

Otrzymujemy liczby, w których niektóre cyfry zostały zastąpione znakami zapytania. Należy wypisać liczbę kombinacji jakie można uzyskać zamieniając znaki '?' na cyfry, aby otrzymać liczby podzielne przez 3.

Rozwiązanie naiwne:

Możemy pod każdy znak zapytania podstawiać każdą możliwą cyfrę, a następnie zliczać te liczby, których suma cyfr jest podzielna przez 3 (co jest warunkiem koniecznym i wystarczającym aby liczba była podzielna prze 3).

Złożoność: $O\left(d^n\right)$, gdzie $d$ to rozmiar naszego alfabetu (czyli $d=10$, bo mamy 10 cyfr), a $n$ do długość liczby. W naszym przypadku $n=10$. Złożoność wygląda właśnie tak, gdyż znaków zapytania może być $n$, a dla każdego z nich musimy sprawdzić każdą z $d$ cyfr.

Rozwiązanie sprytniejsze:

By rozwiązać to zadanie szybciej musimy zauważyć, że nie obchodzi nas kolejność wystąpienia znaków zapytania, a jedynie ich ilość. Tak więc 1?2?3?4 da nam taki sam wynik jak 1234???. Jedynie pierwsza pozycja powinna być obsługiwana inaczej, jako że nie może się na niej znajdywać 0 jeśli długość ciągu jest większa niż 1.

A zatem skonstruujmy funkcję, która będzie przyjmowała ilość znaków zapytania, flagę czy dla ciągu o długości większej niż 1 było 0 oraz minimalną liczbę, którą musimy dodać do sumy sumy ciągu (bez znaków zapytania) by była ona podzielna przez 3. Ostatni parametr jest nam potrzebny, bo dla różnych sum przy tej samej ilości znaków zapytania będzie różny wynik (co wynika z samej treści zadania).

Wygodnie będzie użyć tutaj rekurencji. W poprzednim przypadku dla każdego wywołania wykonalibyśmy 10 podwywołań - jedno dla każdej cyfry. Zastanówmy się jak zmniejszyć ilość wywołań. Zauważmy, że obchodzi nam reszta z dzielenia sumy przez 3. A zatem wyniki dla 0, 3, 6 oraz 9 będą takie same. Tak samo będzie z  1, 4, 7 oraz 2, 5, 8. Wystarczy więc wykonać 3 wywołania - jedno dla różnej reszty z dzielenia i pomnożyć je przez 4 (w pierwszym przypadku) lub 3 (w pozostałych).

A zatem, wywołujemy naszą funkcję $count$ dla liczby znaków zapytania $ques$, reszty z dzielenia sumy przez 3 $rem$ oraz flagi $first$. Co będzie podproblemem? Ano możemy podstawić coś pod 1 znak zapytania. Jednak nie dowolną cyfrę, a jej resztę z dzielenia przez 3. Czyli jeśli chcieliśmy na początku uzyskać sumę z dzielenia prz Następnie wywołujemy tę samą funkcję 3 razy, ale dla $ques-1$ znaków zapytania oraz odpowiednio zmienionego $rem$. Rem może mieć jedynie wartości 0, 1 i 2. Dla cyfr 0, 3, 6 i 9 $rem$ się nie zmieni, bo nadal będziemy musieli dodać $rem$ do sumy by otrzymać liczbę podzielną prze 3. Dla cyfr 1, 4 i 7 będziemy musieli dodać $rem-1$ do sumy, chyba że $rem = 0$ - wtedy musimy dodać 2 do sumy. A zatem wzór na $rem$ dla 1, 4 i 7 to $(rem+2) \mod 3$. Analogicznie, dla cyfr 2, 5 i 8 wzorem będzie $(rem+1) \mod 3$.

No a co z tą flagą dotyczącą pierwszego znaku? Nic prostszego! Wystarczy na początku przekazać 1 jako ową flagę, jeśli ciąg zaczyna się od '?' i ma więcej niż 1 znak. Następnie dla każdego wywołania przekazywać będziemy 0. No a gdzie wykorzystać ową flagę? Ano przy mnożeniu przez 4. Jeśli flaga będzie równa 1 to pomnożymy zamiast przez 4 to przez 3.

Musimy jeszcze mieć jakiś warunek końcowy, żebyśmy nie wywoływali funkcji $count$ w nieskończoność. Będzie on naturalnie dla jednego '?'. Jeśli $rem \neq 0$ to zwracamy 0, a w przeciwnym wypadku zwracamy 3 lub 4 w zależności od wartości flagi $first$.

Złożoność: $O\left(3^n\right)$, bo dla każdego wywołania uruchamiamy 3 kolejne. Jak widać, jest to nadal złożoność wykładnicza. Jeśli jednak zauważymy, że $n = 10$ to widzimy, że wykonamy maksymalnie 59049 operacji (a raczej liczbę tego rzędu), a więc niewiele.

Rozwiązanie jeszcze sprytniejsze:

Możemy wprowadzić sporą i łatwą optymalizację do poprzedniego algorytmu. Mianowicie możemy obliczyć ilość kombinacji różnych wartości argumentów funkcji $count$. $ques$ może wynosić od 0 do 10, $rem$ od 0 do 2, a $first$ - 0 albo 1. Liczba kombinacji wynosi więc $11 \cdot 3 \cdot 2 = 66$. Możemy więc zrobić sobie 3-wymiarową tablicę, która w jednoznacznie opisywała dany zestaw argumentów i w komórce trzymałaby dla niej wynik. Dla każdego testu sprawdzamy komórkę w owej tablicy i jeśli nie jest ona pusta, to zwracamy wynik. W przeciwnym wypadku obliczamy wynik i zapisujemy go do tejże tablicy. Dzięki temu mamy pewność, że dany wynik obliczymy zawsze jedynie raz.

Złożoność: $O\left(3^n\right)$, bo jeśli już wywołamy funkcję $count$ to wykonamy taką samą ilość operacji jak w poprzednim algorytmie. Jednak jeśli wziąć pod uwagę liczbę testów, która może być rzędu miliona, to okaże się, że amortyzowany czas operacji jest stały. Innymi słowy, jeśli będziemy mieli dużo testów to jeśli zsumujemy wszystkie ilości operacji dla każdego testu, a następnie podzielimy tę liczbę przez liczbę testów to wyjdzie nam liczba bardzo mała.

Algorytm:

int count(int ques, int rem, int first)
{
        if(ques == 1) // jeśli pozostał jeden ? - warunek graniczny
                return rem < 1 && !first ? 4 : 3;
        return count(ques-1, rem, 0)*(first ? 3 : 4) + count(ques-1, (rem+2)%3, 0)*3 + count(ques-1, (rem+1)%3, 0)*3;
}
int main()
{
        char in[19];
        int len = strlen(in), ques = 0, sum = 0, tab[2][3][11];

        get(in);
        for(int i = 0; i < len; ++i)
                ques += in[i] == '?',
                sum += in[i] == '?' ? 0 : in[i]-'0';
        if(!ques) // jeśli nie ma znaków zapytania w ciągu
                print(sum%3 == 0); // sprawdzamy czy jest podzielna przez 3
        else if(ques == 1 && len < 2) // osobny przypadek dla in="0"
                print(4);
        else if(tab[*in == '?'][sum%3][ques]) // jeśli mamy wynik w tablicy
                print(tab[*in == '?'][sum%3][ques]);
        else
                tab[*in == '?'][sum%3][ques] = count(ques, sum%3 < 1 ? 0 : 3-sum%3, *in == '?'),
                print(tab[*in == '?'][sum%3][ques]);
}

Rozwiązanie najsprytniejsze:

W poprzednim algorytmie średnia złożoność jest stała. Jak jeszcze można to przyspieszyć? Ano możemy pominąć obliczanie wartości $count$ dla jakiejkolwiek wartości, bo wynik dla każdej kombinacji możemy sobie obliczyć lokalnie, u siebie na komputerze, a następnie owe 66 wartości stablicować i umieścić jawnie w programie owe wartości.

Złożoność: $O(1)$ dla każdego testu, bo sprawdzamy tylko wartość komórki w tablicy 3-wymiarowej.