|
Titlul: Unicat Scris de: Serban Andrei Stan din 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. Titlul: Răspuns: Unicat Scris de: Alex Velea din 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); } Titlul: Răspuns: Unicat Scris de: Dan H Alexandru din Februarie 24, 2013, 13:05:15 Cum ati facut-o ? Adica am avut o idee cu hash-uri care mergea in N^2. :) Voi ?
Titlul: Răspuns: Unicat Scris de: Murtaza Alexandru din 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.
Titlul: Răspuns: Unicat Scris de: Panaete Adrian din Februarie 24, 2013, 13:12:19 Tot cu trie dar in O(N^2). Probabil prea mult :)
Titlul: Răspuns: Unicat Scris de: Mugurel-Ionut Andreica din 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). Titlul: Răspuns: Unicat Scris de: Murtaza Alexandru din Februarie 24, 2013, 13:15:16 Corect :oops:
Acum am realizat ca e O(N^2) Titlul: Răspuns: Unicat Scris de: Alex Velea din 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 :rotfl: A mai facut cineva asa? Titlul: Răspuns: Unicat Scris de: Radu-Andrei Szasz din Februarie 24, 2013, 14:42:49 Care este solutia oficiala la aceasta problema?
Titlul: Răspuns: Unicat Scris de: Andrei Grigorean din Februarie 24, 2013, 14:50:28 Hint: Pentru un sir exista un numar liniar de palindroame distincte.
Titlul: Răspuns: Unicat Scris de: Rares Buhai din 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. Titlul: Răspuns: Unicat Scris de: Mihai Calancea din Februarie 24, 2013, 16:07:56 Da, cam iese cum zici tu :).
|