h3. Rezolvare

Notam cu $a$ numarul lipsa si cu $b$ numarul ce apare de doua ori. Majoritatea celor care stiu sa rezolve problema $1$ prin cele doua solutii optime (suma numerelor si suma xor) incearca sa rezolve aceasta problema determinand doua relatii diferite asupra lui $a$ si $b$, din care apoi incearca sa obtina valorile cerute. Scazand din $n(n + 1)/2$ suma numerelor din fisier obtinem valoarea pentru $a – b$, iar facand suma xor a numerelor din fisier si a numerelor de la $1$ la $n$ obtinem valoarea pentru $a ^∧^ b$. In acest moment putem considera ca problema este rezolvata, dar la o analiza mai atenta se poate observa ca numerele care verifica relatiile respective nu sunt unice. De exemplu pentru $a = 10$ si $b = 9$ obtinem valorile $a - b = 1$ si $a ^∧^ b = 3$. Aceleasi valori le obtinem si pentru $a = 6$ si $b = 5$. Se observa de aici ca cele doua relatii nu pot fi folosite pentru a rezolva problema.

Notam cu $a$ numarul lipsa si cu $b$ numarul ce apare de doua ori. Majoritatea celor care stiu sa rezolve problema $1$ prin cele doua solutii optime (suma numerelor si suma xor) incearca sa rezolve aceasta problema determinand doua relatii diferite asupra lui $a$ si $b$, din care apoi incearca sa obtina valorile cerute. Scazand din $n(n + 1)/2$ suma numerelor din fisier obtinem valoarea pentru $a - b$, iar facand suma xor a numerelor din fisier si a numerelor de la $1$ la $n$ obtinem valoarea pentru $a ^∧^ b$. In acest moment putem considera ca problema este rezolvata, dar la o analiza mai atenta se poate observa ca numerele care verifica relatiile respective nu sunt unice. De exemplu pentru $a = 10$ si $b = 9$ obtinem valorile $a - b = 1$ si $a ^∧^ b = 3$. Aceleasi valori le obtinem si pentru $a = 6$ si $b = 5$. Se observa de aici ca cele doua relatii nu pot fi folosite pentru a rezolva problema.

Stim care este valoarea diferentei $D{~1~} = a - b$, dar mai avem nevoie de o relatie pentru a determina numerele $a$ si $b$. Vom incerca in continuare sa folosim operatia de inmultire pentru a obtine cea de-a doua relatie. Vom avea: $a/b = n! / a[ 1 ] * a[ 2 ] * ... * a[ n ]$. Aceasta relatie nu poate fi calculata in $O(n)$ pentru ca numarul de cifre al lui $n!$ nu este constant. Pentru a evita lucrul cu numere mari am putea sa logaritmam intreaga relatie, obtinand $lg a - lg b = lg 1 + lg 2 + ... + lg n - lg a[ 1 ] - lg a[ 2 ] - ... - lg a[ n ]$. Aceasta rezolvare ar fi buna daca ar fi posibila realizarea unor calcule perfecte cu numere reale. Din pacate acest lucru nu este posibil si rezolvarea are mari probleme cu precizia.
O a doua relatie o putem obtine ca diferenta intre suma patratelor numerelor de la $1$ la $n$ si suma patratelor numerelor din fisier. Obtinem astfel $D{~2~} = a^2^ - b^2^$. Din aceste doua relatii putem usor afla ca $a = (D{~1~} + D{~2~}/D{~1~})/2$ si $b = (D{~2~}/D{~1~} - D{~1~})/2$. Aceasta rezolvare are complexitatea $O(n)$ ca timp si $O(1)$ ca spatiu.

h3. Rezolvare

Fie $a, b, c, ...$ numerele ce lipsesc. Am putea extinde ideea din problema anterioara pentru a obtine in $O(n*k)$ sumele $S{~1~} = a + b + c + ..., S{~2~} = a^2^ + b^2^ + c^2^ + ..., ..., S{~k~} = a^k^ + b^k^ + c^k^ + ...$ si sa obtinem valorile elementelor $a, b, c, ...$, dar in general daca valoarea lui $k$ este variabila, atunci putem gasi solutia ce satisface toate cele $k$ relatii in timp exponential. O metodă este de a transforma relatiile intr-un polinom de radacini $a, b, c, ...$. Pentru a gasi $P(x) = a{~0~}X^k^ + a{~1~}X^k-1^ + ... + a{~k~}$ putem folosi relatiile lui Viete[1]

Fie $a, b, c, ...$ numerele ce lipsesc. Am putea extinde ideea din problema anterioara pentru a obtine in $O(n*k)$ sumele $S{~1~} = a + b + c + ..., S{~2~} = a^2^ + b^2^ + c^2^ + ..., ..., S{~k~} = a^k^ + b^k^ + c^k^ + ...$ si sa obtinem valorile elementelor $a, b, c, ...$, dar in general daca valoarea lui $k$ este variabila, atunci putem gasi solutia ce satisface toate cele $k$ relatii in timp exponential. O metoda este de a transforma relatiile intr-un polinom de radacini $a, b, c, ...$. Pentru a gasi $P(x) = a{~0~}X^k^ + a{~1~}X^k-1^ + ... + a{~k~}$ putem folosi relatiile lui Viete[1]

$s{~1~} = a + b + c + d + ...$
$s{~2~} = ab + ac + ad + bc + bd + cd + ...$
$s{~3~} = abc + acd + bcd + ...$

...
$s{~i~} = (-1)^i^ a{~n-i~}/a{~n~}$

Aceste sume $s{~k~}$ sunt numite polinoame simetrice si sunt strans legate de sumele de puteri $k S{~k~}$ prin relatiile Newton Girard[2]. Astfel avem un algoritm ce determină polinomul in $O(nk)$ si spatiu $O(k)$ (daca se ignora faptul ca numerele ar putea depasi intervalul numerelor reprezentabile pe un intreg), dar determinarea solutiei finale se poate face in $O(1)$ doar pentru ecuatii de gradul doi sau trei, pentru care stim formule de calcul. Pentru ecuatii de grad mai mare nu exista formule generale si trebuie aplicate metode care aproximeaza solutiile. O astfel de metoda ar fi sa derivam polinomul, sa gasim solutiile pentru $P'(x) = 0$, iar apoi sa folosim cate o cautare binara pentru a gasi solutiile $P(x) = 0$.

Aceste sume $s{~k~}$ sunt numite polinoame simetrice si sunt strans legate de sumele de puteri $k S{~k~}$ prin relatiile Newton Girard[2]. Astfel avem un algoritm ce determin� polinomul in $O(nk)$ si spatiu $O(k)$ (daca se ignora faptul ca numerele ar putea depasi intervalul numerelor reprezentabile pe un intreg), dar determinarea solutiei finale se poate face in $O(1)$ doar pentru ecuatii de gradul doi sau trei, pentru care stim formule de calcul. Pentru ecuatii de grad mai mare nu exista formule generale si trebuie aplicate metode care aproximeaza solutiile. O astfel de metoda ar fi sa derivam polinomul, sa gasim solutiile pentru $P'(x) = 0$, iar apoi sa folosim cate o cautare binara pentru a gasi solutiile $P(x) = 0$.

De exemplu pentru trei numere lipsa $a, b, c$ este usor sa determinam $S{~1~} = a + b + c, S{~2~} = a^2^ + b^2^ + c^2^, S{~3~} = a^3^ + b^3^ + c^3^$. $S{~1~}^2^ = a^2^ + b^2^ + c^2^ + 2ab + 2bc + 2ac = S{~2~} + 2s{~2~}, S{~1~}^3^ = a^3^ + b^3^ + c^3^ + 3a^2^b + 3a^2^c + 3b^2^a + 3b^2^a + 3c^2^a + 3c^2^b + 6abc = S{~3~} + 3(a^2^b + b^2^a + abc) + 3(a^2^c + c^2^a + abc) + 3(b^2^c + c^2^b + abc) - 3abc = S{~3~} + 3ab*s{~1~} + 3ac*s{~1~} + 3bc*s{~1~} - s{~3~} = S{~3~} + 3s{~2~}*s{~1~} - s{~3~}$. Din aceste relatii putem sa obtinem usor $s{~1~}, s{~2~}, s{~3~}$ si apoi putem aplica formulele lui Cardano de rezolvare a ecuatiei de gradul trei pe ecuatia $x^3^ - s{~1~} x^2^ + s{~2~} x - s{~3~} = 0$.
h2(#prob8). Problema 8