Solutii preONI 2008, Runda 1

comentarii aici...

• Lista de probleme
• Ordine
• Multimi 2
• Ecuatie
• Economie
• Teren
• Pairs
• Aliens
• Tunelul groazei
• NKPerm

Ordine

Vom forma pas cu pas sirul solutie inserand de fiecare data primul caracter posibil (prin primul caracter posibil intelegem cel mai mic din punct de vedere lexicografic). Daca am inserat caractere pe primele x-1 pozitii si acum ne aflam pe pozitia x, este clar ca acest caracter este in primul rand diferit de caracterul de pe pozitia x-1. Acum daca exista un caracter care apare de (N-x+1)/2+1 ori, atunci acesta este singurul caracter pe care il putem insera, altfel vom insera primul disponibil diferit de cel de pe pozitia x-1. Daca avem un sir de lungime P si un caracter apare de P/2+1 ori singurul mod de constructie a sirului este cx₁cx₂cx₃c....cx_kc.. unde c este caracterul majoritar iar prin x₁, x₂..x_k.. am notat celelalte caractere diferite de c. Complexitatea solutiei este O(sigma*N), unde sigma este dimensiunea alfabetului, in cazul nostru 26. Plecand de la aceasta idee se poate obtine usor si un algoritm O(N), dar acesta nu era necesar pentru obtinerea punctajului maxim.

Multimi 2

Daca N este de forma 4*p vom imparti cele N numere in grupe de cate patru numere de forma 4k, 4k+1, 4k+2, 4k+3. Observam ca 4k-(4k+1)-(4k+2)+(4k+3)=0. Numerele de forma 4k si 4k+3 le vom plasa in prima multime iar celelalte in a doua multime si vom obtine diferenta 0 minim posibila. Daca N da restul 1 la impartirea cu 4, N-1 este divizibil cu 4, vom imparti numerele de la 2 la N in grupe de cate patru ca la pasul anterior si vom plasa numarul 1 in oricare din cele doua multimi si vom obtine diferenta 1. Daca N da restul 2 la impartirea cu 4, vom incepe prin a imparti numerele de la 3 la N iar apoi pe 1 il vom introduce intr-o multime iar pe 2 in cealalta, astfel vom obtine diferenta 1. Daca N da restul 3 la impartirea cu 4 vom imparti in grupe de cate patru numerele de la 4 la N, numerele 1 si 2 le vom introduce intr-o multime, iar 3 in cealalta si vom obtine diferenta 0. Complexitatea solutiei este O(N).

Ecuatie

Dupa cum bine stim de la matematica putem rescrie o ecuatie Ax²+Bx+C ca A(x-x₁)(x-x₂) unde x₁,x₂ sunt solutiile ecuatiei. Acestea se pot determina astfel:

• Fie delta = b²-4ac
• x₁ = (-b-√delta)/2a
• x₂ = (-b+√delta)/2a

Este evident ca o prima condite ca sa putem rescrie ecuatia sub forma (P₁x+Q₁)(P₂x+Q₂) unde P₁,P₂,Q₁,Q₂ sunt numere intregi este ca delta sa fie patrat perfect.
Din cele mai sus putem deduce ca:
(P₁x+Q₁)(P₂x+Q₂) = P₁P₂(x+Q₁/P₁)(x+Q₂/P₂) = A(x-x₁)(x-x₂)
Este imediat evident ca P₁ trebuie sa fie un divizor al numarului A. Vom lua astfel fiecare divizor d al numarului A (atentie la semn! pentru 2 se vor lua valorile 1,-1,2,-2) si vom atribui urmatoarele valori:

pentru d = 1, sqrt(|A|):
    daca A%d = 0:
        d, -d, A/d, -A/d sunt divizori

Economie

Sortam crescator sirul de valori si putem observa ca valoarea cea mai mica din sir sigur va trebui folosita deoarece ea nu poate fi obtinuta adunand alte valori din sir (restul valorilor sunt mai mari sau egale decat aceasta). Fie cea mai mica valoare din sir v₁, acum e clar ca putem obtine toate valorile de forma x*v₁. Daca v₂, a doua cea mai mica valoare din sir nu este de forma x*v₁ va trebui sigur sa o folosim si pe ea. In general, daca suntem la pasul i si v_i nu poate fi obtinuta din subsetul curent de valori selectate vom introduce v_i in subsetul care reprezinta solutia si vom updata toate valorile care se pot obtine considerand si aceasta valoare. Cum am introdus in subsetul solutie doar valorile care erau strict necesare, acesta este si numarul minim de valori. Complexitatea solutiei este O(N*VMAX) ca timp si O(VMAX) ca spatiu, unde VMAX este valoarea maxima din sir, in cazul nostru 50 000.

Teren

Vom alege doua linii i si j din matrice (i ≤ j) si vom determina care este dreptunghiul de arie maxima marginit de aceste doua linii si care contine cel mult X valori de 1. Fie A[k] (1 ≤ K ≤ M) numarul de valori de 1 de pe coloana k care se afla intre liniile i si j. Odata calculat acest vector A problema se reduce la o problema pe vector si anume a determina o secventa de lungime maxima din vectorul A cu suma elementelor ≤ X.
Pentru a rezolva aceasta subproblema ne vom plimba cu doi indici st si dr (st ≤ dr) care vor reprezenta capetele unei secvente cu suma elementelor ≤ X. Pe masura cu avansam cu indicele dr spre dreapta vom mari indicele st in cazul in care suma curenta depaseste X si la fiecare pas vom actualiza secventa de lungime maxima cu valoarea dr-st+1 , respectiv dreptunghiul de arie maxima cu valoarea (j-i+1)*(dr-st+1).
Vom prezenta in continuare pseudocod pentru algoritmul descris, presupunand ca avem deja vectorul A[1..M].

st = 1
suma = 0
pentru dr = 1, M:
    suma += A[dr]
    cat timp (st <= dr) si (suma > X):
        suma -= A[st]
        st = st+1
    daca st <= dr:
        arie_max = max(arie_max, (j-i+1)*(dr-st+1))

Complexitatea acestui algoritm este O(M), deoarece ciclul cat timp nu se va executa mai mult de M ori in total. Mai trebuie doar sa artam cum se poate calcula vectorul A[1..M] in O(M) pentru a obtine o rezolvare de complexitate O(N²*M) (sunt O(N²) perechi de linii pentu care vom efectua acest pas).
Fie S o matrice cu semnificatia ca S[p][q] reprezinta numarul de valori de 1 din coloana q de pe liniile ≤ p. Putem calcula aceasta matrice dupa recurenta S[p][q] = S[p-1][q] + T[p][q] unde T este o matrice reprezentand terenul. Folosind aceasta matrice putem determina vectorul A[1..M] cand avem fixate doua linii i, j dupa recurenta A[k] = S[j][k]-S[i-1][k].

Pairs

Problema admite o rezolvare triviala de complexitate O(N²log MAX), unde MAX este maximul dintre cele N numere ale multimii M: pentru fiecare pereche de numere din multimea data se calculeaza cel mai mare divizor comun folosind algoritmul lui Euclid. O astfel de rezolvare obtine 20-30 de puncte, in functie de prezenta unor optimizari. Rezolvarea optima are complexitatea O(MAX log MAX) si se bazeaza pe faptul ca O(N/1 + N/2 + N/3 ... + N/N) = O(N log N), pentru orice N.
Din numarul total de perechi, N*(N-1)/2, vom scadea numarul de perechi (x y), astfel incat x si y nu sunt prime intre ele si vom obtine rezultatul cerut. Notam cu Res numarul de perechi (x y), cu cmmdc(x, y) > 1. Pentru a afla efectiv numarul Res vom folosi procedeul includerii si excluderii. Fie x_i numarul de numere din M care se divid cu i. Vectorul x se poate calcula in O(MAX log MAX): pentru fiecare numar i de la 1 la MAX verificam cate din numerele i, 2i, 3i ... [MAX/i]*i apartin multimii M. Consideram toate numerele P ce se scriu ca produs de numere prime, unde fiecare numar prim este folosit cel mult o data. Daca numarul de numere prime din descompunerea lui P este un numar impar, adunam x_P * (x_P-1) / 2 la Res. Altfel, din Res scadem x_P * (x_P-1) / 2.
Rezolvarea de complexitate O(MAX log MAX) asigura obtinerea punctajului maxim.

Aliens

Problema se rezolva cu ajutorul programarii dinamice. Fiecare fractie din cele date se poate scrie ca un produs de forma 2^x * 3^y * 5^z, unde x, y si z sunt numere intregi. Daca codificam fiecare fractie prin tripletul corespunzator, problema revine la a selecta anumite triplete (x₁, y₁, z₁), (x₂, y₂, z₂)... (x_K y_K z_K) din cele N astfel incat:

• x₁ + x₂ + ... + x_K ≥ 0
• y₁ + y₂ + ... + y_K ≥ 0
• z₁ + z₂ + ... + z_K ≥ 0
• 2^{(x₁ + x₂ + ... + x_K)} * 3^{(y₁ + y₂ + ... + y_K)} * 5^{(z₁ + z₂ + ... + z_K)} sa fie maxim posibil.

Fie D_{i, x3, x5} valoarea maxim posibila pentru exponentul lui 2 care se poate obtine din primele i fractii, astfel incat exponentul lui 3 sa fie x3 si exponentul lui 5 sa fie x5. Tabloul D poate contine si indici negativi! Relatia de recurenta este urmatoarea:
D_{i, x3, x5} = maxim(D_{i-1, x3, x5}, D_{i-1, x3-x3', x5-x5'} + x2'), unde (x2' ×3' x5') este tripletul asociat celei de a i-a fractii.
Din considerente de memorie nu vom retine tot tabloul D. Deoarece elementele de pe pozitii de forma (i, a, b) depind doar de elemente de pe pozitii de forma (i-1, a', b') vom retine o singura matrice in locul unui tablou tridimensional si vom actualiza elementele din aceasta matrice printr-o parcurgere convenabila a indicilor.
Dupa ce avem tabloul D construit, aflam maxim(2^D_N,x3,x5 * 3^x3 * 5^x5), cu D_{N, x3, x5} ≥ 0, x3 ≥ 0 si x5 ≥ 0. Pentru a compara doua numere 2^x1 * 3^y1 * 5^z1 si 2^x2 * 3^y2 * 5^z2 vom logaritma si vom compara x1*ln2 + y1*ln3 + z1*ln5 cu x2*ln2 + y2*ln3 + z2*ln5. Atunci cand am aflat o solutie optima, este necesara implementarea operatiilor pe numere mari, deoarece rezultatul nu se incadreaza in nici un tip de date conventional.
Complexitatea problemei este O(N³) de constanta 4*(log₃MAX)*(log₅MAX), unde MAX = 400.000.000. Aceasta solutie obtine 100 de puncte.

Tunelul groazei

Vom nota cu X[i] timpul mediu pentru a ajunge din nodul i in nodul N. Evident, X[N] va fi 0. Pentru fiecare nod i, il vom exprima pe X[i] in functie de toate valorile X[j], unde j este vecin cu i. Probabilitatea de a ajunge dintr-un nod i in vecinul sau j este 1/Grad[i]. Deci, exista probabilitatea de 1/Grad[i] ca X[i] sa fie egal cu Distanta[i][j] + X[j]. Dandu-i lui j valorile tuturor vecinilor lui i, gasim o exprimare a lui X[i] sub forma unei ecuatii. Folosind aceste observatii putem sa ne construim un sistem pe care sa il rezolvam cu metoda lui Gauss.

NKPerm

Vom presupune ca avem o functie care determina cate (N,K) permutari exista care incep cu un prefix dat putem efecuta ambele operatii intr-un mod relativ simplu. Pentru a rezolva operatia de tip A putem folosi aceasta functie ca sa numaram cate permutari sunt mai mici din punct de vedere lexicografic decat cea data astfel: luam fiecare prefix al permutarii date si determinam cate permutari exista care incep cu acesta si care au urmatorul element mai mic decat elementul respectiv din permutarea data.
Sa luam permutarea din exemplu (1 3 2 1 2 3). Vom adauga rezultatele pentru prefixele:
(1 1 ...)
(1 2 ...)
(1 3 1 ...)
(1 3 2 1 2 1 ...)

rez = 1
aparitii[1..N] = {0}
pentru i = 1, N*K:
   pentru j = 1, P[i]-1:
       daca j!=P[i-1] si aparitii[j] < K:
           rez += numara(P[1..i-1]+[j])
   aparitii[P[i]]++

rez = 0
aparitii[1..N] = {0}
pentru i = 1, N*K:
   pentru j = 1, N:
       daca j!=P[i-1] si aparitii[j] < K:
           daca rez+numara(P[1..i-1]+[j]) >= X:
               P[i] = j 
               break
           altfel:
               rez += numara(P[1..i-1]+[j]) 
   aparitii[P[i]]++

numara(aparitii[], ultim):
    daca rezultatul pentru (aparitii[], ultim) a mai fost calculat:
        returneaza rezultatul stocat
    daca aparitii[1..N] = {K,K,...,K}:
        returneaza 1
    rez = 0
    pentru i = 1, N:
        daca i != ultim si aparitii[i] < K:
            aparitii[i]++
            rez += numara(aparitii, i)
            aparitii[i]--
    stocheaza rez pentru (aparitii[], ultim)
    returneaza rez

numara(cate[], ultim):
    daca rezultatul pentru (cate[], ultim) a mai fost calculat:
        returneaza rezultatul stocat
    daca cate[K] = N:
        returneaza 1
    rez = 0
    pentru i = 0, K-1:
        daca cate[i] != 0:  
            cate[i]--
            cate[i+1]++
            daca i = ultim:
                // fara valori egale pe pozitii adiacente
                rez += cate[i]*numara(cate, i+1)
            altfel:
                rez += (cate[i]+1)*numara(cate, i+1)
            cate[i+1]--
            cate[i]++
    stocheaza rez pentru (cate[], ultim)
    returneaza rez

Putem estima ca numarul de stari in cazul acesta este N^(K+1)*(K+1), care este destul de mare pentru N = 20, K = 5 (desi mult mai mic decat in cazul precedent). Cum cate[0]+cate[1]+...+cate[K] ≤ N numarul de stari prin care se trece efectiv este mult mult mai mic decat aceasta prima estimare.

Detalii de implemetare

• O codificare rapida a starilor poate fi reprezentarea lor sub forma unui numar de lungime K+2 in baza N+1, codificare care incape intr-un intreg pe 32 de biti.
• In functia de numarare ne putem da seama in momentul in care rezultatul este mai mare de 2⁵⁵ (limita impusa in enunt), si putem returna direct valoarea 2⁵⁵ fara a afecta corectitudinea solutiei. Aceasta optimizare reduce mult numarul starilor care sunt parcurse, deoarece pentru foarte multe stari rezultatul depaseste 2⁵⁵.
• Pentru a verifica daca un rezultat a mai fost calculat deja se poate folosi o tabela hash, dar mai simplu pentru programatorii C++ ar fi fost sa foloseasca un map (desi nu are complexitate O(1) optimizarile anterioare sunt mai mult decat suficiente pentru a face solutiile care folosesc map sa se incadreze in timp)

Solutia oficiala care implementeaza ideile descrise mai sus ruleaza sub 0.1s si parcurge ~100.000 de stari pe testele cele mai mari.