Solutii - Summer Challenge Unu

(Categoria Competitii, autor(i) Cosmin)

Concursul a fost unul reusit, adunand un numar respectabil de participanti.
Concurentii ce vor participa la IOI au fost in forma azi ocupand primele trei pozitii ale clasamentului. greco a impresionat placut fiind singurul ce a rezolvat perfect problema de idee a concursului. Il remarcam pozitiv si pe wefgef care se tine aproape de ei, de asemenea o remarca negativa ar fi la adresa lui Adrian Vladu care nu a participat la aceasta pregatire ,desi ea a fost adresata direct lotului olimpic.

Urmeaza primii 10 clasati:

Pozitie	Nume	Scor
1	Tiberiu-Lucian Florea •greco	300
2	Mircea Pasoi •domino	240
3	Grosu Codrut •Ragnar_Lodbrok	230
4	Andrei Grigorean •wefgef	220
5	Paul-Dan Baltescu •pauldb	200
6	UPB - Andrei Homescu •CommanderK	180
7	Andrei Blanaru •andrei_blanaru	150
8	Lica Adela •adal	140
9	Marius Stroe •Marius	130
9	Bogdan-Cristian Tataroiu •bogdan2412	130

Va invitam mai departe sa va uitati peste schitele solutiilor problemelor propuse.

Free

Aceasta problema a fost considerata cea mai simpla din concurs, in special pentru ca realizarea unui program experimental care simula pasii din problema ne arata ca usile ce raman inchise au ca index un patrat perfect.

Pentru a demonstra aceasta afirmatie avem nevoie de cateva cunostinte minore de teoria numerelor.

La fiecare pas i directorul va vizita toti multiplii lui i, ceea ce inseamna ca un anumit numar X4 va fi vizitat la pasii ai caror indecsi il divid pe {$X}. Deci pentru a afla cate usi vor fi deschise in final va trebui sa numaram cate numere au un numar par de divizori. Pentru acest lucru ne va si mai usor sa numaram cate au un numar impar de divizori urmand sa le scadem din N. Stim ca daca descompunem un numar X in factori primi: X=F₁^P₁*F₂^P₂*...*F_t^P_t numarul de divizori ai sai va fi D=(P₁+1)*(P₂+1)*...*(P_t+1). Pentru ca D sa fie impar trebuie ca fiecare factor al produsului sa fie deci P_i+1 impar ceea ce inseamna ca exponentii factorilor primi din descompunere vor fi pari. X=F₁^2*P'₁*F₂^2*P'₂*...*F_t^2*P'_t = (F₁^P'₁*F₂^P'₂*...*F_t^P'_t)². Inseamna ca X va fi patrat pefrect.

Alta demonstratie mai intuitiva ar fi ca pentru usa X putem imperechea actiunea i cu actiunea X/i daca i este divizor al lui X si astfel cele doua isi anuleaza efectul. Daca X este patrat perfect atunci actiunea [sqrt(X)] ramane neimperecheata, deci usa ramane deschisa.

Astfel solutia problemei va fi N-[sqrt(N)].

Operatiile trebuie implementate pe numere mari. Operatia radical se poate implementa folosind o cautare binara.

Patrol

Aceasta problema a fost considerata una medie, pentru ca algoritmii de drum minim in grafuri sunt foarte frecvent folositi la concursurile de programare.

Obsevam ca fiecare paznic va fi la orasul de unde a pornit la timpii multipli de 2*(l_i-1) (din cauza miscarii dute-vino). Astfel toti paznicii vor fi in acelasi timp la orasul initial al fiecaruia la toti timpii multipli de cmmmc(2*(l₁-1), 2*(l₂-1), ..., 2*(l_n-1)). Din cauza ca l_i < 8 cel mai mic multiplu comun maxim posibil al numerelor din problema poate fi cmmmc(2*4, 2*3, 2*5) = 120, astfel pozitiile paznicilor pe reteaua noastra de orase cicleaza si perioada ciclului este 120 sau un divizor al sau. Vom crea un graf in care nodurile sunt stari ale problemei (oras, timp % 120). Acum am redus problema la determinarea drumului de cost minim de la (1, 0) la (N, timp % 120), putem folosi un algoritm de drum minim la alegere Dijkstra cu heapuri sau bellman ford.

Pscpld

Aceasta problema se vroia a fi cea mai grea din concurs. O solutie bazata pe siruri de sufixe poate fi gasita in articolul "Siruri de sufixe" Adrian Vladu, Negruseri Cosmin, GInfo. Aceasta rezolvare nu ar fi luat punctaj maxim, o solutie similara in O(n) foloseste arbori de sufixe. Denumirea problemei a fost aleasa pentru a sugera ca rezolvarea greoaie cu arbori de sufixe nu este cea cautata. Problema are o solutie simpla in O(n) care urmeaza ideea rezolvarii in O(n²).

In rezolvarea brute force fixam un centru pentru un palindrom si incercam sa marim palindromul cat mai mult. Solutia va pastra un sir LUNG unde LUNG_2*i-1 reprezinta lungimea palindromului maxim centrat in caracterul i al sirului si LUNG_2*i lungimea palindromului centrat intre caracterul i si i + 1 al sirului. Vom parcurge sirul de caractere de la stanga la dreapta si vom afla in ordine valorile din sirul LUNG.
Sa luam un exemplu:

sirul:  a   b   a   a   b    a     c
LUNG:   1 0 3 0 1 6 1 0 x
indice: 1 2 3 4 5 6 7 8 9 10 11 12 13

Acum daca vrem sa calculam LUNG₉ ar trebui sa ne extindem cat putem in lateral fata de b, dar observam ca centrul palindromului curent este continut in palindromul centrat la 6. Din faptul ca palindromul contine doua subsecvente oglindite, noi nu trebuie sa mai iteram prin literele palindromului nostru pentru ca avem deja rezolvata problema oglindita, si continuam comparatiile cu caractere noi (in cazul nostru avem deja rezolvata problema a b a in secventa [1..5] si nu mai trebuie sa o rezolvam inca o data). Am obtinut astfel o rezolvare simpla de complexitate O(N). Mentionam ca sursa oficiala nu are mai mult de 50 de linii.

Exista si alte rezolvari optime posibile si ii rugam pe cei care au luat 100 de puncte sa le explice in cadrul forumului.