Unicat

[•savim]

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.

[•veleandu]

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

string a;
void solve( string T ){
...
}
int main(){
cin>>a;
solve(a);
}

[•danalex97]

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

[•Challenge]

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.

[•proflaurian]

Tot cu trie dar in O(N^2). Probabil prea mult

[•mugurelionut]

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

[•Challenge]

Corect 

Acum am realizat ca e O(N^2)

[•veleandu]

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 

A mai facut cineva asa?

[•repp4radu]

Care este solutia oficiala la aceasta problema?

[•wefgef]

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

[•darren]

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.

[•klamathix]

Da, cam iese cum zici tu .