765 Dictree

[•filipb]

Aici puteti discuta despre problema Dictree.

[•Kid0]

Salut, un hint ceva despre cum ar trebui rezolvat?

Folosesc o structura de date

Cod:

typedef struct _nod
{
	char info;
	_nod *fiu;
	_nod *frate;
} nod;

dar depaseste memoria maxima alocata cu 200-300k.

Ideea este ca fiii unui nod sunt fratii primului fiu si deci *frate va fi o lista de fii. Am incercat si cu __attribute__((__packed__)) dar nu a redus cu prea mult dimensiunea.

[•gabitzish1]

Si eu am incercat cu construirea efectiva a arborelui si a iesit din memorie. Incearca sa retii cuvintele intr'o matrice, le sortezi, apoi vezi care se suprapun si numeri cate litere trebuie introduse in arbore.

[•Kid0]

Mersi.
A mers intradevar asa. Desi asta a fost si prima mea idee de rezolvare, traiam cu impresia ca sortarea tabelei de cuvinte dureaza prea mult si ca nu se va incadra, si de aceea am trecut la crearea arborelui, care din ce am observat este ceva mai rapid.
Insa si std::sort se descurca bine. Oare un radixsort s-ar descurca mai bine?

[•alex_mircescu]

Am si eu o intrebare... 
Cum pot sorta un vector de stringuri ?? 

Am incercat asa ceva in program:

Cod:

int cmp(const void *a, const void *b) {
	return *(char *)a - *(char *)b;
}
.............
.............
//apelarea
qsort(v + 1, n, sizeof(v[0]), cmp);
.............

Nu sorteaza cum trebuie (lexicografic)... AJUTOR?   

[•sima_cotizo]

Slabe sanse sa reusesti cu qsort din stdlib. Poate cu sort-ul din algorithm + clasa string, dar cred ca e prea mare bataia de cap.

Eu as asocia vectorului tau de stringuri un "vector de pozitii" O, care are semnificatia ca daca ordonez vectorul de stringuri, voi avea pe pozitia i stringul O[ i ]. Initial, O[ i ] = i. Folosesc o functie de sortare (acum merge si qsort), cu o functie de comparare de genul:

Cod:

int compare( int a, int b ) {
     return strcmp(S[a],S[b]);           // S este vectorul de stringuri
}

Un exemplu:

Cod:

Initial:
S                O
----------------------
mama             1
tata             2
amam             3
atat             4

Cod:

Dupa sortare:
S                O
----------------------
amam             3
atat             4
mama             1
tata             2

Sper ca poti adapta ideea nevoilor tale

[•zloteanu.adrian]

cum pot sa sortez rapid primul element al fiecarei linii dintr-o  matrice(int)?

[•PavelRazvan]

Un exemplu valoreaza cat 1000 de cuvinte.

Corect

[•otilia_s]

Puteti sa imi dati si mie va rog inca un exemplu, poate unul mai special? Nu reusesc sa imi dau seama unde greseste rezolvarea mea.  Folosesc cam aceeasi idee, cea cu sortarea.

[•SpiderMan]

Uite niste exemple, sper sa te ajute :

Cod:

10
sdlgfnsdigbsdibgisdfsdfsdfsdfsdfdsfdsfds
dsfsdfsdsdifbgsduusidbiusdgsdgsdgsdg
sdgs
dgsdgsdgsdgsdgsgsdgsdgsdgsdgsdg
cghuinsdugbsdugsgsdg
sdg
sdgsdgsgdsgdsgdgsdsgdsgdgsdgsdsgd
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
sdsdgjsiogsdgnisongsiodgsd
jkjjjjjgjsdgsdg

----------------------

12
a
b
c
d
e
f
g
h
i
j
k
l

Cod:

229

---

13

Iar aici unul mai mare :  http://www.2shared.com/file/GjzZL2DP/Desktop.html

[•belginstirbu]

Dacă toate cuvintele încep cu aceeași literă, nu cred că mai trebuie adăugată acea rădăcină neetichetată, deoarece rădăcina poate fi un nod cu prima literă a cuvintelor. Eu am rezolvat ținând cont de acest lucru și programul a picat testul 2 (restul le-a trecut). Când am modificat programul astfel încât să adauge acea rădăcină neetichetată în orice caz, a trecut și testul 2.

[•PlayLikeNeverB4]

Muchiile sunt etichetate cu litere, nu nodurile.

[•ctlin04]

A luat cineva 100 in pascal cu asa limita de timp?? Daca nu cred ca ar trebui putin marita limita pentru ca solutia care intra in timp scrisa in cpp sa intre in timp si in pascal 

[•Schumi]

I-a intrat cuiva in memorie solutia care foloseste trie?

[•klamathix]

Nu. Solutia asta nu ia punctaj maxim.

[•Schumi]

Multumesc  Am bagat solutia cu sortare si a mers.

[•Magnvs]

vedeti ca pe pagina http://infoarena.ro/problema/dictree la "scorul tau" arata tot timpul n/a.

[•superman_01]

tot ma chinui la problema asta si nu imi dau seama ce gresesc(iau Incorect pe un test) +2TLE...ma poate ajuta cineva sa cu o optimizare?
Multumesc anticipat!

[•repp4radu]

Citeste sirul intreg, nu caracter cu caracter.

[•superman_01]

pai il citesc linie cu linie. Cum ar trebui sa citesc ca un sir intreg ?

[•repp4radu]

Scuze, nu am fost atent ca c este un sir de caractere .

[•superman_01]

si al idee de optimizare  ?Eu ma gandeam sa tin minte indicii si sortez indicii dar nu stiu cum sa sortez indicii tinand cont ca ar trebui sa compar 2 string-uri.Am incercat si cum zice mai sus Cotizo,dar nu mi-a mers.

L.E. mi-a iesit pana la urma.Uitam sa pun niste conditii in while