Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-01-22 21:44:59.
Revizia anterioară Revizia următoare

Solutii preONI 2008, Runda 3

Runda a 3-a a concursului preONI 2008 s-a incheiat. Acest articol va prezenta solutiile celor 9 probleme propuse spre rezolvare si cateva aprecieri pe marginea desfasurarii probei de duminica dimineata.

Ca de obicei, concurentii au avut de rezolvat 3 probleme de dificultate variata. Noi am considerat aceasta runda ca fiind mai usoara decat precedentele doua, iar acest lucru s-a putut observa in punctajele obitinute. Multi concurenti au recuperat inainte de ultima batalie pentru cele 10 locuri la Marea Finala preONI 2008.

In fruntea clasamentului de la gimnaziu gasim 2 concurenti cu 280 de puncte: Radu Voroneanu si Andrei Purice. Pe ultimul loc al podiumului, la 30 de puncte in spatele primilor clasati, il gasim pe Serban Andrei Stan. In clasamentul general cei din frunte pot sta linisiti inainte de runda a 4-a, insa lucrurile sunt foarte neclare spre ultimele locuri calificante, cu punctaje stranse si multi concurenti avand sanse de calificare. Problemele au fost destul de usoare, cu multe punctaje de 100. Probabil ca daca unul din primii doi ar fi implementat quicksort la problema medie Restante, am fi asistat la un punctaj maxim :). Mai ramane de precizat faptul ca problema grea, Stergeri, a fost cea care a facut diferenta, ea fiind rezolvata corect doar de primii 3 concurenti clasati.

Spre deosebire de runda anterioara, de aceasta data punctajele la clasa a 9-a au fost mai mici. In fruntea clasamentului este Ioana Pandele. Nu putem sa nu remaracam rezultatele extraordinare pe care le-a obtinut la editia preONI 2008, mai ales avand in vedere ca nu a rezolvat nici macar o problema pe infoarena (cel putin nu de pe acest cont :P). Pe locurile 2 si 3 gasim medaliatii Romaniei cu aur la JBOI 2007, Victor Ionescu si Vlad Tataranu. Un lucru foarte interesant este faptul ca niciun concurent de la clasa a 9-a nu a rezolvat problema usoara, Restante. Acest lucru probabil ca se datoreaza limitei stranse de timp, care nu permitea solutiilor neoptimizate ce nu foloseau quicksort sa obtina punctajul maxim. Problema medie Piese a fost rezolvata de 3 concurenti, iar cea grea, Partitie, doar de Ioana.

Fructe

Se observa ca indiferent de fructele pe care Miruna le mananca, paritatea numarului de banane ramane aceeasi. De aici putem concluziona ca ultimul fruct va fi o banana daca initial aveam un numar impar de banane, si o portocala in caz contrar.

Restante

Pentru fiecare cuvant ii sortam literele in ordine crescatoare. Apoi sortam toate cuvintele in ordine crescatoare. Daca doua cuvinte alaturate din lista de cuvinte sortate sunt egale este clar ca aceste cuvinte nu sunt originale. Dupa sortare putem afla deci in O(N) usor cuvintele care sunt originale, parcurgand lista de cuvinte pas cu pas. Pentru sortare trebuie folosit un algoritm rapid, de exemplu quicksort pentru a obtine complexitatea O(N*L*logN), unde L este lungimea maxima a unui cuvant, in cazul nostru 16.

Stergeri

Sa presupunem ca dupa ce am efectuat toate stergerile am ramas cu valorile X₁, X₂ .. X_k .. X_p. Ne intereseaza ce valoare are X_k (initial X_k=k). Vom considera ordinea inversa a operatiilor, adica plecand de la aceste valori acum nu vom mai face stergeri, vom face inserari de intervale. Altfel spus, in loc sa ne intrebam ce element e pe pozitia K dupa M stergeri, vom afla pe ce pozitie va ajunge al K-lea element dupa M inserari. Daca capatul stanga al unui interval ce trebuie inserat se afla in stanga lui X_k atunci X_k va trebui deplasat la dreapta cu L unitati (L este lungimea intervalului), altfel X_k va ramane neschimbat. Astfel, dupa ce s-au efectuat toate inserarile, daca X_k se va afla pe pozitia T este clar ca T este raspunsul la problema noastra.

Piese

Complexitatea optima este O(M * N) si obtine 100 de puncte. Solutia oficiala se bazeaza pe o abordare recursiva: fie f(x₁, y₁, x₂, y₂) functia care acopera cu un numar minim de piese submatricea de colturi (x₁, y₁), (x₂, y₂). Intuitiv, numarul minim de piese pentru aceasta submatrice se obtine daca in (x₁, y₁) asezam piesa cu latura maxim posibila. Latura maxima este egala cu cel mai mare numar natural k astfel incat 2^k ≤ minim(x₂-x₁+1, y₂-y₁+1). Dupa ce am asezat piesa de latura k pe tabla, apelam recursiv f(x₁, y₁+2^k, x₁+2^k-1, y₂) si f(x₁+2^k, y₁, x₂, y₂). Apelarea este corecta deoarece, din metoda de constructie a functiei f stim sigur ca nu va exista o piesa care sa aiba simultan patratele in submatricile (x₁, y₁+2^k),(x₁+2^k-1, y₂) si (x₁+2^k, y₁),(x₂, y₂).

Partitie

Putem reformula problema astfel: se dau N puncte coliniare (putem sa consideram punctele ca fiind pe axa Ox), fiecare punct avand o coordonata. Trebuie sa coloram punctele cu numar minim de culori astfel incat intre oricare doua puncte colorate la fel sa fie cel putin distanta D.

Lema: Fie un segment AB de lungime D-1 care sa contina un numar maxim de puncte din cele date. Fie MAX numarul de puncte de pe segmentul AB. MAX este numarul minim de culori cerut.

Este evident ca nu putem folosi mai putin de MAX culori. Daca am folosi mai putine culori ar exista (conform principiului cutiei) in segmentul AB doua puncte colorate la fel, dar aceste doua puncte s-ar afla la mai putin de D unitati distanta. In concluzie, numarul minim de culori este cel putin MAX.
Vom demonstra ca exista o constructie cu MAX culori. Avand punctele sortate in functie de coordonata lor, le coloram astfel: 1 2 3 ... MAX 1 2 3 ... MAX 1 2 .... De exemplu, pentru N = 11 si MAX = 3, cele 11 puncte vor fi colorate astfel: (1 2 3 1 2 3 1 2 3 1 2). Se observa ca intre oricare doua puncte colorate la fel (inclusiv capetele) exista cel putin MAX+1 puncte si deci distanta dintre ele va fi sigur mai mare sau egala cu D, deoarece, in caz contrar, ar exista un segment de lungime D-1 care sa contina cel putin MAX+1 puncte - evident fals, din moment ce am presupus ca MAX este numarul maxim de puncte de pe un segment de lungime D-1.

Asadar, pentru a rezolva problema trebuie sa gasim segmentul AB de lungime D-1 care contine un numar maxim de puncte din cele date in interior si vom colora punctele dupa cum s-a prezentat mai sus. Segmentul AB va avea capatul din stanga ( mai mic ) intr-unul din cele N puncte. In caz contrar, AB ar putea fi translatat spre dreapta pana punctul A ajunge peste unul din punctele date si, in acest caz, AB ar contine un numar mai mare sau egal de puncte decat initial. Fie C vectorul de coordonate. Daca avem acest vector sortat crescator, pentru fiecare i trebuie sa gasim acel indice maxim j ≥ i astfel incat C_j-C_i ≤ D-1, iar, in final, MAX va fi maximul dintre valorile de forma j-i+1. Pentru ca acest pas sa aiba complexitatea O(N), in momentul in care cautam indicele j pentru indicele curent i nu vom incepe cautarea de la i, ci de la j-ul obtinut anterior.

Complexitatea solutiei prezentate este O(Nlog₂N), iar complexitatea dupa sortare este O(N). Algoritmul descris obtine 100 de puncte.

Gardieni

Problema cere ca, dandu-se N intervale si un cost pentru fiecare interval, sa asociem fiecarui moment x din [1, T] exact un interval din cele N care sa contina momentul x. Costul pentru x va fi costul intervalului asociat. Trebuie sa gasim acea asociere care minimizeaza suma costurilor tuturor momentelor de la 1 la T.
Problema se rezolva prin metoda greedy: fiecarui moment i de la 1 la T ii vom asocia intervalul de cost minim ce il contine pe i. O prima solutie (neeficienta) are complexitatea O(T * N). Pseudocodul este prezentat mai jos:

Cost_Total = 0
pentru fiecare moment i de la 1 la T
       minim = INFINIT // o valoare foarte mare
       pentru fiecare interval i de capete x[i] si y[i]
              daca (x[i] <= i) si (i <= y[i]) si (c[i] < minim)
                    minim = c[i]
       Cost_Total = minim

Datorita restrictiei ca numarul maxim de intervale care se intersecteaza este maxim 10, stim ca suma lungimilor intervalelor este maxim 10*T, deci (y₁-x₁+1) + (y₂-x₂+1) + ... + (y_N-x_N+1) ≤ 10*T. Pseudocodul de mai jos, desi aparent are complexitatea tot O(T * N), are complexitatea reala O(T), de constanta de 10:

// minim[i] = costul minim al unui interval ce contine punctul i
pentru fiecare moment i de la 1 la T
       minim[i] = INFINIT // o valoare foarte mare
pentru fiecare interval i (x[i], y[i]) de cost c[i]
       pentru fiecare moment j de la x[i] la y[i]
              daca c[i] < minim[j]
                   minim[j] = c[i]
Cost_Total = 0
pentru fiecare moment i de la 1 la T
       Cost_Total = Cost_Total + minim[i]

Aceasta abordare obtine 100 de puncte.
Exista si o solutie de complexitate O(Nlog₂N) care are avantajul ca rezolva problema pe cazul general, in care nu exista nicio restrictie asupra numarului maxim de intervale care se intersecteaza. Aceasta abordare foloseste procedeul numit baleiere si o structura de date numita heap. Daca nu descoperiti singuri ideea din spatele acestei abordari puteti sa intrebati pe forum.

Inundatii

O prima observatie necesara in rezolvarea problemei este urmatoarea: putem rezolva problema independent pentru valorile X, Y si Z datorita functiei de distanta. Astfel, avem de rezolvat de fapt urmatoarea problema: Se da un sir de N numere intregi A₁,A₂...A_N cu A_i > A_i+1, sa se gaseasca un sir de numere intregi B₁,B₂...B_N cu B_i < B_i+1 care minimizeaza suma |A_i-B_i|. Vom rezolva astfel aceasta problema pentru X, Y si Z, la final adunand rezultatele.
Vom mai simplifica un pic problema, inlocuind restrictia B_i < B_i+1 cu B_i ≤ B_i+1 astfel: scadem din A_i valoarea i, rezolvam pentru ≤, si la final adunam i la loc in A si B.
Exemplu:

A = (10, 7, 4, 1)
Scadem i si obtinem A = (9, 5, 1, -3)
Gasim un B optim care respecta B_i ≤ B_i+1. Sunt mai multe solutii posibile, vom lua B = (5, 5, 5, 5)
Adunam la loc i si obtinem ca solutia este B = (6, 7, 8, 9)

Se poate observa ca pentru a obtine rezultat optim pentru problema simplificata, B va avea valori egale. Daca privim valorile din A si valoarea din B pe care o cautam ca puncte pe axa, putem recunoaste problema clasica a oficiului postal in 1 dimenisune (se gaseste si in Cormen la capitolul de Statistici si ordine). Putem trage imediat concluzia ca valoarea din B pe care o cautam va fi mediana lui A (nu conteaza pe care o luam cand N e par). Valorile din A sunt sortate descrescator (si dupa scadere), deci putem determina mediana in O(1).

O solutie alternativa foloseste cautare ternara in O(N*log_1.5(N)). Pentru sirul A de mai sus fie functia f:[A_N, A₁] -> R, cu f(x) costul obtinerii din inegalitatile A₁ > .. > A_i >= x >= A_i+1 > .. > A_N pe urmatoarele A₁ < .. < A_i <= x <= A_i+1 < .. < A_N cu A₂ = A₁ + 1, .. A_N = A₁ + (N-1) pentru minimalitate. Functia f indeplineste proprietatea necesara pentru aplicarea cautarii ternare: exista un X astfel inca functia descreste pe intervalul [A_N, X] si isi schimba monotonia pe [X, A₁]. Pentru determinarea acestui punct folosim cautarea ternara si in final rezultatul va fi f(X).

Xerox

Pe baza urmatoarelor observatii, vom reduce problema la a rezolva jocul NIM:

Pentru o foaie data, pozitiile punctelor nu conteaza. Intr-adevar, atat timp cat punctele sunt distincte, vom putea duce intotdeauna o curba inchisa, suficient de subtire, pe langa celelelalte puncte.
Considerand o foaie cu N puncte, dupa selectarea unei curbe, vom putea lasa celuilalt jucator o foaie cu 0, 1, ..., sau N-1 puncte. Acest lucru se poate face trasand curba prin N, N-1, ..., respectiv 1 punct. Asadar, dintr-o stare cu N puncte, putem ajunge in oricare din starile 0, 1, ..., N-1.
Prin obtinerea unei stari din alta, putem rearanja punctele pe foaie (am observat ca pozitiile punctelor nu conteaza). Asadar, geometria foii nu conteaza, chiar daca dupa selectare forma dreptunghiului se distruge.
Dintr-o stare cu N puncte se poate ajunge si in alte stari prin scindarea foii in alte doua, selectand pe o curba i puncte, ingloband in interiorul ei alte j puncte si lasand in afara ei restul de N-i-j. Totusi, nu vom face astfel de scindari, fiind suficiente observatiile de la punctul 2.

Problema devine: avem N foi (gramezi), fiecare cu cate un numar M_i de puncte (pietre) pe (in) ea. Fiecare foaie (gramada) cu M_i puncte (pietre) poate ajunge intr-o stare cu 0, 1, ..., sau M_i-1 puncte (pietre) prin trasarea unei curbe prin (luarea unui numar de) puncte (pietre). Aceasta este chiar problema jocului NIM.

Strazi

Reformuland problema, trebuie sa adaugam un numar minim de muchii intr-un graf orientat aciclic astfel incat sa existe un drum hamiltonian. Un drum este o insiruire de noduri X₁ X₂ .. X_K astfel incat sa existe o muchie intre oricare doua noduri consecutive. Printr-o acoperire cu drumuri a grafului vom defini o multime de drumuri astfel incat fiecare nod din graf apare exact intr-un singur drum. Daca multimea de drumuri are cardinalul minim, atunci acoperirea este minima. Sa presupunem acum ca am gasit o astfel de acoperire minima, multimea de drumuri fiind formata din drumurile D₁, D₂ .. D_P.
Daca adaugam cate o muchie de la ultimul nod din drumul D_i la primul nod din drumul D_i+1 atunci graful nou format va contine un drum hamiltonian, deoarece toate nodurile din graf apar exact o singura data intr-un drum iar acum toate drumurile au fost unite. Este usor de vazut ca acesta este si numarul minim de muchii care trebuie adaugat (se demonstreaza usor prin reducere la absurd, daca ar exista un numar mai mic de muchii care ar putea fi adaugat atunci acoperirea cu drumuri obtinuta anterior nu ar mai fi minima). Sa ne concentram acum pe gasirea unei acoperiri minime. Vom construi un graf bipartit, in partea stanga vom pune nodurile de la 1 la N iar in partea dreapta de asemenea nodurile de la 1 la N. Sa alegem drumul D₁ reprezentat prin succesiunea de noduri x₁ x₂ .. x_t. Acest drum il vom reprezenta in graful bipartit astfel: vom trage muchie de la nodul x₁ din partea stanga la nodul x₂ din partea dreapta, de la nodul x₂ din partea stanga la nodul x₃ din partea dreapta etc. Vom face acelasi lucru pentru drumurile D₂ .. D_P si observam ca la sfarsit fiecare nod din graful bipartit are maxim un vecin. Mai mult, numarul de noduri din partea stanga din care nu pleaca nici o muchie este egal cu numarul de drumuri din acoperire. Pe noi ne intereseaza ca acest numar sa fie cat mai mic, deci trebuie sa existe un numar cat mai mic de noduri din partea stanga a grafului bipartit care nu au niciun vecin. Pentru a gasi acoperirea minima, pentru fiecare muchie x->y din graful initial vom plasa o muchie de la nodul x din partea stanga a grafului bipartit la nodul y din partea dreapta si vom rula un algoritm de cuplaj maxim. (cuplajul maxim ne garanteaza faptul ca am "cuplat" cat de multe noduri posibile din partea stanga a grafului bipartit)

infoarena informatica de performanta