Zadanie o szalonych liczbach

Witam, próbuję zrobić takie zadanie: http://main.edu.pl/user.phtml?op=showtask&task=sza&con=ALG
ale za nic nie mogę wymyślić sposobu na obliczenie liczby 'szalonych liczb'. Branie każdej liczby po kolei z zakresu jest zbyt wolne. Liczb takich jest zbyt dużo, żeby umieści wszystkie w tablicy. Musi być jakiś sposób obliczenia konkretnej liczby tych liczb, ale nie mogę znaleźć żadnych zależności.

o_O Przecież o to chodzi w takich zadaniach żebyś musiał pomyśleć. Na tym polegają konkursy i rywalizacja. Jak jest za trudne to przykro mi, idź lepić z plasteliny. Co ci da jeśli ktoś ci napisze rozwiązanie? Zero satysfakcji. Ja bym podszedł do tego tak:

• sprawdzenie czy liczba jest szalona można zrobić w czasie O(log10(n)) gdzie n to liczba którą sprawdzamy. Robimy to za pomocą zliczania, mamy tablicę

int tab[10]={};

I robimy sobie:

//int n to nasza liczba
while(liczba){
  int cyfra = n%10; //ostatnia cyfra liczby
  n/=10; //usuwamy ostatnią cyfrę
  tab[cyfra]++;
}
for(int i=1;i<10;i++)
  if(tab[i]>i)
    //błąd, ta liczba nie jest szalona

• takie sprawdzanie moze być za wolne wiec warto zauważyć że dwie kolejne liczby najczęściej różnią się ilościa wystąpień tylko jednej cyfry (tej która jest ostatnią cyfrą), dziesięciokrotnie rzadziej różnią się ilością wystąpień dwóch cyfr, dziesięciokrotnie rzadziej trzech etc.
  Zasadniczo mając policzone ile razy wystąpiły dane cyfry w jakiejś liczbie (jak w kroku pierwszym) i znając tą liczbę, jesteśmy w stanie dość łatwo policzyć ile i jakich cyfr ma liczba kolejna. Możemy to liczyć trochę tak jak dodaje sie pisemnie, do czasu aż występują "przeniesienia"

bool przeniesienie = true;
//int n to nasza liczba, int tab[10] to nasze cyferki
int liczba = n;
while(przeniesienie){
  int cyfra = n%10;
  if(cyfra<9){
    tab[cyfra]--;
    tab[cyfra+1]++;
    przeniesienie = false;
  }else{ //mamy 9 więc będzie przeniesienie
    tab[cyfra]--; //tab[9]--;
    tab[0]++;
    przeniesienie = true;
    liczba/=10; //usuwamy ostatnią cyfrę i idziemy dalej
  }
}

W ten sposób w czasie co najwyżej O(log10(n)) (a efektywnie w znacznie mniejszym) możemy policzyć sobie wystąpienie cyfr w kolejnej liczbie. Teraz wystarczy sprawdzić czy jest szalona (jedna pętlą pokazaną wyzej) i jeśli tak to podbić licznik.

Tyle że wtedy dostaje się w pesymistycznym przypadku O(n * log10(n)) operacji, czyli w przybliżeniu 2 * 10⁹ * log10(2 * 10⁹) = ok. 18 600 000 000 opereacji, zaś main-owe komputery nie są niestety superwydajnymi klastrami.

Wydaje mi się, że trzeba byłoby sprawdzić każdą możliwą kombinację zbioru zawierającego liczby cyfr: ({1, 0, ...}, {0, 1, ...}, {0, 2, ...}, ..., {1, 0, ...}, {1, 1, ...}, {1, 2, ...}, ...} Zdaje mi się, że liczbę akceptowalnych rozwiązań dla danego zbioru można załatwić w czasie O(k). Dostalibyśmy złożoność O(k * k!) w zależności od k - liczby różnych cyfr (=9), co jest akceptowalną złożonością.

@up no chyba nie za bardzo. Musisz wygenerować sobie wszystkie permutacje wszystkich podzbiorów, więc O(k* 2^k * k!)
Faktycznie złożoność mojego algorytmu wąskie gardło ma tylko w procedurze sprawdzania czy liczba jest szalona czy też nie, która zabiera O(log(n)) czasu. Myśle że dałoby się zapamiętać dla poprzedniej liczby gdzie nam brakowało / gdzie bylo za dużo i w chwili wyliczania nowych wartości w tablicy od razu sobie to policzyć. W ten sposób mamy złożoność rzędu:
O(1)+2O(1)+3O(1)+...+O(log10(n))*O(1) = 1+2+3+...+log10(n) = 1+2+3+...+9; dla każdej liczby
Czyli w efekcie algorytm jest liniowy względem ilości liczb w przedziale do przeszukania.

Algorytm liniowy to chyba wciąż za dużo i dla wartości dwóch miliardów algo będzie się wykonywać dobre kilkanaście/kilkadziesiąt? sekund. A w moim przykładzie trzeba zauważyć, że przecież:

• ilość wystąpień cyfry "1" nie jest większa niż 1, jest więc ze zbioru {0, 1} o liczności 2,
• ilość wystąpień cyfry "2" nie jest większa niż 2, jest więc ze zbioru {0, 1, 2} o liczności 3 itd.
  Otrzymujemy liczbę permutacji 23...*10 = 10! = 3628800. Tylko problemem tutaj byłoby znalezienie ilości liczb pasujących do wzorca.

@Shalom Po pierwsze to jest zadanie z kursu algorytmiki, a nie z konkursu. Po drugie sam sposób sprawdzenia, czy liczba jest szalona już miałem napisany. Tylko właśnie o to chodzi żeby znaleźć jakiś szybki algorytm do liczenia liczby takich liczb.

Dzięki za pomysły, spróbuję nad tym pokombinować, ale jak co jeszcze wymyślicie to piszcie

Odwróć warunek - policz ilość nie szalonych liczb.

Rozwiązałem to w końcu umieszczając w tablicy liczbę szalonych liczb z danego zakresu (co 1mln). Sam program liczył od 'a' do najbliższej wielokrotności mln i na odwrót do 'b', a zakres pomiędzy dodawał z tablicy.

Tak też można :D
Jednak prościej byłoby zauważyć, że aby policzyć ilość liczb od p do q, możesz prościej policzyć ilości liczb:

• od 1 do q,
• od 1 do p-1
  a potem te dwie wartości odjąć - zostanie ilość liczb w zakresie od p do q. A liczyć od 1 będzie zdecydowanie łatwiej.