Pagini: [1] 2   În jos
  Imprimă  
Ajutor Subiect: 242 Password  (Citit de 10109 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« : Aprilie 12, 2006, 16:07:28 »

Aici puteţi discuta despre problema Password.
Memorat
tudalex
Strain
*

Karma: -8
Deconectat Deconectat

Mesaje: 44



Vezi Profilul
« Răspunde #1 : Aprilie 14, 2006, 14:05:06 »

Citat
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
Nu mai tace
*****

Karma: 36
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #2 : Aprilie 14, 2006, 14:11:48 »

da  Ok
Memorat

Viata e scurta. Daca nu o putem lungi, macar s-o facem lata.
greco
Nu mai tace
*****

Karma: 144
Deconectat Deconectat

Mesaje: 434



Vezi Profilul
« Răspunde #3 : Aprilie 14, 2006, 16:50:05 »

ordine cat mai crescatoare

Interesanta exprimare  Shame on you
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 Deconectat

Mesaje: 20



Vezi Profilul
« 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
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #5 : Mai 17, 2006, 13:45:25 »

http://info.devnet.ro/download.php

downlodeaza-ti articolul. Smile
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
rmikeweb
Strain


Karma: -4
Deconectat Deconectat

Mesaje: 20



Vezi Profilul
« 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 Deconectat

Mesaje: 86



Vezi Profilul
« 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
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« 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
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« 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 Deconectat

Mesaje: 86



Vezi Profilul
« 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
Nu mai tace
*****

Karma: 204
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« 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
Nu mai tace
*****

Karma: 301
Deconectat Deconectat

Mesaje: 962



Vezi Profilul
« Răspunde #12 : Aprilie 18, 2007, 21:12:27 »

Eu am luat 100 cu suffix array Smile
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #13 : Aprilie 19, 2007, 05:37:14 »

O modalitate care nu ar merge ar fi sa sortezi cu qsort sufixele Smile).
Memorat
StTwister
Client obisnuit
**

Karma: 11
Deconectat Deconectat

Mesaje: 86



Vezi Profilul
« 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 Tongue). Pana la urma nu m-am lamurit daca abordarea e gresita sau implementarea mea (totusi de ce TLE si nu WA atunci?).
Memorat
marcelcodrea
Nu mai tace
*****

Karma: 173
Deconectat Deconectat

Mesaje: 217



Vezi Profilul
« 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 Deconectat

Mesaje: 86



Vezi Profilul
« 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
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« 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
Moderatori infoarena
Nu mai tace
*****

Karma: 321
Deconectat Deconectat

Mesaje: 926



Vezi Profilul
« 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
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #19 : Ianuarie 09, 2008, 09:06:02 »

Ce nu era ca in articol?
Memorat
gabitzish1
Moderatori infoarena
Nu mai tace
*****

Karma: 321
Deconectat Deconectat

Mesaje: 926



Vezi Profilul
« Răspunde #20 : Ianuarie 09, 2008, 13:20:09 »

Ce nu era ca in articol?
in articol apare pseudocodul urmator:
Cod:
   
   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
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« 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
De-al casei
***

Karma: -47
Deconectat Deconectat

Mesaje: 121



Vezi Profilul
« Răspunde #22 : Martie 21, 2009, 10:14:04 »

care sunt rotatiile?
mississippi
ississippim
ssissippimi
sissippimis
issippimiss
ssippimissi
sippimissis
ippimississ
ppimississi
pimississip
mississipp
Huh
Memorat
Bogdan_tmm
De-al casei
***

Karma: 4
Deconectat Deconectat

Mesaje: 122



Vezi Profilul
« Răspunde #23 : Martie 22, 2009, 10:17:09 »

la problema asta ori eram eu prea ametit si nu faceam citirea bine Smile) ori kiar nu merge cu FILE *f(..)...Andrici incearca sa folosesti fstream.La mine asta era problema Angry Angry Angry
Memorat
andrici_cezar
De-al casei
***

Karma: -47
Deconectat Deconectat

Mesaje: 121



Vezi Profilul
« 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
Pagini: [1] 2   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines