Problema 7 (Jocul vietii) a fost intr-o anumita masura un esec, mai
ales pentru cei care n-au trimis nici o sursa. Imi pare foarte rau si
promit ca pe viitor sa postez numai probleme cu teste "urate" gata
facute. Care a fost buba: aceasta problema nu are teste "urate", in
sensul ca orice configuratie cu N<=100 celule, ori se stabilizeaza in
maximum 16 iteratii, ori nu se stabilizeaza.
Totusi, iata algoritmul "destept", care are complexitate O(N^2) nu
O(N^3), lucru pe care l-am descoperit cu stupoare scriind programul.
Mai mult, raspunsul la intrebarea daca o colonie se stabilizeaza se
poate da in O(N).
Ideea de pornire este ca exista 2^N configuratii distincte de N
celule. Din acest motiv, conform principiului lui Dirichlet, este
evident ca dupa cel mult 2^N generatii configuratiile incep sa se
repete. Deci tot ce avem de facut este sa comparam generatia 2^N cu
generatia 2^N+1 si aflam daca (,) colonia se stabilizeaza.
Cum facem sa evoluam 2^N generatii ? Desigur, nu iterativ, ci evoluand
in salturi. Pentru aceasta, sa facem niste notatii: fie C[0]..C[N-1]
colonia originala si fie D[t][i] starea celulei i la momentul t.
Postulam ca:
D[2^k][i]=C[i-2^k] xor C[i+2^k] oricare k>=0
(aici indicii in C se iau modulo N).
Cu alte cuvinte, starea unei celule la momentul 1 este data de starea
originala a vecinilor ei; starea la momentul 8 este data de starea
originala a vecinilor ei de la 8 celule departare s.a.m.d.
Demonstratia se face prin inductie completa, desi dupa cum stim
programatorii se multumesc adesea cu inductia incompleta :) Deci:
1) Pentru k=0 propozitia este adevarata:
D[2^0][i]=C[i-2^0] xor C[i+2^0], adica D[1][i]=C[i-1] xor C[i+1],
ceea ce este adevarat.
2) Presupunem ca propozitia este adevarata pentru k si demonstram ca
este adevarata si pentru k+1. Pentru aceasta, remarcam ca generatia
de la momentul 2^(k+1) se obtine plecand din configuratia de la momentul
2^k si evoluand cu inca 2^k generatii:
C ----------------> D[2^(k+1)]
\ /
--> D[2^k] -->
Dar pentru 2^k iteratii afirmatia se verifica si putem scrie:
D[2^(k+1)][i]=D[2^k][i-2^k] xor D[2^k][i+2^k]
D[2^k][i-2^k]=C[i-2^k-2^k] xor C[i-2^k+2^k] = C[i-2^(k+1)] xor C[i]
D[2^k][i+2^k]=C[i+2^k-2^k] xor C[i+2^k+2^k] = C[i] xor C[i+2^(k+1)]
Din cele trei rezulta ca
D[2^(k+1)][i] = C[i-2^(k+1)] xor C[i] xor C[i] xor C[i+2^(k+1)]
= C[i-2^(k+1)] xor C[i+2^(k+1)] q.e.d.
Asadar pentru a calcula ceea ce ne intereseaza, si anume D[2^N],
scriem ca D[2^N][i]=C[i-2^N] xor C[i+2^N]. Nu va speriati ca 2^N are
vreo 30 de cifre cand N=100, pentru ca noua ne trebuie indicii (i-2^N)
modulo N si (i+2^N) modulo N, deci nu este nevoie de numere mari
(deocamdata).
D[2^N] se poate calcula in O(N) si astfel decidem daca (iar ,) colonia
se stabilizeaza. Presupunem ca se stabilizeaza - cum decidem in cat timp ?
Sa notam D[2^N] = S, configuratia in care incremeneste colonia. Acum
sa analizam sirul D[0]=C, D[1], D[2], ..., D[2^N].
Acest sir contine niste elemente diferite de S, apoi un sir de
elemente egale cu S, deoarece din clipa in care apare prima generatie
egala cu S, toate cele care ii urmeaza sunt egale cu S. Trebuie sa
aflam indicele primei generatii egale cu S. Aceasta se face prin
cautare binara. Intr-o prima faza, calculam D[2^(N-1)] si avem doua
variante:
- Daca D[2^(N-1)]=S, atunci colonia se stabilizeaza intr-un moment
anterior lui 2^(N-1);
- Daca D[2^(N-1)]<>S, atunci colonia se stabilizeaza intr-un moment
ulterior lui 2^(N-1);
Si asa mai departe. Teoretic, complexitatea se calculeaza astfel:
Numarul generatiei in care colonia se stabilizeaza este cuprins intre
0 si 2^N-1, deci are O(N) cifre. Adunarile pe asemenea numere se fac
in O(N).
Cautarea prin injumatatirea intervalului efectueaza log 2^N = N pasi.
Fiecare pas presupune o evolutie cu 2^tz generatii, care se face in
O(N), si eventual o adunare pe numere mari, deci inca O(N). Per total
O(N)*(O(N)+O(N))=O(N^2).
Cu "mica" observatie facuta la inceputul acestui mesaj, anume ca o
configuratie cu 100 celule se stabilizeaza in cel mult 16 iteratii,
putem reduce complexitatea la O(N). Dar asta-i alta poveste...
|
|
