infoarena

Aici puteţi discuta despre problema SETI (http://infoarena.ro/problema/seti).

Cred ca aveti probleme cu evaluatorul, mai exact cu timpii dati de el:
  Am trimis exact aceasi sursa de doua ori intr-un interval de 1 minut. Pt prima data am luat 40 de puncte, iar a doua oara 50  =D>

  Later edited:
  Am incercat din nou, si iar am luat 40 cu 50 de puncte  :mrgreen:

Asta se intampla la cazurile limita.. daca mai optimizezi putin programul o sa iei 50 constant. Prin putin se poate intelege de exemplu declararea variabilelor folosite in for local si nu global.

btw.. de ce trimiti exact aceasi sursa intr-un interval de 1 minut ?

Pai aveam probleme cu internetul si am dat de doua ori fara sa stiu ca prima data a fost acceptata. Si inca ceva... puteti sa-mi spuneti complexitatea solutiei oficiale?  [-o<

daca faci intai o preprocesare si apoi raspunzi la fiecare intrebare in logN*c (c o constanta :) ) ar trebui sa intre in timp fara probleme.

preprocesare la ce?

pai asupra sirului initial, nu prea ai altceva la ce

Complexitatea solutiei mele e O(N log LMAX + M log N * LMAX), unde N e lungimea vectorului, M e numarul de cuvinte si LMAX e lungimea maxima a unui cuvant. Mie imi intra fara nici o problema in timp...

pentru cei care lucreaza in pascal, cum ati facut citirea?

stiu ca noul compilator are probleme cu readln/read.

Era vorba de vechiul compilator , nu de cel nou

later edit: nevermind, am schimbat ceva pe la citire si a luat 100

s-ar putea sa nu fie din cauza asta.. la o problema schimbam citirea in mai multe moduri si atatea punctaje diferite luam, era din cauza unui bug care nu avea nici o legatura cu citirea datelor

As vrea si eu sa stiu ce are programul cand iti da eroarea RUN OUT OF MEMORY. E din cauza pointerilor care probabil nu sunt alocati bine?
In total memoria mea nu depaseste 0.5 Mb :?:

wefgef, imi areti si mie cum ai facut citirea?

Iau in continuare 0 puncte (toate testele WA - ma rog, sau fisier de iesire lipsa, dar nu cred ca asta e problema), desi mi-am dat o groaza de teste si le iau pe toate.
  ](*,)
Poate e de la citire... :cry:

Eu am facut asa pentru fiecare cuvant sau linie de text:


unde st e un string. Nu cred ca sunt probleme cu citirea. Aproape sigur ai un bug pe altundeva

eu citeam in array of char.

Am reusit si eu sa storc 40 puncte cu o solutie bazata pe cautari cu pointeri,la restul da TLE.

Spuneti-mi si mie una dintre cele mai eficiente metode de citire ale sirurilor de caractere in c sau c++,ppppplllllssssssss

V-ati gandit cumva si la posibilitatea de a lucra cu numere in baza 64.Cred ca pentru asta a fost pusa problema. Sa te prinzi de niste optimizari.....Insa nu stiu ce sa zic :x

Tot ma chinui sa gasesc o idee cat de cat eficienta si nu reusesc

eu am luat 100 cu citirea urmatoare


Nu este nevoie de pointeri sau de Int64 (daca la asta te referi), ci doar de niste mici observatii de bun simt. Cat despre optimizari ale solutiei corececte sunt si ele, de asemenea, de bun simt. Nu e ceva complicat, oricum tot resepctul celui care ia 100 si pe Borland C sau Borland Pascal  [-o<  [-o<  [-o<

Ar putea cineva sa-mi explice ideea pentru rezolvarea cu suffix arrays? Am gasit pe articolul cu siruri de sufixe cateva indicatii, unde se pomenea ceva de 2 cautari binare. Ce anume se cauta binar, cumva sufixele ce au ca prefix pe fiecare din cuvintele din lista de M? Si cum se face comparatia de prefixe, trebuie preprocesate si cele M cuvinte cu aceeasi metoda ca pentru sirul principal?
Multumesc anticipat  :)

Daca un sir P apare intr-un sir S, atunci P trebuie sa fie prefix al unuia sau mai multor sufixe ale lui S. Astfel, avand sirul sortat al sufixelor lui S, toate pozitiile i din acest sir care indeplinesc conditia ca sufixul ce corespunde acestei pozitii sa aiba ca prefix sirul P sunt deplasamente corecte ale lui P in S. Vei observa ca toate aceste pozitii i sunt consecutive in sirul de sufixe, si poti gasi un "upper bound" si un "lower bound" cu doua cautari binare. Fiecare cautare binara are nevoie de log|S| pasi, iar fiecare pas are nevoie de cel mult |P| comparatii. De aici O( |P|*log|S| ).

Datorita conditiei suplimentare ca niciun pattern nu va fi mai lung de 64 de caractere, poti sorta sufixele in asa fel incat prefixele lor de lungime 64 sa fie in ordinea corecta (asta reduce din timpul constructiei suffix array-ului).

Testul 1 nu are '\n' dupa ultimul cuvant ceea ceea ce strica unele functii de citire. Ar trebui adaugat.  :)

Cat m-am chinuit sa fac testu ala sa mearga...  :)

Da si eu , nu greseam nimci la program pur si simplu calculam lungimea stringului tinand cont ca e si '\n' cand am pus un if sa verific am trecut testul.
Apropo tu cum ai facut de ai trecut asa rapid de testele 6,7 , eu tot laum tle pe ele.  :-k

Am facut problema cu suffix array. Insa, daca opream precalcularea la pasul 4 ( adica dupa ce sortam sufixele de lungime 2^4 = 16 ), luam WA. Cand am lasat pana la pasul logN, a mers de 100. Nelamurirea mea este: de ce nu functiona cand ma opream la pasul 4 ?  :-k

Cred ca testele 5,6 si 7 nu respecta restrictiile problemei. Daca fiecare cuvant il citesc cu maxim 19 caractere ( fgets(s, 19, stdin) ) atunci iau WA pe testele respective. Daca modific din 19 in 20 iau corect pe toate testele.

Nu cred ca e o problema cu testele. Si eu am patit cu fgets, trebuie declarat cu 5 sau mai multe caractere, pentru ca el citeste si \n, si in cazul windowsului \r si altele. Si daca ai avea sa zicem cuvantul : abcd, si ai avea fgets ( S, 4, stdin ) , nu ti-ar mai citi \n si nu s-ar executa corect ;) .

Stiu, tocmai de aceea am pus 19(cuvintele au maxim 16 caractere, deci citesc cu 3 caractere in plus). Daca nu sunt testele de vina nu inteleg de ce nu e bine cu 19 si este bine cu 20.

EDIT: am modificat citirea(am pus scanf) si daca declar stringul de 18 elemente iau KBS pe aceleasi teste. Eu zic ca testele sunt gresite.

Ia testele si vezi daca sunt ok ( Sectiunea downloads, ONI 2002, clasele 11-12 ) .

Pentru cine nu a reusit sa ia 100

testul 5 contine cuvintele interrelationship si interrelationships care au 17, respectiv 18 litere

Am inlocuit 16 cu 20 in enunt  :)