428 Ghicit

[•astronomy]

Aici puteţi discuta despre problema Ghicit.

[•Florian]

Nu pot deschide problema...nu am permisiuni suficiente...nu e finalizata?? 

[•raula_san]

Foarte dubios ... cu un radix sort iau 60p si pe 8 teste TLE, iar cu sort din STL 95p si un singur TLE

[•Binary_Fire]

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.

[•cretu]

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...

[•amadaeus]

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).

[•cretu]

mersi mult in principiu am inteles sa vedem cum e cu implementarea

[•PlayLikeNeverB4]

Cum se construieste lcp[] in paralel cu sirul de sufixe?

[•wefgef]

Poti afla mai multe despre suffix arrays in acest articol.

[•PlayLikeNeverB4]

Am citit articolul, insa nu cred ca imi raspunde la intrebare. Am facut cum zice in articol, dar iau TLE.

[•SebiSebi]

Cred ca ar trebui marita putin limita de timp. Cu O(N * log² N) iau 90 cu 2 TLE si am inteles ca radix sort merge mai incet la problema asta decat sort din STL. Multumesc!

[•danalex97]

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.

[•klamathix]

Am marit limita.

[•valen.valentin]

Ar putea sa se uite cineva la sursa mea,primesc 50 de puncte si chiar nu stiu ce gresesc,multumesc anticipat 

[•depevlad]

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.

[•vladrochian]

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