•Cosmin
|
|
« : Aprilie 12, 2006, 16:07:28 » |
|
Aici puteţi discuta despre problema Password.
|
|
|
Memorat
|
|
|
|
•tudalex
Strain
Karma: -8
Deconectat
Mesaje: 44
|
|
« Răspunde #1 : Aprilie 14, 2006, 14:05:06 » |
|
Parola este data de cea mai mica rotatie la stanga (in ordine lexicografica) a cuvantului cheie. Asta inseamna ca trebuie sa rotim cuvantul de cat mai putine ori astfel incat sa il obtinem in ordine cat mai crescatoare a litereror?
|
|
|
Memorat
|
"Doua lucruri sunt infinite: universul si prostia omeneasca, dar de prima inca nu sunt sigur" Albert Einstein
|
|
|
•fireatmyself
|
|
« Răspunde #2 : Aprilie 14, 2006, 14:11:48 » |
|
da
|
|
|
Memorat
|
Viata e scurta. Daca nu o putem lungi, macar s-o facem lata.
|
|
|
•greco
|
|
« Răspunde #3 : Aprilie 14, 2006, 16:50:05 » |
|
ordine cat mai crescatoare
Interesanta exprimare
|
|
|
Memorat
|
Jump in the cockpit and start up the engines Remove all the wheelblocks there's no time to waste Gathering speed as we head down the runway Gotta get airborne before it's too late.
|
|
|
•rmikeweb
Strain
Karma: -4
Deconectat
Mesaje: 20
|
|
« Răspunde #4 : Mai 17, 2006, 08:40:10 » |
|
Mi-ati putea da si mie un hint. Singura solutie pe care o stiu la problema asta merge in N^2 si evident nu intra in timp.
|
|
|
Memorat
|
Mike
|
|
|
•wefgef
|
|
« Răspunde #5 : Mai 17, 2006, 13:45:25 » |
|
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•rmikeweb
Strain
Karma: -4
Deconectat
Mesaje: 20
|
|
« Răspunde #6 : Mai 24, 2006, 07:04:28 » |
|
Ok, o sa-l citesc si o sa incerc sa il implementez.
|
|
|
Memorat
|
Mike
|
|
|
•StTwister
Client obisnuit
Karma: 11
Deconectat
Mesaje: 86
|
|
« Răspunde #7 : Aprilie 17, 2007, 23:06:16 » |
|
Nu e putin cam stransa limita de timp?
Cu suffix array in O(NlogN) nu scot decat 5 puncte
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #8 : Aprilie 18, 2007, 05:28:04 » |
|
Se poate face in O(n) ... si constanta la suffix array in O(n log n) e cam mare.
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #9 : Aprilie 18, 2007, 14:20:48 » |
|
oricum, e mult mai lejer sa implementezi rotatii decat suff array..
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•StTwister
Client obisnuit
Karma: 11
Deconectat
Mesaje: 86
|
|
« Răspunde #10 : Aprilie 18, 2007, 17:35:05 » |
|
Stiu asta, am si facut implementarea in O(N), dar nu prea mi se pare firesc sa iei 5 puncte cu O(NlogN)
Practic nu se poate face o deparatajre intre solutii ca si complexitate. Si totusi nu puteti spune ca NlogN e brut, ca sa primeasca 0-10 puncte
|
|
|
Memorat
|
|
|
|
•astronomy
|
|
« Răspunde #11 : Aprilie 18, 2007, 18:13:12 » |
|
Depinde ce suffix array ai facut, eu tin minte ca luam in jur de 80 cu suffix array la problema asta.
|
|
|
Memorat
|
|
|
|
•DITzoneC
|
|
« Răspunde #12 : Aprilie 18, 2007, 21:12:27 » |
|
Eu am luat 100 cu suffix array
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #13 : Aprilie 19, 2007, 05:37:14 » |
|
O modalitate care nu ar merge ar fi sa sortezi cu qsort sufixele ).
|
|
|
Memorat
|
|
|
|
•StTwister
Client obisnuit
Karma: 11
Deconectat
Mesaje: 86
|
|
« Răspunde #14 : Aprilie 19, 2007, 18:11:41 » |
|
Intr-adevar am incercat o alta implementare si am ajuns pana la 80 de puncte folosind aceasta abordare. Prima oara inceram sa implementez la fel ca in articolul despre siruri de sufixe de la sectiunea downloads, cu o complexitate totala O(N*logN*logN), nu O(N*logN) cum am zis la inceput (am uitat sa includ si sortarea ). Pana la urma nu m-am lamurit daca abordarea e gresita sau implementarea mea (totusi de ce TLE si nu WA atunci?).
|
|
|
Memorat
|
|
|
|
•marcelcodrea
|
|
« Răspunde #15 : Aprilie 19, 2007, 18:37:53 » |
|
Cu suffix array se ia 80 puncte din cauza timpului depasit , intotdeauna algoritmul va furniza raspunsul corect , cel putin asa cred !
|
|
|
Memorat
|
|
|
|
•StTwister
Client obisnuit
Karma: 11
Deconectat
Mesaje: 86
|
|
« Răspunde #16 : Aprilie 19, 2007, 20:33:54 » |
|
Normal ca va furniza raspunsul corect, dar eu ma refeream la faptul ca poate am implementat gresit arborii de sufixe. Si acum depinde de fiecare implementare, pentru ca sunt destule posibilitati, de la O(N^2*logN) pana la O(N) se pare (nu am implementat niciodata). Teoretic, in O(N) ar trebui sa intre de 100 (folosind suffix array, nu rotatii), chiar daca constanta e ceva cam mare.
A incercat cineva cu suffix array in O(N) ?
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #17 : Aprilie 20, 2007, 08:52:23 » |
|
Nu cred ca merg prea bine suff array in O(n) in practica.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•gabitzish1
|
|
« Răspunde #18 : Ianuarie 08, 2008, 10:20:52 » |
|
Am rezolvat problema asa cum e descrisa in articolul "Rotatie lexicografic minima". Am luat 80 puncte cu 4 WA. Timpii de executie sunt de 0 si 4 ms... Un hint? ce poate fi gresit?
LE: am gasit... nu era chiar ca si in articol...
|
|
« Ultima modificare: Ianuarie 08, 2008, 20:00:59 de către Bitis Gabriel »
|
Memorat
|
|
|
|
•domino
|
|
« Răspunde #19 : Ianuarie 09, 2008, 09:06:02 » |
|
Ce nu era ca in articol?
|
|
|
Memorat
|
|
|
|
•gabitzish1
|
|
« Răspunde #20 : Ianuarie 09, 2008, 13:20:09 » |
|
Ce nu era ca in articol?
in articol apare pseudocodul urmator: 1. min <- 0; p <- 1; l <- 1; 2. cat timp (p < N) AND (min+l+1 < N) executa 3. daca S[min+l] = S[p+l] atunci l <- l+1; 4. daca S[min+l] < S[p+l] atunci p <- p+l+1; l <- 0; 5. daca S[min+l] > S[p+l] atunci min <- max(min+l+1, p); p <- min+1; l <- 0; 6. sfarsit cat timp 7. scrie min luam 80 de puncte cu asta. am luat 100 modificand la linia a doua din "cat timp (p < N)" in "cat timp (p < N-1)"
|
|
|
Memorat
|
|
|
|
•domino
|
|
« Răspunde #21 : Ianuarie 09, 2008, 14:34:02 » |
|
Nu cred ca modificarea ta este corecta, chiar daca ai luat 100. Cred ca motivul pentru care luai 80 era ca p+l poate fi mai mare ca N, deci trebuie sa faci (p+l)%N cand indexezi S.
|
|
|
Memorat
|
|
|
|
•andrici_cezar
|
|
« Răspunde #22 : Martie 21, 2009, 10:14:04 » |
|
care sunt rotatiile? mississippi ississippim ssissippimi sissippimis issippimiss ssippimissi sippimissis ippimississ ppimississi pimississip mississipp
|
|
|
Memorat
|
|
|
|
•Bogdan_tmm
|
|
« Răspunde #23 : Martie 22, 2009, 10:17:09 » |
|
|
|
|
Memorat
|
|
|
|
•andrici_cezar
|
|
« Răspunde #24 : Martie 22, 2009, 14:24:02 » |
|
mie imi citeste bine, la testul acela imi face bine, dar pentru restu nu, nu inteleg ce am gresit:(( eu lucrez in pascal:d nu in cpp
|
|
|
Memorat
|
|
|
|
|