Solutia problemei Chei

In primul rand, pot distinge doua chei de forme diferite. Consideram cazul acesta acoperit in demonstratiile care urmeaza.

Intuitia

Ca sa pot distinge doua chei de aceeasi forma, am nevoie de un reper care nu se modifica atunci cand mi se roteste inelul in buzunar sau cand privesc sirul dintr-o alta parte. Un posibil reper ar fi sa consider o distanta d si sa compar perechea de chei aflate la distanta circulara d de prima cheie cu perechea de chei aflate la distanta circulara d de a doua cheie. Daca perechile neordonate ar fi distincte, cu siguranta pot distinge cheile.

Spre exemplu, in sirul de chei baxac, cheile de tip a au la distanta d = 1 perechile de chei (x, b) si (x, c).

Cu toate acestea, verificarea aceasta este insuficienta. De exemplu, pentru sirul bbaccbcabc, cheile a au perechea de chei (b, c) pentru toate distantele d (mai putin cand ambele obtin perechea (a, a)), dar pot sa le disting cu urmatorul rationament: Daca, in loc sa consider doar caracterul aflat la distanta d, as considera tot sirul de caractere pana la acel caracter? Practic, distanta d de o cheie nu ne mai da doar un caracter, ci intregul sir vizitat pana acolo.

Astfel, pentru sirul bbaccbcabc, cheile a au perechile de siruri de chei, pentru d = 2, ("bb", "cc"), respectiv ("cb", "bc"). Deci le putem distinge. Dar daca tot comparam perechi de siruri de marime d, nu mai bine comparam doar pentru d = N?

Concret

Sa notam cu alfa(p) sirul de N caractere pe care il citesc parcurgand circular spre dreapta sirul de chei incepand cu cea de la pozitia p.
Sa notam cu beta(p) sirul de N caractere pe care il citesc parcurgand circular spre stanga sirul de chei incepand cu cea de la pozitia p.

Lema

Pot distinge doua chei aflate la indicii p si q <=> multimea / perechea neordonata {alfa(p), beta(p)} este diferita de multimea / perechea neordonata {alfa(q), beta(q)}.

Demostratie

Daca pot distinge doua chei, inseamna ca am un reper care nu se schimba atunci cand rotesc sau intorc de nenumarate ori sirul. O informatie care nu se poate schimba este perechea neordonata {alfa(p), beta(p)}, dar ea este si suficienta deoarece este memoria maxima disponibila de informatii relevante a unei pozitii. In momentul cand mie mi se dau doua chei, le pot distinge daca si numai daca aceasta memorie a lor este identica.

O mica problema?

Atunci cand aflu, analizand sirul, despre doua chei de aceeasi forma ca le pot distinge, s-ar putea sa pot folosi acest fapt pentru a afla despre alte perechi de chei ca le pot distinge, desi inainte nu le puteam distinge. Asta s-ar putea sa se intample deoarece atunci cand verific egalitatea a doua siruri, a = a in mod normal. Dar daca eu am reusit sa disting intre cele 2 chei a, egalitatea dispare, s-ar putea spune ca a diferit de a, deoarece degeaba au aceeasi forma daca eu totusi le pot distinge.

Un rationament si complicatia dispare

Sa consideram cele doua chei pe care le-am distins prin faptul ca multimile mentionate mai sus sunt diferite. Ne punem intrebarea: pentru ce perechi de chei ar putea conta faptul ca ele sunt de fapt diferite? Pai pentru perechile de chei egal distantate de ele. Dar din moment ce le-am distins deja pe acestea doua chei, inseamna ca acele perechi de chei pentru care ar conta informatia, ele deja ar fi avut perechile (alfa, beta) diferite! Practic, informatia aceasta nu schimba cu nimic faptul ca doua chei ar putea sau nu sa fie acum distinse - daca se pot distinge, s-ar fi destins oricum.

Solutia

Trebuie doar sa afisam numarul de perechi de indici care au aceeasi pereche neordonata (alfa(p), beta(p)).

- 22 de puncte

Se aleg doi indici p si q si se compara prin parcurgere liniara sirul alfa(p) cu beta(q), sirul alfa(p) cu alfa(q), etc. si se ia deiciza daca multumile sunt egale sau nu. Trebuie putina grija sa parcurgem circular sirul din input.

- 51 de puncte

Egalitatea a doua siruri poate fi testata si altfel decat prin parcurgere directa. Sa ne uitam la un sir de caractere ca la un numar in baza 27, unde literele devin cifre - a devine 1, ..., z devine 26. Egalitatea a doua numere uriase se poate face cu probabilitate foarte mare daca le comparam resturile la impartirea cu doua numere, sa zicem prime, de ordinul zecilor sau sutelor de milioane. Daca vreti sa deveniti familiari cu aceasta tehnica numita hashing, puteti studia algoritmul Rabin-Karp.

Acum alfa si beta nu mai sunt siruri de caractere, ci niste numere mari pe care le retinem doar prin doua numere, resturile la impartirea cu doua numere de tip int alese dinainte. Acum, egalitatea poate fi verificata cu probabilitate foarte mare, in O(1).

- 100 de puncte

In loc sa luam toate perechile de indici (p, q) si sa verificam daca informatiile lor sunt egale, schimbam cumva tehnica numararii. Ne fixam informatia (perechea (alfa, beta)) si vedem cate perechi de indici au aceasta informatie. Practic, pentru fiecare pereche neordonata (alfa, beta) care apare macar o data intre cele N, notam cu F numarul de indici care au aceasta pereche. Atunci, trebuie doar sa adunam F * (F - 1) / 2 la raspuns, pentru ca atatea perechi ar fi spus ca sunt identice in solutia O(N^2).

Cum aflam F pentru fiecare pereche, fara sa parcurgem de fiecare data sirul de perechi? Mai intai, in cadrul fiecarei perechi, ordonam alfa <= beta conform unui comparator oarecare. Apoi sortam sirul de perechi, tot dupa un comparator oarecare. Astfel, perechile egale vor fi consecutive in sirul sortat. Acum, pentru fiecare segment maximal de perechi egale, F este egal cu marimea segmentului respectiv.