Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Unicat  (Citit de 5170 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
savim
Nu mai tace
*****

Karma: 194
Deconectat Deconectat

Mesaje: 333



Vezi Profilul
« : Februarie 24, 2013, 01:28:28 »

Aici se pot pune întrebări legate de problema Unicat de la Runda 3 a concursului Algoritmiada 2013.

Timpul alocat întrebărilor este de 1 ora dupa inceperea concursului. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea își găsește răspuns în enunțul problemei, răspunsul va fi FARA COMENTARII.
Memorat
veleandu
De-al casei
***

Karma: 155
Deconectat Deconectat

Mesaje: 132



Vezi Profilul
« Răspunde #1 : Februarie 24, 2013, 13:04:04 »

Poate sa imi spuna cineva de ce as putea lua KBS 6?
Nu am asserturi, si am verificat ca indicii sa fie in ce am initializat.

Pot lua pentru ca faceam .. ?
Citat
string a;
void solve( string T ){
...
}
int main(){
cin>>a;
solve(a);
}
Memorat
danalex97
Vorbaret
****

Karma: 54
Deconectat Deconectat

Mesaje: 192



Vezi Profilul
« Răspunde #2 : Februarie 24, 2013, 13:05:15 »

Cum ati facut-o ? Adica am avut o idee cu hash-uri care mergea in N^2.  Smile Voi ?
Memorat
Challenge
Strain


Karma: 18
Deconectat Deconectat

Mesaje: 19



Vezi Profilul
« Răspunde #3 : Februarie 24, 2013, 13:08:41 »

Eu am tinut Trie in care adaug fiecare palindrom de lungime maxima pentru fiecare centru posibil in parte. Nu sunt sigur de complexitate, dar cred ca e O(N). Palindroamele le fac ca la problema PSCPLD. Iar in Trie tin doar a 2-a jumatate a palindromului.
Memorat
proflaurian
Client obisnuit
**

Karma: 46
Deconectat Deconectat

Mesaje: 58



Vezi Profilul
« Răspunde #4 : Februarie 24, 2013, 13:12:19 »

Tot cu trie dar in O(N^2). Probabil prea mult Smile
Memorat
mugurelionut
De-al casei
***

Karma: 209
Deconectat Deconectat

Mesaje: 136



Vezi Profilul
« Răspunde #5 : Februarie 24, 2013, 13:13:12 »

@Murtaza Alexandru: Si daca, de exemplu, ambele siruri contin 500.000 de 'a'-uri fiecare ?
In acest caz ai palindroame lungi de la fiecare centru posibil, iar suma lungimilor lor este O(N^2) (chiar daca in trie o sa ai doar O(N) noduri).
Memorat
Challenge
Strain


Karma: 18
Deconectat Deconectat

Mesaje: 19



Vezi Profilul
« Răspunde #6 : Februarie 24, 2013, 13:15:16 »

Corect  Embarassed

Acum am realizat ca e O(N^2)
Memorat
veleandu
De-al casei
***

Karma: 155
Deconectat Deconectat

Mesaje: 132



Vezi Profilul
« Răspunde #7 : Februarie 24, 2013, 13:26:04 »

Si eu fac in principiu ca Rares ...
Cand fac PSCPLD, cand ma extind cu un caracter, pun palindromul acela in hash. Asta se face in o(1) dar trebuie precalculate in NlogN ..
Apoi sortez hashurile, si presupun in O(1) ca sunt egale  Rolling on the Floor Laughing

A mai facut cineva asa?
Memorat
repp4radu
Nu mai tace
*****

Karma: 118
Deconectat Deconectat

Mesaje: 204



Vezi Profilul
« Răspunde #8 : Februarie 24, 2013, 14:42:49 »

Care este solutia oficiala la aceasta problema?
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #9 : Februarie 24, 2013, 14:50:28 »

Hint: Pentru un sir exista un numar liniar de palindroame distincte.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
darren
Client obisnuit
**

Karma: 106
Deconectat Deconectat

Mesaje: 76



Vezi Profilul
« Răspunde #10 : Februarie 24, 2013, 16:04:08 »

Eu mi-am facut PSCPLD-ul, dupa care pentru fiecare pozitie puneam intr-un hash codul palindroamelor incepand cu cel mai mare (i - P[ i], i + P[ i]). Daca intalneam unul care era pus deja, ma opream (si cele mai mici ar fi fost puse). Astfel aveam maxim O(rezultat).
Am luat in concurs 40 din cauza codului hashului. L-am pus acum pe long long si am luat 100.
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #11 : Februarie 24, 2013, 16:07:56 »

Da, cam iese cum zici tu Smile.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

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