O solutie naiva, dar eficienta ar fi sa luam cateva nume votate aleatoare din sir. Cum castigatorul apare ca optiunea a multi votanti, daca alegem destul de multe valori din sirul optiunilor vom da cu probabilitate mare peste castigator. Cand alegem un nume aleator avem probabilitatea $p > 1/3$ ca am ales numele viitorului castigator. Deci daca alegem k valori vom avea un timp de executie de ordinul $O(kn)$ pentru a verifica daca una dintre cele $k$ valori e cea buna si probabilitatea de a gasi peresedintele mai mare de $1 - (1/3)^k^$.

Alta idee vine de la faptul ca in sirul sortat, elementele de valori egale vor fi pe pozitii consecutive. Astfel numele presedintelui va aparea pe cel putin $n/3 + 1$ pozitii consecutive. Deci numele presedintelui va aparea sigur pe cel putin una din pozitiile $n/3$ sau $2n/3$ din sir. Astfel putem folosi un algoritm de selectie pentru a gasi in $O(n)$ elementele de pe pozitiile n/3 si 2n/3 si apoi in $O(n)$ putem verifica care dintre acesti doi candidati au castigat.

Alta idee vine de la faptul ca in sirul sortat, elementele de valori egale vor fi pe pozitii consecutive. Astfel numele presedintelui va aparea pe cel putin $n/3 + 1$ pozitii consecutive. Deci numele presedintelui va aparea sigur pe cel putin una din pozitiile $n/3$ sau $2n/3$ din sir. Astfel putem folosi un algoritm de selectie pentru a gasi in $O(n)$ elementele de pe pozitiile $n/3$ si $2n/3$ si apoi in $O(n)$ putem verifica care dintre acesti doi candidati au castigat.

Daca n nu depaseste un milion, putem la fiecare pas sa incrementam pentru candidatul votat $x$ numerele $a[x / 1000]$ si $b[x % 1000]$. Acum pentru a determina candidatul castigator, gasim valoarea $p$ cu $a[p] > n/3 + 1$ si valoarea $q$ cu $b[q] > n/3 + 1$, iar castigatorul va fi $p * 1000 + q$.

      altfel daca x = a[i] atunci counter_x++;
      altfel daca y = a[i] atunci counter_y++;
          altfel

           // am gasit un grup de trei alegatori cu optiuni
           // diferite pe care il eliminam
           // x != a[i] si y != a[i]

           // am gasit un grup de trei alegatori cu optiunile
           // x, y si a[i] pe care il eliminam
           // x != a[i], y != a[i] si x != y

           counter_x--, counter_y--;
verificam daca x sau y este elementul cautat.
==

_Problema poate parea artificiala, dar reformulata in aceea de a gasi in mod eficient queriuri foarte frecvente(ce apar de $n/k$ ori) pentru un motor de cautare devine mai interesanta si practica. Articolul a fost inspirat din articolul "Problema majoritatii votului" ce l-am publicat in Ginfo, iar partea cu cearta intre alegatori din R. S. Boyer, J. S. Moore A Fast Majority Vote Algorithm_

_Problema poate parea artificiala, dar reformulata in aceea de a gasi in mod eficient queriuri foarte frecvente(ce apar de $n/k$ ori) pentru un motor de cautare devine mai interesanta si practica. Postul a fost inspirat din articolul "Problema majoritatii votului" ce l-am publicat in Ginfo, iar partea cu cearta intre alegatori din R. S. Boyer, J. S. Moore A Fast Majority Vote Algorithm_

==BlogCommentCount(topic_id="2350")==

2350