preONI 2005 runda #1 - solutii

(Creat de Mircea Pasoi •domino la data de 2005-01-24 categoria Competitii, autor(i) Mircea Pasoi)

Articolul contine ideile de rezolvare ale problemelor propuse la prima runda a concursului preONI ce s-a desfasurat pe data de 23 ianuarie 2005, cat si comentarii legate de concurs.

Cum s-a si promis, setul de probleme de data aceasta n-a fost dur, problemele fiind mult mai accesibile, fapt care se vede imediat din punctaje. Spre deosebire de concursurile anterioare in care problemele erau toate de acelasi nivel, de data aceasta a existat o problema usoara, una medie si una grea la fiecare grupa (gen TopCoder).

Toti care am participat la compunerea problemelor suntem de parere ca probleme au fost de nivelul ONI, chiar un pic mai usoare. De asemenea, testele au fost create astfel incat sa se poata obtine 190-200p in mod usor de un concurent cu cunostiinte medii care implementeaza solutii corecte dar care nu se incadreaza complet in limita de timp. Din pacate rezultatele sunt un pic sub nivelul asteptarilor, dar speram ca se vor inbunatati in rundele urmatoare! ;)

Clasele 9-10

Primele 5 locuri din clasamentul de la 9-10 arata astfel:

Pozitie	Nume	Scor
1	Macarie & Petronela •macarie	270
2	Bogdan-Cristian Tataroiu •bogdan2412	210
3	Stefan Andrei •theandy	190
4	Daniel Ghilea •dani	180
5	Vlad Saveluc •TYTUS	170
5	Stanescu Lucian •triplex	170

Este de mentionat faptul ca sub pseudonimul Macarie & Petronela •macarie se "ascunde" echipa care va reprezenta Romania la finala ACM, formata din Mugurel Andreica, Marius Andrei si Ghinea Dan. Ei au concurat pe un singur calculator si au rezolvat toate cele 6 probleme propuse pentu a simula un concurs ACM. De asemenea, un lucru remarcabil, concurentul clasat pe locul 2, Tataroiu Bogdan este abia clasa a 7-a! Probabil ca va reprezenta Romania la multe IOI-uri :)

Text

Problema a fost cea mai usoara din cele 3 probleme din grupa si rezolvarea nu ar trebui sa ridice mari dificultati nici macar unui elev de a 9-a incepator. Fie N numarul de caractere din fisierul de intrare - voi prezenta o solutie O(N). Se parcurge fisierul caracter cu caracter (nu este necesara stocarea datelor de intrare intr-un vector) si se mentin doua variabile care indica pozitia de inceput si sfarsit a ultimului cuvant detectat pana in prezent, daca s-a gasit vreunul. De asemenea se pastreaza si doua variabile pentru suma lungimilor cuvintelor si numarul de cuvinte pentru a calcula rezultatul. Atentie insa ca la sfarsitul parcurgerii fisierului de iesire, daca ultimul caracter citit a fost o litera mare sau mica, sa se actualizeze numarul de cuvinte si suma lungimilor.

Trapez

Problema a fost cea de nivel mediu din cele 3 si face apel la cunostiinte minime de geometrie. Conditia ca oricare trei puncte nu sunt coliniare simplifica mult rezolvarea. Din definitie, un trapez are cel putin doua laturi paralele deci se poate construi urmatorul algoritm: se iau toate perechile de puncte - acestea determina cate un segment - si sorteaza in functie de unghiul cu axa OX (panta dreptei). Pentru fiecare k segmente cu acelasi unghi se pot forma Comb(k,2) trapeze. Pentru a evita calculele cu reale (care pot cauza erori de precizie), se tin pantele ca perechi de numere intregi (y, x), fara a efectua efectiv impartirea y/x. Pentru compararea a doua astfel de perechi sunt necesare tipuri de date pe 64 de biti. Algoritmul descris are complexitate O(N²*lg N). Las ca exercitiu rezolvarea acestei probleme folosind un algoritm O(N²) care foloseste hashing (vezi articolul de pe site). Se puteau obtine 40-50p cu un algoritm brut O(N⁴).

Subsir

Aceasta problema, care a fost si cea mai grea, a fost prezenta si la CEOI 2003, dar intr-o forma mai simpla. Acolo se cerea generarea efectiva a tuturor subsirurilor , nu numararea lor, si se garanta ca numarul lor este sub 1000. Orice solutie care ar fi luat 100p la problema de la CEOI ar fi obtinut 50p la aceasta (primele 5 teste fiind de fapt preluate de la CEOI 2003). Cum multi probabil au intuit, rezolvarea se bazeaza pe programare dinamica. Voi numi cele doua siruri A si B, de lungime N, respectiv M si voi construi initial matricea C_i,j = lungimea celui mai lung subsir comun al sirurilor A_1..i si B_1..j. Acest lucru se poate face in O(N*M) si este o aplicatie clasica a programarii dinamice (se gaseste in foarte multe carti explicata ideea). In continuare voi numara sirurile folosind un algoritm O(N*M*Sigma) unde Sigma este numarul litere din care pot fi formate sirurile, adica 26. Se va calcula o matrice Nr_i,j = cate subsiruri comune de lungime maxima existe pentru sirurile A_1..i si
B_1..i (evident modulo 666013). Se calculeaza Nr_i,j doar atunci cand A_i = B_i, astfel: pentru fiecare caracter c intre 'a' si 'z' se cauta ultima sa aparitie in sirul A_1..i-1 (fie aceasta pozitia ii) si ultima sa aparitie in sirul B_1..j-1 (fie aceasta pozitia jj). Acest lucru se poate face in O(1) daca se preproceseaza inainte aceste informatii in O((N+M)*Sigma). Daca C_i,j = C_ii,jj+1 se va aduna Nr_ii,jj la Nr_i,j - aceasta conditie ne garanteaza ca subsirurile adaugate au lungime maxima, iar faptul ca ii si jj reprezinta ultima aparitie a caracterului garanteaza ca nu se vor numara subsiruri identice. Pentru a gasi rezultatul final se aduna toate valorile Nr_i,j calculate, cu urmatoarea exceptie: daca exista pozitiile x si y astfel incat A_x = A_i = B_y = B_j, se aduna Nr_i,j doar daca x < i si y < j (pentru a asigura ca nu se numara subsiruri identice de mai multe ori).

Clasele 11-12

Primele 5 locuri din clasamentul de la 11-12 arata astfel:

Pozitie	Nume	Scor
1	Filip Simion •Dust	200
2	Dan-Leonard Crestez •fluffy	190
2	Macarie & Petronela •macarie	190
4	Bindea Calin •ParrAzitU	170
5	Grosu Codrut •Ragnar_Lodbrok	140
6	Constantin-Cristian Balas •cristi8	130

Iepuri

Problema a fost cea mai usoara din cel 3 si necesita cunostiine elementare de matematica de clasa a 11-a. Daca se noteaza cu I_n cati iepuri sunt in ziua n se deduc urmatoarele relatii din enunt:

• I₀=X, I₁=Y, I₂=Z
• I_n=A*I_n-1 + B*I_n-2 + C*I_n-3 pt 3 ≤ n

Rezultatul cerut este I_N modulo 666013 pentru fiecare test.
O prima rezolvare, si cea mai simpla, este implementarea directa a relatiei de recurenta si conduce la o complexitate O(N) pe set de date. Aceasta abordare ar fi obtinut 50p.In continuare voi descrie o rezolvare $O(lg N)4 care foloseste matrici. Se construieste matricea:

[0 1 0]
M = [0 0 1]
[C B A]

care sta la baza relatiei:

[I₀]  [I_N  ]
M * [I₁] = [I_N+1]
[I₂]  [I_N+2]

Din asta se deduce:

[I₀]  [I_N  ]
M^N * [I₁] = [I_N+1]
[I₂]  [I_N+2]

astfel problema se reduce la a calcula M^N in O(lg N). Algoritmul de ridicare la putere in timp logaritmic este clasic si nu-l mai mentionez aici.

Barbar

Problema este de nivel mediu si necesita cunostiinte elementare de teoria grafurilor. Se considera matricea initiala un graf cu R*C noduri, mai putin zidurile. Se face o parcurgere BF pentru a determina pentru fiecare casuta din matrice distanta pana la cel mai apropiat dragon. Astfel, se incepe BF-ul cu toate nodurile care corespund dragonilor inserate in coada (deci nu va fi doar un nod in coada la inceput). Complexitatea acestui pas este O(R*C). Se observa daca exista un traseu valid care trece prin casute situate la distanta >=x fata de cel mai apropiat dragon, atunci exista in mod evident un traseu valid care trece prin casute situate la distanta >=x-1 fata de cel mai apropiat dragon. Aceasta observatie duce la folosirea cautarii binare a rezultatului (vezi articolul de pe site pentru alte aplicatii). Pentru a verifica daca exista un traseu valid care trece doar prin casute situate la o anumita distanta fata de cel mai apropiat dragon se foloseste tot o parcurgere BF, astfel rezolvarea fiind
O(R*C*lg(R*C)).

ADN

La primul pas se elimina toate cuvintele incluse in alte cuvinte mai mari (pentru a cauta daca exista un cuvant in alt cuvant se foloseste algoritmul KMP pentru incadrarea in timp - vezi articolul de pe site). Apoi, se construieste un graf cu noduri cuvintele si muchii intre oricare doua cuvinte. Costul unei muchii (i, j) va fi cel mai lung sufix al cuvantului i care este prefix al cuvantului j (informatie care se poate determina cu KMP), adica cate litere sunt "inutile" daca lipim cuvantul i cu cuvantul j. Aceasta prima etapa are complexitate O(N^2*L), unde L e lungimea maxima a unui cuvant. Deoarece trebuie sa existe fiecar cuvant in sirul rezultat, iar sirul sa fie de lungime minima problema se reduce la determinarea unui lant hamiltonian de cost maxim, problema care este binecunoscuta ca fiind NP. Un algoritm care incearca toate cele n! permutari are complexitate O(n!) si va obtine 50p. Pentru punctaj maxim vom folosi programare dinamica astfel: fie A[i][(n1, n2.. nk)] = costul unui lant hamiltonian
de cost maxim care incepe din nodul i si trece prin nodurile n1, n2 .. nk. Relatia de recurenta este: A[i][(n1,n2..nk)] = max cost(i, nj) + A[nj][(n1,n2,nj-1,nj+1..nk)] pentru fiecare j. Dinamica se initializeaza cu A[i][(i)] = 0 pentru fiecare i. Reprezentarea multimilor de noduri se face folosind un numar binar cu N biti, astfel complexitatea acestei etape fiind O(N^2*2N). Mentionez ca aceasta rezolvare nu produce solutia minim lexicografic, fapt observat in timpul concursului si astfel s-a reevaluat problema dandu-se puncte pentru orice solutie valida, nu neaparat minim lexicografic. Rezolvarea problemei cu cerinta de minim lexicografic este posibila, dar pentru realizarea ei trebuie folosite structuri de date avansate ca Suffix Arrays sau Suffix Trees si nivelul de dificultate ar fi mult mai mare. Alta observarie este ca matricea cost ar putea fi calculata mai repede daca am folosi structurile mentionate mai devreme. Folosind prima structura am avea complexitatea O( N*L log (N*L)) iar a folosind a
doua structura am avea complexitatea O(N*L) . De asemenea mentionam posibilitatea folositii algoritmului randomizat de potrivire a sirurilor de caractere numit Rabin Karp pentru calcularea matricii cost ceea ce ar fi dus la o solutie mai scurta si la un cod mai clar. Ne cerem scuze pentru eventualele neplaceri cauzate de aceasta situatie.

Bafta la urmatorul concurs! (undeva prin februarie...)