h1. Solutii - Summer Challenge Unu
(Creat de '_Cosmin_':user/Cosmin la data de _2006-08-03_ categoria __, autor(i) _Cosmin_)
*Continut scurt:*
Concursul a fost unul reusit, adunand un numar respectabil de concurenti.
Va multumim pentru participare!
Va invitam mai departe sa va uitati peste schitele solutiilor problemelor propuse.
*Continut lung:*
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:
|1 |greco |Florea Tiberiu |300p |
|2 |domino |Mircea Pasoi |240p |
|3 |Ragnar_Lodbrok |Grosu Codrut |234p |
|4 |wefgef |Andrei Grigorean |220p |
|5 |PaulDB |Paul-Dan Baltescu |200p |
|6 |CommanderK |Andrei Homescu |180p |
|7 |andrei_blanaru |Blanaru Andrei |150p |
|8 |adal |Lica Adela |140p |
|9 |Marius |Marius Stroe |130p |
|10 |Bogdan2412 |Bogdan Tataroiu |130p |
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 nevie 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 X 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[1]^P[1]*F[2]^P[2]*..*F[t]^P[t] numarul de divizori ai sai va fi D=(P[1]+1)*(P[2]+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[1]^2*P'[1]*F[2]^2*P'[2]*..F[t]^2*P'[t] = (F[1]^P'[1]*F[2]^P'[2]*..*F[t]^P'[t])^2. 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]-1), 2*(l[2]-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^2).
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[2i - 1] reprezinta lungimea palindromului maxim centrat in caracterul i al sirului si LUNG[2i] 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[9] 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.
h1. 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:
==Rankings(rounds="summer06" display_entries="10" pager_style="none")==
Va invitam mai departe sa va uitati peste schitele solutiilor problemelor propuse.
h2. 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{~1~}^P{~1~}^*F{~2~}^P{~2~}^*...*F{~t~}^P{~t~}^$} numarul de divizori ai sai va fi {$D=(P{~1~}+1)*(P{~2~}+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{~1~}^2*P'{~1~}^*F{~2~}^2*P'{~2~}^*...*F{~t~}^2*P'{~t~}^ = (F{~1~}^P'{~1~}^*F{~2~}^P'{~2~}^*...*F{~t~}^P'{~t~}^)^2^$}. 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.
h2. 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~}-1), 2*(l{~2~}-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.
h2. 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^2^)$}.
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:
== code(cpp) |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{~9~}$ 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":http://infoarena.ro/forum/index.php/board,25.0.html.
