|
Titlul: 765 Dictree Scris de: Filip Cristian Buruiana din Septembrie 13, 2008, 15:13:38 Aici puteti discuta despre problema Dictree (http://infoarena.ro/problema/dictree).
Titlul: Răspuns: 765 Dictree Scris de: Shizzle Nizzle din Octombrie 10, 2008, 23:10:54 Salut, un hint ceva despre cum ar trebui rezolvat?
Folosesc o structura de date Cod: typedef struct _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. Titlul: Răspuns: 765 Dictree Scris de: Gabriel Bitis din Octombrie 10, 2008, 23:32:03 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.
Titlul: Răspuns: 765 Dictree Scris de: Shizzle Nizzle din Octombrie 11, 2008, 16:13:15 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? Titlul: Răspuns: 765 Dictree Scris de: Alex Mircescu din Noiembrie 06, 2008, 17:57:49 Am si eu o intrebare... :?
Cum pot sorta un vector de stringuri ?? :oops: Am incercat asa ceva in program: Cod: int cmp(const void *a, const void *b) {Nu sorteaza cum trebuie (lexicografic)... AJUTOR? :sad: Titlul: Răspuns: 765 Dictree Scris de: Sima Cotizo din Noiembrie 06, 2008, 20:26:05 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 ) {Un exemplu: Cod: Initial: Cod: Dupa sortare: Sper ca poti adapta ideea nevoilor tale ;) Titlul: Răspuns: 765 Dictree Scris de: zloteanu adrian nichita din Septembrie 12, 2009, 15:02:17 cum pot sa sortez rapid primul element al fiecarei linii dintr-o matrice(int)?
Titlul: Răspuns: 765 Dictree Scris de: Pavel Razvan din Decembrie 07, 2009, 18:26:33 Citat Un exemplu valoreaza cat 1000 de cuvinte. Corect :ok:Titlul: Răspuns: 765 Dictree Scris de: Otilia Stretcu din Martie 15, 2010, 18:59:07 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. :?
Titlul: Răspuns: 765 Dictree Scris de: Simoiu Robert din August 19, 2010, 12:44:21 Uite niste exemple, sper sa te ajute :
Cod: 10 Cod: 229 Iar aici unul mai mare : http://www.2shared.com/file/GjzZL2DP/Desktop.html (http://www.2shared.com/file/GjzZL2DP/Desktop.html) Titlul: Răspuns: 765 Dictree Scris de: asdf asdf din Iunie 18, 2012, 10:08:34 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.
Titlul: Răspuns: 765 Dictree Scris de: George Marcus din Iunie 18, 2012, 18:45:13 Muchiile sunt etichetate cu litere, nu nodurile.
Titlul: Răspuns: 765 Dictree Scris de: UAIC.VlasCatalin din Iunie 18, 2012, 18:58:34 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 :? :x
Titlul: Răspuns: 765 Dictree Scris de: Dumitru Andrei Georgian din Iulie 11, 2012, 12:40:11 I-a intrat cuiva in memorie solutia care foloseste trie?
Titlul: Răspuns: 765 Dictree Scris de: Mihai Calancea din Iulie 11, 2012, 12:43:01 Nu. Solutia asta nu ia punctaj maxim.
Titlul: Răspuns: 765 Dictree Scris de: Dumitru Andrei Georgian din Iulie 11, 2012, 13:16:29 Multumesc :D Am bagat solutia cu sortare si a mers.
Titlul: Răspuns: 765 Dictree Scris de: Daniel Constantin Anghel din Februarie 11, 2013, 21:06:06 vedeti ca pe pagina http://infoarena.ro/problema/dictree (http://infoarena.ro/problema/dictree) la "scorul tau" arata tot timpul n/a.
Titlul: Răspuns: 765 Dictree Scris de: Avramescu Cristian din Martie 29, 2013, 20:33:37 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! Titlul: Răspuns: 765 Dictree Scris de: Radu-Andrei Szasz din Martie 29, 2013, 22:40:07 Citeste sirul intreg, nu caracter cu caracter.
Titlul: Răspuns: 765 Dictree Scris de: Avramescu Cristian din Martie 30, 2013, 00:04:23 pai il citesc linie cu linie. Cum ar trebui sa citesc ca un sir intreg ? :D
Titlul: Răspuns: 765 Dictree Scris de: Radu-Andrei Szasz din Martie 30, 2013, 09:03:06 Scuze, nu am fost atent ca c este un sir de caractere :).
Titlul: Răspuns: 765 Dictree Scris de: Avramescu Cristian din Martie 30, 2013, 09:14:40 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 :D |