100 - MaxSquare
Complexitate O(n4)
Se fixeaza un colt al patratului pe care il analizam (complexitate O(n2)) - cel mai simplu, cel din dreapta sus. Se mai fixeaza apoi si latura patratului. Cu aceste trei elemente determinate (coordonatele unui colt, respectiv latura patratului), acesta este unic determinat. Acum, tot ce mai avem de facut este sa iteram printre elementele conturului patratului selectat si sa le aflam suma. Fixarea lungimii laturii si iterarea printre elementele perimetrului sau iau inca O(n2) timp de executie, deci, complexitatea timp totala a acestei prime solutii este O(n4). Complexitate O(n3)
Cu o simpla observatie, putem reduce complexitatea solutiei de mai sus la O(n3). Observam ca daca avem un patrat cu colturile in (x1,y1), respectiv in (x2,y2), suma elementelor conturului sau se poate exprima ca suma a doua intervale de linii si a doua intervale de coloane. Concret, ne vom folosi de tehnica sumelor partiale pentru a reduce complexitatea rezolvarii de mai sus cu un ordin de N. Astfel, vom precalcula 2 matrici h[i][j] si v[i][j] dupa urmatoarea recurenta: h[i][j]=h[i][j-1]+mat[i][j] v[i][j]=v[i-1][j]+mat[i][j]unde
h[i][0]=0 si v[0][j]=0 Acum, in functie de implementare, este posibil sa avem un caz particular pentru subpatratele de latura 1. In general, suma conturului patratului cu colturile in (x1,y1), respectiv in (x2,y2) este h[x2][y2]-h[x2][y1-1]+h[x1][y2]-h[x1][y1-1]+v[x2-1][y2]-v[x1][y2]+v[x2-1][y2]-v[x1][y2] Formula de mai sus poate parea complicata, dar, daca cititorul va incerca sa o deduca singur o va intelege cu siguranta.
Asadar, aflarea sumei de pe contur a fost coborata de la O(n) la O(1) printr-o preprocesare in O(n2), aceasta neafectand insa complexitatea totala a algoritmului.
Complexitate totala: O(n3)
Lasam ca tema de gandire cititorului rezolvarea problemei in cazul in care avem lucram cu dreptunghiuri in loc de patrate in complexitate O(n4). Mentionez ca in acest caz exista o arie mult mai variata de cazuri particulare ce vor trebui tratate. O alta idee interesanta este rezolvarea problemei cu produse in loc de sume in O(n3) pentru cazul cu patrate (extensia pentru cazul cu dreptunghiuri devenind triviala ca idee in cazul in care deja se cunoaste solutia pentru problema cu sume pe dreptunghiuri).
250 - 2AM Rule
O greseala pe care au facut-o multi participanti a fost citirea incorecta. Regulamentul olimpiadei spune ca fisierele se termine cu un caracter newline, lucru pe care multi participanti nu l-au luat in considerare, tratand si ultima "linie" (goala) ca o expresie.
Intrucat operatorii + si - sunt echivalenti, incepem prin a inlocui + cu - (1). Apoi verificam daca sirul incepe cu -, se termina cu -, sau contine subsirurile [- sau -], caz in care returnam ERROR (2). Continuam prin inlocuirea subsirurilor de forma [ceva] cu +ceva (3).
Acum avem o expresie delimitata de caracterul -. Consideram separat fiecare token (4):
- Daca e egal cu
bxsaubp(case-insensitive), incrementam numarul de base registers (5) - Daca e egal cu
sisaudi(case-insensitive), incrementam numarul de index registers (6) - Daca e egal cu o litera lowercase, incrementam numarul de variabile (7)
- Daca e numar, trecem mai departe (8)
- Daca nu e niciuna din cele de mai sus, returnam ERROR (9)
Sursa oficiala:
1 #!/usr/bin/perl -w 2 use v5.14; 3 no if $] >= 5.017011, warnings => 'experimental::smartmatch'; 4 5 sub ok{ 6 chomp; # Remove the final newline 7 y/+/-/; # (1) Replace + with - 8 return if /^-|-$|\[-|-\]/; # (2) ERROR if the string starts/ends with a - or if it contains [- or -] 9 1 while s/\[([^[\]]+)]/-$1/; # (3) Replace [...] with -... 10 my ($base, $index, $vars) = (0, 0, 0); 11 for (split '-'){ # (4) Tokenize the expression, using '-' as the delimiter 12 $base++ when m/^bx$|^bp$/i; # (5) If the current token is bx or bp, increment $base 13 $index++ when m/^si$|^di$/i; # (6) If the current token is si or di, increment $index 14 $vars++ when m/^[a-z]$/; # (7) If the current token is a lowercase letter, increment $vars 15 1 when m/^\d*$/i; # (8) If the current token is a number, do nothing 16 default { return } # (9) Otherwise ERROR 17 } 18 19 $base < 2 && $index < 2 && $vars < 2 # (10) 20 } 21 22 say ok() ? 'OK' : 'ERROR' while <>;
500 - Big Integers
Matrici
RecurentaX[i] = 2 (102), i == 1 sau (X[i-1] * 2k+1 + 2k) % 666013 se poate transpune in inmultiri de matrici | 2k+1 1 0 | | Xk | | Xk+1| | 0 1 0 | x | 2k | = | 2k | | 0 0 1 | | 1 | | 1 |
Matematica
Se observa ca elementullX[i] este suma termenilor unei progresii geometrice cu ratia 2k+1 , se aplica formula pentru suma de termeni de progresie geometrica. Sum = b*(qn-1)/(q-1). Deoarece raspunsul trebuie afisat modulo 666013 vom folosi invers modular pentru impartire. Solutia Smen
Se identifica ciclurile si se preproceseaza Din cauza ca de laX[i] mergem la X[i] * 2k+1 + 2k se formeaza cicluri pe baza resturilor De exemplu pentru k = 1 se formeaza ciclu la i = 333006 de la valoarea 0, pentru k = 3 la i = 166503, pentru k = 13 tot la i = 333006 cu valoarea 0.
Acum ca sa calculam restul celui de al i-lea nr din X trebuie doar sa calculam restul lui i la perioada si sa afisam restul pentru acel numar.
1000 - Evil Geometry
(a*eps, b*eps), eps fiind o constanta fixata) din patratul cu colturi (-75, -75) si (75, 75) si apoi numara cate din ele sunt in interiorul a macar una dintre elipse. Notand acest numar cu b, aria devine b * eps2. Aceasta solutie insa iese din timp, avand o complexitate de O(1/eps2). O optimizare care duce la AC este urmatoarea:
Parcurgem liniile din eps in eps, si pentru fiecare linie parcurgem coloanele din eps*step in eps*step. Retinem la fiecare moment daca ne aflam in interiorul unei elipse sau nu. Daca la un pas de lungime step iesim sau intram din reuniunea elipselor, parcurgem fiecare din aceste step puncte in parte. Solutia oficiala, cu eps = 3e-2 si step = 100
1 #include <iostream> 2 #include <iomanip> 3 #include <cstdlib> 4 #define FACT 300 5 #define STEP 100 6 using namespace std; 7 8 static struct { 9 long long x, y, a, b, aa, bb, limit; 10 11 void read() { 12 cin>>x>>y>>a>>b; 13 x*=FACT, y*=FACT; 14 limit = a * a * b * b * FACT * FACT; 15 } 16 17 bool inside(long long px, long long py) { 18 return (px - x) * (px - x) * b * b + (py - y) * (py - y) * a * a <= limit; 19 } 20 }e1, e2, e3; 21 22 bool inside(int i, int j){ 23 return e1.inside(i, j) || e2.inside(i, j) || e3.inside(i, j); 24 } 25 26 int main() { 27 e1.read(); e2.read(); e3.read(); 28 long long bune=0; 29 for(int i = -75 * FACT; i < 75 * FACT; i++){ 30 int j = -75 * FACT; 31 bool last = 0; 32 for(; j < 75 * FACT; j+=STEP){ 33 bool cur = inside(i, j); 34 if(cur != last) 35 for(int k = 0; k < STEP; k++) 36 bune += inside(i, j-k); 37 else if(cur) 38 bune += STEP; 39 last = cur; 40 } 41 } 42 cout << fixed << setprecision(6) << 1.0 * bune / FACT / FACT; 43 }
Solutie cu 'patratele' (Catalin-Stefan Tiseanu)
Vom incerca sa aproximam aria ceruta (in cazul acesta, a reuniunii de elipse, pe care o vom numi U) cu patratele.Ideea de baza este ca atat timp cat o zona a patratelului curent nu este in totalitate in U, il impartim in 4 sub patratele egale si apelam recursiv.
Daca zona patratelului este total in afara lui U, ne oprim pt patratelul curent si returnam 0.
Daca zona patratelului este total in U, ne oprim si returnam aria lui. Apelul recursiv se opreste cand aria patratelului curenta este suficient de mica.
Mai exact, pentru a testa relatia patratelului relativ la U este suficient sa ne uitam la cele 4 colturi ale lui:
- toate in U (in aceeasi elipsa dupa cum vedem mai jos): returnam aria patratelului (este continut in U)
- toata in afara lui U: returnam 0
- cel putin unul in afara lui U si cel putin unul inauntrul lui U: apelam recursiv
O optimizare importanta pentru precizie: trebuie sa verificam pentru cele 4 colturi ca se afla in ACEEASI elipsa, nu este suficient sa se afle in elipse diferite pentru ca pot apare cazuri cand o zona din patratel nu este in U, desi toate cele 4 colturi ale lui sunt in U.
1 // x, y - coordonatele stanga jos ale patratelului 2 // l - latura curenta 3 inline double rec (double x, double y, double l) { 4 double area = l * l; 5 if (area <= EPSILON * EPSILON) 6 return area / 2; 7 ++counter; // cate operatii facem 8 int msk[3] = {1, 1, 1}; 9 int sum = in_ellipses(mp(x, y), msk) + 10 in_ellipses(mp(x + l, y), msk) + 11 in_ellipses(mp(x, y + l), msk) + 12 in_ellipses(mp(x + l, y + l), msk); 13 // (msk[i] == 1) = toate cele 4 puncte se afla in elipsa i 14 // all in same elipse 15 if(msk[0] + msk[1] + msk[2]) 16 return area; // cel putin un msk[i] != 0 => cel putin o elipsa contine toate colturile 17 else if (sum == 0) // toate in afara lui U 18 return 0.0; 19 return rec(x, y, l / 2) + 20 rec(x + l / 2, y, l / 2) + 21 rec(x, y + l / 2, l / 2) + 22 rec(x + l / 2, y + l / 2, l / 2); 23 }Apelul initial se face pe toate patratelele de arie 1 si coordonate intregi din zona de interes (MIN_COORD ... MAX_COORD).
Solutie Mihai Popa
La fel ca in cazul celorlalte solutii, vom incerca sa aproximam aria ceruta. Ne impartim planul in dreptunghiuri de latimeeps = 1e-4 (pe axa OX) si inaltime infinit (pe axa OY). Asadar, planul va fi impartit in dreptunghiuri cu coltul din stanga jos (x,-infinit) si coltul din dreapta sus (x+eps,+infinit). Parcurgem pe rand x-ii care reprezinta o latura a unui dreptunghi si calculam intersectiile lor cu elipsele. Pentru un x fixat, nu este foarte dificil sa calculam suma lungimilor segmentelor paralele cu OY la x-ul curent care se afla in interiorul cel putin unei elipse. Sa notam aceasta suma cu s. Acum putem aduna la solutie s*eps, corespunzand ariei aproximate apartinand dreptunghiului (x,-infinit), (x+eps,infinit) care se afla in interiorul cel putin unei elipse.
