Solutii Autumn WarmUp 2006

(Categoria Competitii, autor(i) Echipa Infoarena)

Aici puteti gasi solutiile oficiale la cele 5 probleme propuse in concurs. De precizat si ca aceasta initiativa infoarena a fost un succes, adunand un numar respectabil de participanti. Punctajele au fost mai mici decat cele asteptate, fapt ce a confirmat ca setul de probleme a fost unul capabil sa puna in dificultate nume cunoscute la olimpiadele de informatica. Iata si solutiile:

poly

Problema este una de programare dinamica si are complexitatea O(N), de constanta 2⁷ = 128. Sa notam cu M_i,j lungimea celui mai lung subsir utilizand primele i numere din vector astfel incat ultimul element din subsirul optim sa aiba ca divizori numerele din multimea data corespunzatoare bitilor de 1 din j. Mai intai M_i,j = M_i-1,j ( nu folosim numarul al i-lea ). Daca dorim sa folosim si numarul al i-lea, atunci M_i,config = maxim(M_i,config, M_i-1,k + 1), cu k and config = 0, unde config are bitii de 1 corespunzatori numerelor din multimea data cu care se divide acest al i-lea numar din sirul initial. Conditia k and config ne asigura ca penultimul si ultimul numar din subsir nu au amandoua vreun divizor comun din multimea data (operatia and in acest context este o operatie pe biti). Rezultatul va fi max(M_n,0, M_n,1... M_n,127). Memoria folosita poate fi O(1), retinand doar ultimele doua linii ale matricei.

Un algoritm de complexitate patratica in N folosind tot programarea dinamica ar fi obtinut 30-40 de puncte.

bridge

Un algoritm de complexitate O(M + N * K) folosind programarea dinamica nu este foarte greu de gasit. Daca notam cu M_i,j numarul de moduri (modulo 666013) de a ajunge in i pasi pe scandura j din pozitia initiala, atunci mai trebuie avut grija doar la relatiile de recurenta. In cazul de fata vom utiliza metoda inainte si vom trata cazurile: daca scandura j este lipsa atunci M_i,j = 0, daca scandura j este teleportoare incrementam M_i+1,undej cu M_i,j daca si numai daca unde_j nu este lipsa sau subreda (unde_j este destinatia teleportarii de pe scandura j),daca j este scandura buna, incrementam M_i+1,j+1 cu M_i,j si M_i+1,j+2 cu M_i,j doar daca j+2 nu e lipsa sau subreda, etc.

Avand construita matricea M, pentru fiecare query putem raspunde acum in O(1). Exista diferite optimizari care pot fi facute si care sporesc substantial timpul de executie.

secv4

Deoarece logaritmul unui produs de numere este egal cu suma logaritmilor fiecarui numar din produs, si in ipoteza ca toate numerele din sir sunt pozitive, logaritmam fiecare numar si notam cu S_i suma primilor i logaritmi. Astfel, pentru a afla secventa de produs maxim care se termina pe pozitia i, este suficient sa determinam, pentru k intre i-y si i-x care este S_k minim (astfel, S_i - S_k va fi maxim, deci si produsul maxim, iar secventa va incepe pe pozitia k+1). Putem folosi un arbore de intervale si obtinem un algoritm O(NlogN), sau o coada prin care scoatem elementele prin ambele parti (structura de date numita deque - double ended queue), obtinand complexitatea O(N). Daca exista si numere negative, in momentul logaritmarii numerelor negative logaritmam opusul lor. Aplicand procedeul descris mai sus, stim sigur la final ca produsul obtinut are modulul maxim. Pentru a fi cu adevarat maxim (deci pozitiv), notam cu semn_i semnul produsului primelor i numere. Ca secventa <j+1, i> sa aiba produs maxim trebuie in plus semn_i = semn_j. Vom retine doua deque-uri, unul pentru + si unul pt -, conform vectorului semn. Astfel, in final, suntem siguri ca produsul are semnul + si, cum are si modulul maxim, are valoarea maxima ceruta.

parcare

Problema este exponentiala in dimensiunea matricii, dar polinomiala in numarul total de posibilitati de pozitionare al masinilor. Astfel, vom folosi un algoritm de tip BFS care garanteaza ca se ajunge la solutie intr-un numar minim de miscari. Plecam de la matricea initiala, si expandam pe rand toate starile posibile, miscand din starea curenta cate o masina pana cand nu mai exista nici o varianta noua de pozitionare a masinilor sau pana cand am scos masina A din parcare. Starile problemei le putem codifica intr-un intreg de 64 de biti. Singurele variabile sunt pozitiile masinilor. Dupa ce eliminam zidurile inconjuratoare, coordonatele nu sunt mai mari decat 7 ( 3 biti ), deci pentru pozitia unei masini vom folosi 6 biti. Concatenam pozitiile masinilor si, cum sunt maxim 10 masini, codificarea nu va avea mai mult de 60 de biti.
Pentru a memora starile explorate vom folosi o tabela de hash. De precizat si ca numarul total de posibilitati pornind de la starea initiala este destul de redus, deci problema va rula aproape instantaneu.

easy query

Un algoritm simplu de complexitate O(N*M) obtine 30-50 de puncte. Algoritmul de 100 de puncte are complexitatea O(MlogN) si foloseste arbori de intervale. Considerand o secventa x_i x_i+1... x_j este evident ca pentru ca elementele sirurilor y si z sa fie maxime, respectiv minime, ele trebuiesc construite astfel:

• y_t = x_t- min(x_k) + max(x_p), i ≤ t ≤ j, t ≤ k, p ≤ j
• z_t = x_t - max(x_k) + min(x_p), i ≤ t ≤ j, t ≤ k, p ≤ j

Pentru a calcula in timp optim valoarea P = max(y) + min(z) ne vom folosi de un arbore de intervale in urmatorul mod: fiecare nod al acestuia va constitui o secventa x_st, x_st+1... x_dr ( unde st si dr sunt marginile intervalului din nodul arborelui ) pe care o vom rezolva prin metoda brute force de la inceput, avand grija sa precalculam si alte valori necesare mai tarziu, cum ar fi :

• min = minim(x_st, x_st+1... x_dr)
• max = maxim(x_st, x_st+1... x_dr)
• x_max_max = maxim(x_t + maxim(x_p) ),st ≤ t ≤ dr si t ≤ p ≤ dr
• x_max_min = minim(x_t - maxim(x_p) ),st ≤ t ≤ dr si t ≤ p ≤ dr
• x_min_max = maxim(x_t - minim(x_p) ),st ≤ t ≤ dr si t ≤ p ≤ dr
• x_min_min = minim(x_t + minim(x_p) ),st ≤ t ≤ dr si t ≤ p ≤ dr
• y_max = maximul din sirul y corespunzator secventei x_st, x_st+1... x_dr
• z_min = minimul din sirul z corespunzator secventei x_st, x_st+1... x_dr

Avand precalculate valorile de mai sus pentru fiecare nod al arborelui in parte vom putea raspunde in timp O(logN) pentru fiecare din cele M intrebari. Fiecare subsecventa data x_i, x_i+1... x_j va putea fi compusa din reuniunea mai multor noduri din arborele de intervale. Acum parcurgem nodurile ce compun subsecventa data de la dreapta la stanga si vom gasi rapid valorile maxim(y) si minim(z). Presupunand ca am ajuns la nodul Q valoarea maxim(y) pana aici se calculeaza astfel:

• MAX(Y) = maxim (y_max(Q) ; y_max_max(Q) - min(W) ; x_min_max(Q)+max(W) ; max(Q)+max(W)-min(W))

Analog se calculeaza si minim(z).