|
Titlul: 428 Ghicit Scris de: Airinei Adrian din Aprilie 25, 2007, 09:27:34 Aici puteţi discuta despre problema Ghicit (http://infoarena.ro/problema/ghicit).
Titlul: Răspuns: 428 Ghicit Scris de: Florian Marcu din Aprilie 25, 2007, 09:38:03 Nu pot deschide problema...nu am permisiuni suficiente...nu e finalizata?? :-k
Titlul: Răspuns: 428 Ghicit Scris de: Chis Raoul din Martie 06, 2008, 11:56:02 Foarte dubios ... cu un radix sort iau 60p si pe 8 teste TLE, iar cu sort din STL 95p si un singur TLE
Titlul: Răspuns: 428 Ghicit Scris de: Florin Pogocsan din Aprilie 13, 2008, 20:53:59 Am incercat si eu cu radix sort, dar nu am reusit sa il fac mai eficient decat STL sort [numa cu sortul asta am luat 100]. Am testat radix sort implementat iterativ si si recursiv dar nu s-au observat mari diferente de timp.
Titlul: Răspuns: 428 Ghicit Scris de: Musina Rares din Aprilie 24, 2008, 08:32:32 Citat Obtinem sirul sortat de sufixe in O(n lg n), dupa care cautam pozitia in care fiecare pereche de sufixe consecutive difera (folosind functia lcp) si adunam la solutie restul caracterelor Poate sa clarifice cineva explicatia asta? E luata din articolul cu suffix arrays si nu prea inteleg care-i faza cu pozitia in care fiecare pereche de sufixe consecutive difera... :? Titlul: Răspuns: 428 Ghicit Scris de: Lucian Boca din Aprilie 24, 2008, 10:30:33 Ca sa iei in calcul toate subsecventele, trebuie sa studiezi toate prefixele tuturor sufixelor. Sunt totusi subsecvente comune, pe care nu trebuie sa le numeri de doua ori, iar acestea apar ca prefixe comune ale sufixelor consecutive.
Lungimea prefixelor comune dintre sufixele consecutive (consecutive in lista de sufixe sortate) le tii intr-un tabel lcp[], pe care il poti construi in paralele cu sortarea sufixelor (vezi in articol). Titlul: Răspuns: 428 Ghicit Scris de: Musina Rares din Aprilie 24, 2008, 11:32:58 mersi mult :peacefingers: in principiu am inteles sa vedem cum e cu implementarea :)
Titlul: Răspuns: 428 Ghicit Scris de: George Marcus din Octombrie 25, 2012, 00:04:22 Cum se construieste lcp[] in paralel cu sirul de sufixe?
Titlul: Răspuns: 428 Ghicit Scris de: Andrei Grigorean din Octombrie 25, 2012, 15:26:13 Poti afla mai multe despre suffix arrays in acest articol (http://infoarena.ro/siruri-de-sufixe).
Titlul: Răspuns: 428 Ghicit Scris de: George Marcus din Octombrie 25, 2012, 15:40:47 Am citit articolul, insa nu cred ca imi raspunde la intrebare. Am facut cum zice in articol, dar iau TLE.
Titlul: Răspuns: 428 Ghicit Scris de: Pirtoaca George Sebastian din Martie 16, 2013, 17:37:48 Cred ca ar trebui marita putin limita de timp. Cu O(N * log2 N) iau 90 cu 2 TLE si am inteles ca radix sort merge mai incet la problema asta decat sort din STL. Multumesc!
Titlul: Răspuns: 428 Ghicit Scris de: Dan H Alexandru din Septembrie 21, 2013, 17:05:30 E buna limita de timp ? Iau TLE cu O(N log^2 N). Am inteles ca radix merge mai incet in practica asa ca nu am mai implementat si varianta aceasta.
Titlul: Răspuns: 428 Ghicit Scris de: Mihai Calancea din Septembrie 21, 2013, 17:25:03 Am marit limita.
Titlul: Răspuns: 428 Ghicit Scris de: Valentin Valeanu din Februarie 19, 2015, 20:55:37 Ar putea sa se uite cineva la sursa mea,primesc 50 de puncte si chiar nu stiu ce gresesc,multumesc anticipat :annoyed:
Titlul: Răspuns: 428 Ghicit Scris de: Vlad Dumitru-Popescu din Aprilie 29, 2016, 00:47:14 Pentru oricine nu intelege de ce are 80p si WA pe primele si ultimele teste: sirul poate contine si whitespace ... Pentru mine s-a rezolvat trecand de la citire standard cu streamuri la getline.
Titlul: Răspuns: 428 Ghicit Scris de: Vlad Rochian din Mai 01, 2016, 20:26:27 Pentru oricine nu intelege de ce are 80p si WA pe primele si ultimele teste: sirul poate contine si whitespace ... Pentru mine s-a rezolvat trecand de la citire standard cu streamuri la getline. Cine e atent la restricții se prinde |