876 Nums

[•DITzoneC]

Aici puteţi discuta despre problema Nums.

[•DITzoneC]

Problema a fost scoasa temporar din arhiva.
Revenim intr-o zi, doua.

[•Dastas]

Am facut problema cu arbori de intervale. Daca trimit numai citirea si sortarea, imi ia cam jumatate de timp. Folosesc sort din STL. Cum as putea sorta mai rapid niste stringuri?

[•wefgef]

In solutia oficiala nu trebuie sa sortezi stringurile.

[•pauldb]

Am facut problema cu arbori de intervale. Daca trimit numai citirea si sortarea, imi ia cam jumatate de timp. Folosesc sort din STL. Cum as putea sorta mai rapid niste stringuri?

Incearca Radix Sort. Solutia oficiala se baza pe o particularitate a testelor si acum cel mai probabil nu mai obtine punctaj maxim.

[•bogdan2412]

O sursa care sorteaza stringurile cu sort din STL si apoi foloseste arbori indexati binar pentru mentinerea seturilor de numere obtine 90 de puncte, desi in concurs aceeasi sursa a obtinut 60 de puncte.

Mai trebuie umblat un pic la teste. Am observat ca nu sunt folosite aceleasi teste ca in concurs, probabil au fost refacute pentru a determina alte surse proaste sa pice Trebuie facute cateva teste special si pentru a pica sursa mea.

[•APOCALYPTO]

Salut!
Cate puncte iau cu o padure de trie-uri?

[•stocarul]

Încearcă și vei vedea.
Dar cred că dacă faci un arbore binar echilibrat pentru lungimile numerelor, iar în fiecare nod al arborelui ți un trie cu numerele ce au lungimea nodului vei obține 100 :p

LE: Da, un Treap cu Trie în noduri 

[•toni2007]

Practic ti treap cu trie in noduri nu ? Pana si mie mi s-a parut jeg sa bag asta  .

[•Mishu91]

Pentru 100 poți sorta numerele date, iar apoi ții nu AIB/ArbInt pentru a răspunde la query-uri(evident, parcurgând încă odată operațiile în ordinea în care apar). Implementarea astea nu este așa scârboasă, dar parcă nici cea mai ortodoxă nu este. 

[•APOCALYPTO]

Pai eu de fapt vreau sa implementez cat mai multe solutii la problema asta pentru ca e numai buna pentru antrenament si pot folosi o mare parte din structurile de date avansate pe care le cunosc.
Nu ma intereseaza punctele ci antrenamentul in sine.
O sa implementez varianta cu treapuri si trie-uri maine. Azi am implementat un vector in care tin fiecare trie si se pare ca obtin 55 si uneori se obtine si 60 depinde de cum ruleaza evaluatorul la momentul respectiv.
Multumesc pentru raspunsuri!

[•blasterz]

Pentru 100 poți sorta numerele date, iar apoi ții nu AIB/ArbInt pentru a răspunde la query-uri(evident, parcurgând încă odată operațiile în ordinea în care apar). Implementarea astea nu este așa scârboasă, dar parcă nici cea mai ortodoxă nu este.  

Daca problema era interactiva nu mergea solutia cu sortatul

Încearcă și vei vedea.
Dar cred că dacă faci un arbore binar echilibrat pentru lungimile numerelor, iar în fiecare nod al arborelui ți un trie cu numerele ce au lungimea nodului vei obține 100 :p

LE: Da, un Treap cu Trie în noduri 

Ai luat 100 pe infoarena cu Treap cu Trie-uri?

Eu am luat 75. imi iese din memorie (testele de la oni trec totusi).

[•sharky12592]

Imi puteti spune va rog unde pot gasi solutia oficiala in Pascal de la aceasta problema ? Multumesc.

[•costyv87]

Poate sa'mi spuna cineva care este solutia buna? Adica cum tre sa implementez. Daca fac chestia cu noduri pentru fiecare lungime si sa tin cate un trie pentru fiecare nod nu'mi intra in memorie pe cateva teste. 

[•dushmi]

Doar solutia cu treap-uri mai intra in timp acum???

[•darkseeker]

Ar trebui putin marita limita de memorie a acestei probleme .. eu am o solutie cu trie si aib , fac query pe aib ca sa aflu cate cifre are al k-lea nr din trie la momentul curent , si ia mle pe 5 teste . Daca lista de fii ptr fiecare nod din trie in mod dinamic , ia mle pe un test si tle pe 2 teste . Solutia cu lista de fii alocata static merge f bine ca timp . Rog un admin sa se uite putin peste limitele problemei . Multumesc anticipat .

[•SpiderMan]

Prea stransa limita de timp, am trimis o sursa de 100 pct. si ia 55 parca, am trimis si la limite de timp ....