Diferente pentru preoni-2006/runda-4/solutii intre reviziile #12 si #27

Nu exista diferente intre titluri.

Diferente intre continut:

h1. Solutii preONI 2006, Runda a 4-a
(Creat de '_domino_':user/domino la data de _2006-02-19_ categoria _Competitii_, autor(i) _Echipa info-arena_)
(Categoria _Competitii_, autor(i) _Echipa infoarena_)
Suntem bucurosi sa va anuntam ca Runda a 4-a concursului preONI 2006 s-a incheiat. In acest articol va vom prezenta solutiile oficiale ale celor 7 probleme propuse precum si cateva aprecieri dupa cele patru probe de foc.
S-a consumat si al patrulea act al bataliei si odata cu el si etapa on-line a concursului preONI. S-a tras linia si s-au desemnat "fericitii calificati in runda finala":http://infoarena.devnet.ro/clasament/preoni2006.php (atentie! verificarea inca nu a fost facuta, dar cu asta ne vom ocupa in urmatoarea perioada).
S-a consumat si al patrulea act al bataliei si odata cu el si etapa on-line a concursului preONI. S-a tras linia si s-au desemnat "fericitii calificati in runda finala":preoni-2006/clasament (atentie! verificarea inca nu a fost facuta, dar cu asta ne vom ocupa in urmatoarea perioada).
Aruncandu-ne ochii pe clasamentele Rundei 4, constatam ca participantii au tras tare pe ultima suta de metri vrand sa ne contrazica previziunile sumbre dupa Runda 3. Desi nivelul de dificultate al problemelor a fost un pic mai scazut fata de runda precedenta, concurentii s-au dovedit mult mai conectati la concurs - suspectam ca apropierea olimpiadelor ar fi cauza. Asadar am avut punctaje aproape maxime (275, 255) obtinute in viteza maxima de primii doi clasati la clasa a 9-a - $Bogdan Tataroiu$ si $Sima Mihai Cotizo$, un punctaj maxim la clasa a 12-a realizat de $Costea Andrei$ care a reusit, dupa un start mai putin reusit in rundele precedente, sa treaca la pas pe langa ceilalti info-atleti, unii dintre ei deja nume mari. De data aceasta, concurentii de la clasa a 10-a nu s-au lasat mai prejos fata de celelalte grupe de varsta si, avand un set clar mai usor decat precedentul, au adunat in ritm de maraton punctaje frumoase care au atins si depasit limita (legal admisa) de 200. Felicitari pentru aceasta realizare lui $Vlad Dumitriu$ si $Bogdan Stoica$. In concluzie, am asistat la un concurs bine organizat (felicitari comisiei!) si la un sprint de sanatate din partea concurentilor (felicitari mai ales lor!) care ne-au convins inca o data ca tinerii nostri sunt pregatiti sa fuga mancand pamantul pentru gloria si renumele olimpiadelor nationale si internationale.
Aruncandu-ne ochii pe clasamentele Rundei 4, constatam ca participantii au tras tare pe ultima suta de metri vrand sa ne contrazica previziunile sumbre dupa Runda 3. Desi nivelul de dificultate al problemelor a fost un pic mai scazut fata de runda precedenta, concurentii s-au dovedit mult mai conectati la concurs - suspectam ca apropierea olimpiadelor ar fi cauza. Asadar am avut punctaje aproape maxime $(275, 255)$ obtinute in viteza maxima de primii doi clasati la clasa a 9-a - $Bogdan Tataroiu$ si $Sima Mihai Cotizo$, un punctaj maxim la clasa a 12-a realizat de $Costea Andrei$ care a reusit, dupa un start mai putin reusit in rundele precedente, sa treaca la pas pe langa ceilalti info-atleti, unii dintre ei deja nume mari. De data aceasta, concurentii de la clasa a 10-a nu s-au lasat mai prejos fata de celelalte grupe de varsta si, avand un set clar mai usor decat precedentul, au adunat in ritm de maraton punctaje frumoase care au atins si depasit limita (legal admisa) de $200$. Felicitari pentru aceasta realizare lui $Vlad Dumitriu$ si $Bogdan Stoica$. In concluzie, am asistat la un concurs bine organizat (felicitari comisiei!) si la un sprint de sanatate din partea concurentilor (felicitari mai ales lor!) care ne-au convins inca o data ca tinerii nostri sunt pregatiti sa fuga mancand pamantul pentru gloria si renumele olimpiadelor nationale si internationale.
Una peste alta, s-a incheiat o etapa frumoasa a concursului in care am pus mult suflet. Normal, pot fi doar 30 de participanti fericiti de rezultate. Ii felicitam pe cei calificati si abia asteptam sa-i vedem in finala. Ii felicitam si pe ceilalti care nu au putut sa-si tina suflul pana in final, pierzand locurile calificabile. Noi le uram cat mai multe succese, sa mai alerge vreo cateva sute de probleme (incepand cu cele din Arhiva noastra) si sa ne intalnim cu ei mult mai pregatiti la startul urmatorului preONI.
In urmatoarele pagini vom incerca sa explicam solutiile problemelor. Asa cum v-ati obisnuit, va puteti lamuri orice vi se pare neclar sau vag explicat intreband pe forum, unde vom incerca sa raspundem cat mai promt. Va asteptam cu intrebari si sugestii (asigurati-va ca pareririle va sunt auzite!)
In urmatoarele pagini vom incerca sa explicam solutiile problemelor. Asa cum v-ati obisnuit, va puteti lamuri orice vi se pare neclar sau vag explicat intreband pe "forum":http://forum.infoarena.ro/, unde vom incerca sa raspundem cat mai prompt. Va asteptam cu intrebari si sugestii (asigurati-va ca pareririle va sunt auzite!)
h2. NextSeq
(problema simpla clasa a 9-a)
h2. GFact
(problema medie clasa a 9-a)
Primul pas in rezolvarea problemei il reprezinta factorizarea numarului $P$. Acest lucru se poate realiza intr-o complexitate $O(sqrt(P))$. Odata obtinuta factorizarea, vom avea o relatie de forma:
 
Primul pas in rezolvarea problemei il reprezinta factorizarea numarului $P$. Acest lucru se poate realiza intr-o complexitate $O(√P)$. Odata obtinuta factorizarea, vom avea o relatie de forma:
$P = T{~1~}^R1^ * ... * T{~K~}^RK^$
 
Imediat rezulta:
 
$A = T{~1~}^R1 * Q^ * ... * T{~K~}^RK * Q^$
 
Al doilea pas este sa observam ca daca aflam pentru fiecare $T{~i~}$, $B{~i~}$ astfel incat $B{~i~}!$ se divide la $T{~i~}^Ri * Q^$ atunci $B$ (numarul cautat in problema) este maximul dintre $B{~i~}$. Implicatia imediata e ca putem sa ne ocupam de fiecare numar prim in parte fara sa tinem cont de celelalte.
Al treilea pas consta in determinarea $B{~i~}$-urilor cu ajutorul cautarii binare. Pentru o valoare candidata $X$ (din cautarea binara) trebuie sa calculam puterea lui $T{~i~}$ in descompunerea lui $X!$. Acest lucru se afla simplu ca fiind $[X/T{~i~}] + [X/(T{~i~}^2^)] + ... (unde prin $[x]$ intelegem partea intreaga a lui $x$). Cautarea binara se poate optimiza observand ca $B{~i~}$ este intotdeauna divizibil cu $T{~i~}$, ba mai mult nu va fi mai mare decat $(R{~i~} * Q) * T{~i~}$ (observatie necesara obtinerii punctajului maxim). In concluzie, vom cauta binar o valoare intreaga $K$ in intervalul $[1, R{~i~} * Q]$ astfel incat $B{~i~} = K * T{~i~}$ sa aiba propietata ca $B{~i~}!$ se divide la $T{~i~}^Ri * Q^$. Va puteti intreba de ce putem cauta binar. Este simplu: daca o valoare $X$ are propietatea ca $X!$ se divide la $Y$ (unde lui $X$ si $Y$ le putem da semnificatiile dorite de noi) atunci, evident, si $(X + 1)!$ se divide la $Y$.
Al treilea pas consta in determinarea $B{~i~}$-urilor cu ajutorul cautarii binare. Pentru o valoare candidata $X$ (din cautarea binara) trebuie sa calculam puterea lui $T{~i~}$ in descompunerea lui $X!$. Acest lucru se afla simplu ca fiind $[X/T{~i~}] + [X/T{~i~}^2^] + ...$ (unde prin $[x]$ intelegem partea intreaga a lui $x$). Cautarea binara se poate optimiza observand ca $B{~i~}$ este intotdeauna divizibil cu $T{~i~}$, ba mai mult nu va fi mai mare decat $(R{~i~} * Q) * T{~i~}$ (observatie necesara obtinerii punctajului maxim). In concluzie, vom cauta binar o valoare intreaga $K$ in intervalul $[1, R{~i~} * Q]$ astfel incat $B{~i~} = K * T{~i~}$ sa aiba propietatea ca $B{~i~}!$ se divide la $T{~i~}^Ri * Q^$. Va puteti intreba de ce putem cauta binar. Este simplu: daca o valoare $X$ are propietatea ca $X!$ se divide la $Y$ (unde lui $X$ si $Y$ le putem da semnificatiile dorite de noi) atunci, evident, si $(X + 1)!$ se divide la $Y$.
Solutia finala va avea complexitatea $O(√P * log Q * log Q)$. Exista o serie de solutii intermediare care permiteau obtinerea de punctaje suficient de mari si de aceea problema a fost considerata medie desi rezolvarea completa este destul de dificila.
h2. Matrix
 
(problema grea clasa a 9-a, problema medie clasa a 10-a)
Primul pas al algoritmului este calcularea numarului de aparitii ale fiecarei litere in matricea de N*N. Prima idee care ne vine in minte este ca pentru toate submatricile posibile sa calculam numarul de aparitii ale fiecarei litere si sa comparam cu valorile care trebuie obtinute. Acest algoritm are complexitatea O(M^2*(N+S)), unde S este dimensiunea alfabetului. Aceasta abordare obtine 50 de puncte. Vom verifica pentru toate cele (M-N)^2 matrici posibile daca sunt sau nu permutari ale matricii-template. Apoi, pentru fiecare litera a alfabetului, efectuam urmatoarea preprocesare pentru a putea calcula in O(1) numarul de aparitii ale literei din orice submatrice: T[i][j] = numarul de aparitii pe pozitii (x, y) cu 1 <= x <= i si 1 <= y <= j.
Relatia de recurenta este T[i][j] = T[i-1][j]+T[i][j-1]-T[i-1][j-1], la care se adauga 1 daca si numai daca pe pozitia (i, j) se afla litera pe care o cautam. In aceste conditii, numarul de aparitii ale literei curente in submatricea cu colturile in (i-N+1, j-N+1) si (i, j) este T[i][j]-T[i-N][j]-T[i][j-N]+T[i-N][j-N]. Aceasta solutie are complexitatea O(M^2*S). Daca se foloseste O(M^2*S) memorie se obtin 70-80 de puncte, iar pentru punctaj maxim este necesara reducerea la O(M^2). Acest lucru poate fi realizat folosind doua matrici, una in care tinem minte daca pentru o anumita pozitie s-a gasit vreo litera pentru care numarul de aparitii nu coincide cu cel dorit, si una in care se efectueaza preprocesarea pentru litera curenta. O alta optimizare, mult mai nesimnificativa, si care nu este necesara pentru 100 de puncte, este renuntarea la verificarea pentru ultima litera, deoarece daca primele 25 de litere s-au potrivit, iar numarul de litere este constant, e clar ca si cea de-a 26-a litera se va
potrivi.
Primul pas al algoritmului este calcularea numarului de aparitii ale fiecarei litere in matricea de $N*N$. Prima idee care ne vine in minte este ca pentru toate submatricile posibile sa calculam numarul de aparitii ale fiecarei litere si sa comparam cu valorile care trebuie obtinute. Acest algoritm are complexitatea $O(M^2^*(N+S))$, unde $S$ este dimensiunea alfabetului. Aceasta abordare obtine $50$ de puncte.
Vom verifica pentru toate cele {@(M-N)@}$^2^$ matrici posibile daca sunt sau nu permutari ale matricii-template. Apoi, pentru fiecare litera a alfabetului, efectuam urmatoarea preprocesare pentru a putea calcula in $O(1)$ numarul de aparitii ale literei din orice submatrice: $T{~i,j~}$ = numarul de aparitii pe pozitii $(x, y)$ cu $1 &le; x &le; i$ si $1 &le; y &le; j$.
 
Relatia de recurenta este $T{~i,j~} = T{~i-1,j~}+T{~i,j-1~}-T{~i-1,j-1~}$, la care se adauga $1$ daca si numai daca pe pozitia $(i, j)$ se afla litera pe care o cautam. In aceste conditii, numarul de aparitii ale literei curente in submatricea cu colturile in $(i-N+1, j-N+1)$ si $(i, j)$ este $T{~i,j~}-T{~i-N,j~}-T{~i,j-N~}+T{~i-N,j-N~}$. Aceasta solutie are complexitatea $O(M^2^*S)$. Daca se foloseste $O(M^2^*S)$ memorie se obtin $70-80$ de puncte, iar pentru punctaj maxim este necesara reducerea la $O(M^2^)$. Acest lucru poate fi realizat folosind doua matrici, una in care tinem minte daca pentru o anumita pozitie s-a gasit vreo litera pentru care numarul de aparitii nu coincide cu cel dorit, si una in care se efectueaza preprocesarea pentru litera curenta. O alta optimizare, mult mai nesimnificativa, si care nu este necesara pentru $100$ de puncte, este renuntarea la verificarea pentru ultima litera, deoarece daca primele $25$ de litere s-au potrivit, iar numarul de litere este constant, e clar ca si cea de-a $26$-a litera se va potrivi.
h2. Lista lui Andrei
(problema usoara clasa a 10-a)
Problema se rezolva folosind programare dinamica. Putem tine o matrice $V{~1..N~}{~1..26~}$ unde $V{~i,j~}$ reprezinta numarul de siruri de lungime $i$ ce contin ultima litera $j$. Incepem completarea matricii in ordine crescatoare a lungimii sirurilor, iar $V{~i,j~}$ se obtine prin insumarea valorilor V{~i-1,k~}, pentru orice $k$ a.i perechea $(k, j)$ sau $(j, k)$ sa nu se regaseasca in lista. Acest rationament conduce la un algoritm in $O(N * &#931;^2^)$, unde $&#931;$ reprezinta marimea alfabetului (in cazul nostru $26$).
 
Calcul
Problema se rezolva folosind programare dinamica. Putem tine o matrice $V{~1..N~}{~1..26~}$ unde $V{~i,j~}$ reprezinta numarul de siruri de lungime $i$ ce contin ultima litera $j$. Incepem completarea matricii in ordine crescatoare a lungimii sirurilor, iar $V{~i,j~}$ se obtine prin insumarea valorilor $V{~i-1,k~}$, pentru orice $k$ a.i perechea $(k, j)$ sau $(j, k)$ sa nu se regaseasca in lista. Acest rationament conduce la un algoritm in $O(N * &#931;^2^)$, unde $&#931;$ reprezinta marimea alfabetului (in cazul nostru $26$).
h2. Calcul
(problema grea clasa a 10-a, problema medie clasele 11-12)
Deoarece se cer doar ultimele C cifre se va lucra modulo 10^C. Asadar, la primul pas se va calcula A modulo 10^C, adica ne intereseaza doar ultimele C cifre din A.
O prima solutie pentru a calcula A^1 + A^2 + ... + A^B este de calcula A^i in O(lg i) pentru fiecare i folosind algoritmul clasic de ridicare la o putere in numar logaritmic de pasi (Cormen, capitolul 33). Aceasta solutie ar fi adus doar 20p.
Suma prezentata este o progresie geometrica clasica, si se poate calcula folosind formula (A^(B+1)-A) / (A-1). Calculul lui A^(B+1) se face folosind acelasi algoritm mentionat mai sus in O(lg B) (lg = logaritm in baza 2). Pentru a efectua impartirea modulo 10^C, trebuie sa existe un invers multiplicativ pentru A-1 , modulo 10^C, lucru garantat doar pentru 50% din teste (cmmdc(A-1, 10^C) = 1). Inversul multiplicativ poate fi calculat folosind algoritmul [2]Euclid extins sau teorema lui Fermat: X^phi(N) = 1 (mod N) pentru cmmdc(X, N) = 1 si phi(N) = indicatorul lui Euler, cate numere < N sunt prime cu N. Din teorema reiese ca X^(phi(N)-1) = X^(-1) (mod N), asadar inversul poate fi calculat algoritmul de ridicare la o putere mentionat mai sus (phi(10^C) poate fi calculat usor). Un caz special la aceasta solutie apare atunci cand A = 1. Aceasta solutie n-ar fi adus decat 50p si necesita cunostiinte de matematica de clasa a 12-a. Exista o solutie mult mai accesibila pentru clasele a 10-a si a 11-a, folosind
Deoarece se cer doar ultimele $C$ cifre se va lucra modulo $10^C^$. Asadar, la primul pas se va calcula $A$ modulo $10^C^$, adica ne intereseaza doar ultimele $C$ cifre din $A$.
O prima solutie pentru a calcula $A^1^ + A^2^ + ... + A^B^$ este de calcula $A^i^$ in $O(lg i)$ pentru fiecare $i$ folosind algoritmul clasic de ridicare la o putere in numar logaritmic de pasi (Cormen, capitolul 33). Aceasta solutie ar fi adus doar $20p$.
 
Suma prezentata este o progresie geometrica clasica, si se poate calcula folosind formula $(A^B+1^-A) / (A-1)$. Calculul lui $A^(B+1)^$ se face folosind acelasi algoritm mentionat mai sus in $O(lg B)$ ({$lg$} = logaritm in baza 2). Pentru a efectua impartirea modulo $10^C^$, trebuie sa existe un invers multiplicativ pentru $A-1$ , modulo $10^C^$, lucru garantat doar pentru $50%$ din teste $(cmmdc(A-1, 10^C^) = 1)$. Inversul multiplicativ poate fi calculat folosind algoritmul Euclid extins sau teorema lui Fermat: $X^phi(N)^ = 1 (mod N)$ pentru $cmmdc(X, N) = 1$ si $phi(N)$ = indicatorul lui Euler, cate numere < $N$ sunt prime cu $N$. Din teorema reiese ca $X^phi(N)-1^ = X^-1^ (mod N)$, asadar inversul poate fi calculat algoritmul de ridicare la o putere mentionat mai sus ({$phi(10^C^)$} poate fi calculat usor). Un caz special la aceasta solutie apare atunci cand $A = 1$. Aceasta solutie n-ar fi adus decat $50p$ si necesita cunostiinte de matematica de clasa a 12-a.
 
Exista o solutie mult mai accesibila pentru clasele a 10-a si a 11-a, folosind
relatiile:
S(A,2*B) = S(A,B) * (1+A^B)
S(A,2*B+1) = A * (1+S(A,2*B))
Cum numarul B este dat in baza 16, parcurgerea bitilor acestuia se face usor, simuland algoritmul de mai sus. Daca A^B se calculeaza la fiecare pas, complexitatea va fi O(lg^2 B), obtinand 60p. O solutie O(lg B) de 100 de puncte se poate obtine calculand in paralel si valorile S(A,B) si A^B. O ultima "problema" care ar fi putut exista este faptul ca se cer ultimele C cifre, nu rezultatul modulo 10^C; spre exemplu, daca C = 4 si rezultatul modulo 10^4 ar fi fost "123", in fisierul de iesire trebuia afisat "0123".
$S(A,2*B) = S(A,B) * (1+A^B^)$
$S(A,2*B+1) = A * (1+S(A,2*B))$
Cum numarul $B$ este dat in baza $16$, parcurgerea bitilor acestuia se face usor, simuland algoritmul de mai sus. Daca $A^B^$ se calculeaza la fiecare pas, complexitatea va fi $O(lg^2^ B)$, obtinand $60p$. O solutie $O(lg B)$ de $100$ de puncte se poate obtine calculand in paralel valorile $S(A,B)$ si $A^B^$. O ultima "problema" care ar fi putut exista este faptul ca se cer ultimele $C$ cifre, nu rezultatul modulo $10^C^$; spre exemplu, daca $C = 4$ si rezultatul modulo $10^4^$ ar fi fost $"123"$, in fisierul de iesire trebuia afisat $"0123"$.
h2. Distante minime
(problema usoara clasele 11-12)
Mai intai vom calcula, pentru fiecare pereche de puncte $A$ si $B$ din punctele ce reprezinta vizuinele, in sirul $sub{~AB~}$ cate puncte din restul de $n$ se afla sub segmentul de dreapta determinat de $A$ si $B$. Aceasta preprocesare poate fi efectuata in $O(n^2^ log n)$ cu un algoritm inteligent sau poate fi efectuata in $O(n^3^)$ cu metoda naiva care verifica pentru fiecare punct daca este situat pe intervalul $[A.x, B.x]$ si este sub dreapta determinata de cele doua puncte. Preprocesare vom putea pentru fiecare triunghi $ABC$ sa aflam in timp $O(1)$ cate puncte are in interior: presupunem fara a restrange generalitatea ca $A.x &le; B.x &le; C.x$, daca punctul $B$ e deasupra dreptei $AC$ atunci numarul de puncte din interiorul lui $ABC$ este $sub{~AB~} + sub{~BC~} - sub{~AC~}$, iar daca $B$ este sub dreapta $AC$ atunci numarul de puncte este $sub{~AC~} - sub{~AB~} - sub{~BC~} - 1$.
Orice patrulater, fie el concav sau convex, are o diagonala interna. Daca fixam un segment $PQ$ ca fiind diagonala interna putem sa incercam sa gasim pentru fiecare $x$ triunghiul $PQR$ de arie minima pentru care punctul $R$ este deasupra dreptei $PQ$ si care contine in interior cel putin $x$ puncte, iar apoi sa gasim un triunghi $PQS$ de arie minima cu varful $S$ sub dreapta $PQ$ ce contine in interior cel putin $k-x$ puncte. Ariile minime ale acestor triunghiuri se pastreaza in doua siruri over si under iar aria minima a unui patrulater cu o diagonala $PQ$ va fi $min(over{~x~} + under{~k-x~} | unde x ia toate valorile de la 0 la k)$. Folosind artificiul explicat mai sus putem determina in $O(1)$ numarul de puncte ce se afla in interiorul unui triunghi, si astfel sirurile $over$ si $under$ pot fi calculate in $O(n)$. Complexitatea totala a algoritmului este $O(n^3^)$ pentru ca avem $O(n^3^)$ calcule in faza de preprocesare si pentru fiecare $n(n-1)/2$ diagonale vom efectua $O(n)$ calcule.
 
References
 
Visible links
1.
2. http://info.devnet.ro/articole.php?page=art&art=26
 

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.