|
•astronomy
|
 |
« : Aprilie 25, 2007, 09:27:34 » |
|
Aici puteţi discuta despre problema Ghicit. |
|
|
|
|
Memorat
|
|
|
|
|
•Florian
|
|
« Răspunde #1 : Aprilie 25, 2007, 09:38:03 » |
|
Nu pot deschide problema...nu am permisiuni suficiente...nu e finalizata??  |
|
|
|
|
Memorat
|
|
|
|
•raula_san
Strain
Karma: -23
 Deconectat
Mesaje: 32
|
|
« Răspunde #2 : 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
|
|
|
|
|
Memorat
|
{oo}
|
/\/\/\
\/\/\/
|
|
|
•Binary_Fire
Client obisnuit
Karma: 82
Deconectat
Mesaje: 87
|
|
« Răspunde #3 : 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.
|
|
|
|
|
Memorat
|
|
|
|
•cretu
Strain
Karma: 7
Deconectat
Mesaje: 15
|
|
« Răspunde #4 : Aprilie 24, 2008, 08:32:32 » |
|
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...  |
|
|
|
|
Memorat
|
I wuv C++.
|
|
|
•amadaeus
Client obisnuit
Karma: 28
Deconectat
Mesaje: 93
|
|
« Răspunde #5 : 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).
|
|
|
|
« Ultima modificare: Aprilie 24, 2008, 10:59:25 de către Lucian Boca »
|
Memorat
|
"one of these days I'm going to cut you into little pieces..."
|
|
|
•cretu
Strain
Karma: 7
Deconectat
Mesaje: 15
|
|
« Răspunde #6 : Aprilie 24, 2008, 11:32:58 » |
|
mersi mult  in principiu am inteles sa vedem cum e cu implementarea  |
|
|
|
|
Memorat
|
I wuv C++.
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #7 : Octombrie 25, 2012, 00:04:22 » |
|
Cum se construieste lcp[] in paralel cu sirul de sufixe?
|
|
|
|
|
Memorat
|
|
|
|
|
•wefgef
|
|
« Răspunde #8 : Octombrie 25, 2012, 15:26:13 » |
|
Poti afla mai multe despre suffix arrays in acest articol. |
|
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #9 : 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.
|
|
|
|
|
Memorat
|
|
|
|
|
•SebiSebi
|
|
« Răspunde #10 : 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!
|
|
|
|
|
Memorat
|
|
|
|
|
•danalex97
|
|
« Răspunde #11 : 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.
|
|
|
|
|
Memorat
|
|
|
|
|
•klamathix
|
|
« Răspunde #12 : Septembrie 21, 2013, 17:25:03 » |
|
Am marit limita.
|
|
|
|
|
Memorat
|
|
|
|
•valen.valentin
Strain
Karma: -2
Deconectat
Mesaje: 15
|
|
« Răspunde #13 : 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  |
|
|
|
|
Memorat
|
|
|
|
•depevlad
Strain
Karma: 13
Deconectat
Mesaje: 32
|
|
« Răspunde #14 : 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.
|
|
|
|
|
Memorat
|
|
|
|
•vladrochian
Strain
Karma: 25
Deconectat
Mesaje: 29
|
|
« Răspunde #15 : 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 |
|
|
|
|
Memorat
|
|
|
|
|
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena