BitCell

Poveste:
Nineta este angajata NASA . Principala ei ocupatie este sa analizeze semnalele radio venite din spatiu .
In fiecare dimineata primeste de la sefi liste de milioane de numere aparent aleatoare iar ei ii revine sarcina sa gaseasca un "pattern" .

Nu a progresat foarte mult si nici nu crede in extraterestri, dar a gasit "o anomalie" pe care doreste sa o tina sub observatie, anume:

"Submultimea numerelor prime din multimea totala de numere are un element majoritar." Adica exista un numar prim "special" care se repeta de mai mult de P/2 ori, unde P reprezinta dimensiunea submultimii numerelor prime .

Ajut-o pe Nineta sa gaseasca acest numar prim majoritar .

Date de intrare ("bitcell20.in"):
Un fisier ce contine M linii, pe fiecare linie exista un singur numar N "aparent" aleator .
Cunoasteti (fara a fi nevoie sa validati) ca exista in mod cert un numar prim "majoritar" .

Date de iesire "bitcell20.out":
O singura linie ce contine valoarea numarului prim majoritar .

Limitari:
0 <= N <= 10 000 000 (intervalul in care se gasesc numerele "aparent" aleatoare)
10 <= M <= 5 000 000 (numarul total de numere "aparent" aleatoare)

Exemplu:
Date de intrare:

Date de iesire:


Explicatii:
Din multimea de numere "aparent" aleatoare primite de Nineta, avem o submultime de numere prime: {3, 3, 2, 5, 5, 3, 3, 3, 7} de dimensiune 9 . Observam ca numarul prim 3 se repeta de cele mai multe ori (5 ori), iar 5 > 9/2 => 3 este numarul prim majoritar.

Timp de lucru:
Data inceput : 22/11/2011
Data finalizare: 1/12/2011
Desemnare castigator: 2/11/2011

Altele:
"Problema" nu e total originala ci combina doua exercitii clasice .
"Dificultatea" consta in optimizarea solutiei pentru numerele mari .

O intrebare, conditia nº de aparitii > P/2 e obligatorie? De exemplu avem 50 de numere prime si numarul prim cu cele mai multe aparitii are 20 de aparitii in total.

nomemory wrote:Cunoasteti (fara a fi nevoie sa validati) ca exista in mod cert un numar prim "majoritar" .

@Payne, da e o obligatoriu . In datele de intrare exista in mod cert un astfel de numar . Daca dimensiunea submultimii de numere prime este 50, poti sa te bazezi linistit pe faptul ca unul din elemente apare de minim 26 de ori .

S-ar putea sa ne pui la dispozitie un fisier cu numere mai mare?


Vin cu varianta mea in -> http://filebeam.com/9ab7308e4cd85d7eb6e0bca253198e43


L.E Codul sursa cui il trimitem?

Poti sa mi-l trimiti mie daca vrei .
Fac maine niste teste mai convingatoare si urc aici fisierele .

Daca faci testele ar fi bine sa specifici cam care este timpul de raspuns asteptat pentru fiecare test.

Fisierele de test:

Fisierul 0
t0_numbers_10000_primes_3000_majority_1600_answer_13.in

Fisierul1
t1_numbers_1000000_primes_100000_majority_60000_answer_5.in

Fisierul 2
t2_numbers_1000000_primes_500000_majority_250001_answer_7.in

Fisierul 3
t3_numbers_5000000_primes_2000000_majority_1000500_answer_11.in

Numele fisierului ne da informatii despre ce se gaseste in interior:


(Ca sa le salvati: Save Link As .
Unele sunt foarte mari)

PS:
Incercati sa scoateti timpi de sub 2 secunde (depinde mult de calculator...) pentru 5 milioane de numere .

Mie pe ultimul test imi da si timpul de executie este mizerabil pe masina mea. (in jur de 4,4 sec) Acum ma pun pe optimizari insa nu prea am ce sa optimizez. [I'm gonna die.]

E OK sa ai 4 secunde .
Aici e solutia mea, cat dureaza la tine rularea ? (Trebuie sa existe un fisier bitcell20.in in acelasi folder cu executabilul) .

Aici este si solutia mea. (oricine are timp si poate sa imi ataseze si mie executabilul- nu este valabil foarte mult link-ul de pe speedy share)

---

L.E. (-- 22 Nov 2011, 23:10 --)

^ Pana la urma la testul cu cinci milioane de numere sunt 1000500 majoritare sau 1000502? Solutia ta ruleaza la mine tot cam in 4 secunde.

^ La mine merge in doua secunde, si e mai rapida decat solutia pe care o am eu cu cateva zeci de milisecunde, so nice .

Later Edit:
Am mers putin mai extrem si am ajuns la solutia asta. E putin mai rapida .

^La cat e de mare fisierul, am o mica mare impresie ca ai bagat in el destule valori pre-calculate.

^ Am incercat .

Am sa plec zilele urmatoare din oras si cel mai probabil nu o sa am acces la internet pana pe 4 Decembrie .
Probabil aceea va fi data cand va fi desemnat si castigatorul .

Le multumesc celor doi participanti ca au ajutat-o pe Nineta .

Rezultatele pe baza sursele compilate local pe calculatorul meu folosind acelasi compilator (pentru o departajare mai exacta):
Testul 1 (10 000 de numere)
cata - 0.445 s - corect
payne - 0.034 s - corect

Testul 2 (100 000 de numere)
cata - 0.898 s - corect
payne - 0.547 s - corect

Testul 3 (500 000)
cata - 0.569 s - corect
payne - 1.618 s - corect

Testul 4 (5 000 000)
cata - 1.934 s - corect
payne - 7.254 s - corect

Surse:
payne


cata


Ideea principala a problemei era sa combinam unul dintre algoritmi de tip sita (Atkin sau Eratostene) cu un algoritm de determinare a majoritatii (ex.: aici) .

Daca voiati sa trisati, puteati sa folositi un truc vechi (aplicabil in C/C++): - se precalcula o lista de numere prime si se includea in sursa cu #include in felul urmator:


(Executabilul rezultat era insa cam mare, in plus pe windows s-ar putea sa fi fost probleme cu dimensiunea stack-ului - poate da stack overflow) .

Ambele solutii au fost foarte interesante (solutia mea initiala era mai infecienta decat ale voastre simtitor), dar pentru ca rezolvarea lui cata45 se descurca mai bine atunci cand limitele intervalelor cresc, il declar pe cata45 castigator .

PS: Imi cer scuze de intarziere ...

Foarte interesant algoritmul lui Atkin. Nu stiam de el. Deci am invatat ceva nou .
Multumim pentru problema nomemory. Ne bucuram ca am putut sa o ajutam pe Nineta.

Frumos concurs si felicitari cata45. Astept urmatorul cu nerabdare.