* 'Teoria jocurilor: numerele Sprague-Grundy':http://www.ginfo.ro/revista/14_5/mate.pdf, 'GInfo Mai 2004':http://www.ginfo.ro, Cosmin Negruseri
* 'Game Theory Text: Impartial Combinatorial Games':http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf, Thomas Ferguson

Aceasta probleme se regaseste in literatura de specialitate si cu titlul de _Kayles_. Rezultatul pentru un joc se poate calcula in functie de $XOR$-ul numerelor _Grundy_ pentru fiecare secventa de popice din sir. Cum $N ≤ 50.000$, trebuie calculate valorile Grundy pentru fiecare secventa de $i$ popice cu $i ≤ 50.000$. Acestea se pot calcula in complexitate patratica si se pot pune in sursa ca un sir de constante. O alta solutie se foloseste de observatia ca incepand cu $i = 72$ sirul de valori se repeta cu perioada $12$. Pentru fiecare test din fisier, complexitatea rezolvarii este $O(N)$.

Aceasta problema se regaseste in literatura de specialitate si cu titlul de _Kayles_. Rezultatul pentru un joc se poate calcula in functie de $XOR$-ul numerelor _Grundy_ pentru fiecare secventa de popice din sir. Cum $N ≤ 50.000$, trebuie calculate valorile Grundy pentru fiecare secventa de $i$ popice cu $i ≤ 50.000$. Acestea se pot calcula in complexitate patratica si se pot pune in sursa ca un sir de constante. O alta solutie se foloseste de observatia ca incepand cu $i = 72$ sirul de valori se repeta cu perioada $12$. Pentru fiecare test din fisier, complexitatea rezolvarii este $O(N)$.

h2. 'Regiuni':problema/regiuni

Aceasta problema a aparut din cauza faptului ca autorul a inteles gresit problema Druizi de la concursul .campion. Dupa ce am discutat problema cu mai multe persoane am observat ca majoritatea pornesc de la problema mai simpla de a vedea daca doua puncte sunt sau nu in acelasi grup. Ideea mea initiala este putin diferita: rezolvam problema adaugand pas cu pas cate o dreapta si mentinand informatia despre grupuri. Cand adaugam o dreapta iteram peste toate grupurile. Un grup va fi impartit in alte doua: punctele din stanga dreptei si punctele din dreapta. E posibil ca unul din aceste doua grupuri sa fie vid si atunci nu il mai retinem. Un grup il impartim in doua in $O(a)$ operatii unde a este numarul de elemente din grup. Toate grupurile vor avea in total $a1 + a2 + ... + ai + ... = M$ elemente, deci pentru a actualiza grupurile adaugand o dreapta facem $O(M)$ pasi. Astfel solutia are complexitatea finala $O(N * M)$, si este foarte usor de implementat.

Alte solutii ar fi determinarea pentru fiecare punct a unui vector ce ne spune pentru fiecare dreapta in ce parte e situat punctul. Daca doi astfel de vectori asociati la doua puncte sunt egali, atunci cele doua puncte sunt situate in aceiasi regiune. Pentru determinarea egalitatii vectorilor s-ar fi putut folosi o sortare naiva si astfel am fi avut o solutie de complexitate $O(MN log M)$ sau am fi putut folosi radix sort pentru a o aduce la $O(MN). Aceste doua solutii folosesc $O(MN)$ memorie. Alta solutie ar fi sa obtinem un cod hash pentru fiecare vector, aceasta solutie are complexitatea O(MN) ca timp si $O(M + N)$. memorie. Pentru a face probabilitatea de coliziune cat mai mica putem folosi cate doua coduri diferite pentru fiecare vector. Alta observatie ar fi ca vectorii sunt binari si pastrand informatia pe biti folosim mai putina memorie si avem mult mai putine operatii la comparare.

Alte solutii ar fi determinarea pentru fiecare punct a unui vector ce ne spune pentru fiecare dreapta in ce parte e situat punctul. Daca doi astfel de vectori asociati la doua puncte sunt egali, atunci cele doua puncte sunt situate in aceiasi regiune. Pentru determinarea egalitatii vectorilor s-ar fi putut folosi o sortare naiva si astfel am fi avut o solutie de complexitate $O(MN log M)$ sau am fi putut folosi radix sort pentru a o aduce la $O(MN)$. Aceste doua solutii folosesc $O(MN)$ memorie. Alta solutie ar fi sa obtinem un cod hash pentru fiecare vector, aceasta solutie are complexitatea O(MN) ca timp si $O(M + N)$. memorie. Pentru a face probabilitatea de coliziune cat mai mica putem folosi cate doua coduri diferite pentru fiecare vector. Alta observatie ar fi ca vectorii sunt binari si pastrand informatia pe biti folosim mai putina memorie si avem mult mai putine operatii la comparare.

h2. 'Elimin 2':problema/elimin2