blog/onis-2016-1-editorial

Mihai Calancea
08 martie 2016

Prima rundă de calificare a concursului ONIS 2016 s-a încheiat. În cele ce urmează vom prezenta o scurtă analiză a concursului, însoţită de soluţiile oficiale ale problemelor propuse.

În primul rând, felicitări câştigătorilor! Mai exact, primelor cinci echipe de studenţi în ordinea clasamentului:

1. UPB Banu Popa Visan •team_name

2. Mafia Unibuc •mafia_unibuc

UNIBUC Kira96 lockmihai •corul_barbatesc

UBB Cociorva Popoveniuc Salajan •lookingForAChallenge

UNIBUC Impaler-009 Challenge costyv87 •The_Viper_The_Mountain_And_The_Imp

De-asemenea, primelor 5 echipe de liceu:

Oncescu Costin •geniucos

Tamio Vesa Nakajima •tamionv

Popa Andrei •andreiiii

UVS Babalau Rochian Tarniceru •enterprise

UNIBUCThrowTerror •Spiromanii_Messi

A. MaxSubSum

Algoritmul general de determinare a submatricei de sumă maximă este prea încet pentru această problemă, având complexitate O(N ^ 3). Este în schimb natural să ne gândim că putem obţine o soluţie mai rapidă dacă analizăm modul de construcţie al matricei. Astfel, analizând matricea cu colţurile (x1, y1, x2, y2), observăm că suma sa este (x2 - x1 + 1) * B[y1...y2] + (y2 - y1 + 1) * A[x1...x2], unde prin T[a...b] am notat suma T[a] + T[a + 1] + …. T[b]. Această formulă ne arată, printre altele, că nu este întotdeauna optim să alegem independent liniile şi coloanele matricei bazându-ne pe subsecvenţele de sumă maximă din cele două şiruri (soluţie încercată iniţial de unii concurenţi). Uneori o subsecvenţă de sumă nemaximă, dar de lungime mare, poate fi de ajutor.

În schimb, este adevărat că dacă submatricea optimă va avea X linii şi Y coloane, ne intereseaza doar subsecvenţele de lungime X, respectiv Y care au suma maximă posibilă în A şi B. Putem precalcula uşor şirul bestA[Length] = “suma maximă a unei subsecvenţe din A de lungime Length ” în timp O(N²), analog pentru şirul bestB[]. Apoi vom itera peste toate cele N ^ 2 dimensiuni posibile ale submatricei şi vom reţine maximul expresiei LineCount * bestB[ColumnCount] + ColumnCount * bestA[LineCount].

B. Avioane2

Construim 3 tipuri de evenimente:

• Decolare: Decoleaza avionul cu indicele X din aeroportul A la timpul Td
• Aterizare: Aterizeaza avionul cu indicele X din aeroportul B la timpul Ta
• Query: Raspundem la un query pentru aeroportul C, timpul Tq

Sortam evenimentele in functie de timp si simulam un algoritm de drum minim, pas cu pas in functie de ce evenimente apar. La orice moment de timp, tinem pentru fiecare nod X costul minim de a junge din nodul 1 in nodul X.

• Eveniment query (aeroportul C): raspunsul este costul minim curent de a ajunge din 1 in C, pur si simplu trebuie afisat.
• Eveniment de Decolare (aeroportul A): costul minim de a ajunge intr-o anumita destinatie poate sa fie modificat cu costul minim de a ajunge in momentul de fata in nodul din care decolam (nodul A) + pretul biletului pentru acest avion. In cazul in care aceasta varianta se va dovedi a fi mai buna, vom actualiza costul minim pentru destinatie in momentul aterizarii
• Eveniment de Aterizare (aeroportul B): selectam pentru nodul in care aterizam (nodul B) cea mai buna varianta (ori pastram costul minim de pana acum, ori costul obtinut prin intermediul avionului care tocmai a aterizat, cost calculat la evenimentul de tip Decolare)
  Problema poate fi vizualizata ca si un caz particular al algoritmului de Bellman-Ford. Din moment ce avem si axa timpului, este suficient sa trecem o singura data prin muchii deoarece o muchie cu un cost mic la un anumit moment de timp nu poate afecta alte configuratii la timpi mai mici

C. MinLcm

Folosim proprietatea: cmmmc(a, b) = a * b / cmmdc(a, b)
Din moment ce a, b <= 100.000, avem garantia si ca cmmdc(a, b) <= 100.000
Se observa faptul ca pentru un cmmdc fixat D, ne intereseaza cele mai mici 2 elemente din sir care au acest D drept divizor (pentru a minimiza a * b / D). Aceste 2 numere se pot calcula simplu pentru fiecare divizor D cu ajutorul ciurului lui Eratostene.

Obsevatie: Algoritmul fixeaza in realitate doar un divizor al celor 2 numere (fără a avea vreo garanţie că este cmmdc-ul real), dar dacă divizorul respectiv nu este într-adevăr cel mai mare posibil al celor două numere, va produce un rezultat mai mare decât cel real, deci răspunsul problemei nu va fi afectat.

D. Unlock

O primă soluţie posibilă este cea de a itera pe rând prin toate cele K culori şi a efectua câte o parcurgere a matricei pentru a verifica dacă celulele libere sunt conexe. Această soluţie are complexitate worst-case O(N * M * K), iar date fiind limitările lui K, este echivalentă cu O((N * M) ^ 2). Deşi la prima vedere ar părea că este puţin probabil ca atât K cât şi zonele atinse de fiecare parcurgere să fie de mărime Theta(N * M) simultan, există teste în care acest lucru se întâmplă, iar soluţia descrisă depăşeşte cu mult limita de timp, care, mai mult, este calibrată pentru a procesa 25 de teste, nu unul singur.

Pentru a obţine o soluţie mai rapidă, vom încerca ca pentru fiecare culoare fixată să depunem efort (i.e număr de operaţii) proporţional cu numărul total de celule de această culoare. Deoarece în total acest număr este limitat de N * M, complexitatea ar fi şi ea proporţională cu această valoare. Pentru a construi o asemenea soluţie, vom face pentru început nişte parcurgeri care vor identifica zonele conexe de celulele libere. Apoi, pentru fiecare culoare fixată, fie ea C, vom face o parcurgere pentru fiecare componentă conexă de culoare C şi vom reţine cu ce zone conexe libere este vecină fiecare astfel de componentă. Dacă o anumită componentă Comp de culoare C este vecină cu zonele libere “x1, x2 .. xT”, atunci aceste zone vor deveni conectate în momentul în care o facem pe Comp accesibilă. Astfel, pentru fiecare componentă îi putem uni vecinii cu o structură de date eficientă (de tip păduri de mulţimi disjuncte), iar la final trebuie ca toate zonele libere iniţiale să fie conexe. Pentru a justifica faptul că numărul de operaţii este proporţional cu mărimea componentelor de culoare C, observăm faptul că fiecare zonă liberă vecină cu o anumită componentă trebuie să fie adiacentă cu componenta respectivă pe cel puţin o latură a unei celule din componentă. Deoarece numărul de laturi al unei componente conexe este limitat de 4 * (mărimea componentei), rezultă că numărul maxim de vecini distincţi posibili este limitat de aceeaşi valoare.

Este nevoie de o implementare atentă pentru a menţine complexitatea dorită. Spre exemplu, reiniţializarea completă a pădurilor de mulţimi disjuncte pentru fiecare culoare poate duce din nou la timp O((N * M) ^ 2), chiar dacă restul algoritmului este eficient.

E. MinMaxStore

Se observa faptul ca proprietatea este independenta pentru minim si maxim.

Initial consideram ca toate cele N valori sunt posibile minime. In momentul in care avem o operatie Store(A, B), aplicam urmatorii pasi:

• Daca A este posibil minim, ramane posibil minim
• Daca A nu este posibil minim, acesta devine posibil minim doar daca B este posibil minim.
• B nu mai poate sa fie minim orice ar fi

La sfarsit proprietatea este adevarata daca avem un singur posibil minim si acesta se afla pe pozitia indicata. Analog facem si pentru maxim si raspundem la fiecare din cele 4 cazuri in functie de corectitudinea celor 2 raspunsuri.

F. Pokemon3

În ciuda enunţului mai complex, aceasta este una dintre cele mai simple probleme la nivel algoritmic. Deoarece numărul de tipuri de pokemon este mic, putem itera prin toate submulţimile posibile de pokemoni şi verifica pentru fiecare submulţime dacă aceasta asigură victoria. Pentru a se încadra în timp, soluţia trebuie să codeze submulţimile ca măşti de biţi şi să facă verificarile folosind operaţii pe biţi pe aceste valori. Complexitatea finală este O(2 ^ N * N).

G. Puzzle2

Problema admite multe soluţii, care variază mai ales ca dificultate a implementării. O soluţie rezonabilă vine din observaţia că o dată ce am aflat prima linie a matricei, restul matricei se poate reconstitui cu uşurinţă, linie cu linie. Pentru a construi prima linie, putem începe dintr-un colţ (un nod cu 2 vecini) şi parcurge numai noduri de margine (care au 3 vecini) până găsim un alt colţ. Dacă alegem să facem acest lucru, trebuie să tratăm special cazul matricelor cu 2 linii (sau coloane), deoarece în acest caz parcurgerea nodurilor de margine poate alterna haotic între cele două linii, fără ca lanţul obţinut în final să fie o linie reală a matricei. Cazul se tratează uşor, observând că acum un colţ este vecin direct cu cel puţin un alt colţ. Cele două colţuri vor forma singure prima linie, iar acum putem reconstitui restul matricei ca în cazul general.

H. Subpermutari

Consideram toate cele N² subsecventele are permutarii noastre. Observam faptul ca daca pentru o secventa [a,b] determinam cea mai lunga subpermutare care este atat prefix, cat si sufix a secventei noastre, putem foarte usor marca sufixul ca fiind o secventa care a mai aparut deja si crestem frecventa prefixului.
Pentru a determina cea mai lunga subpermutare care este atat prefix, cat si sufix, vom aplica un algoritm foarte asemanator KMP-ului:
Fixam pozitia de start a subsecventei noastre si pornim algoritmul de KMP de acolo.
Presupunem ca avem calculat pentru o subsecventa [a,b] acest cel mai bun prefix-sufix (il notam identic ca la KMP cu pi[b]). Cand vrem sa trecem la urmatorul element, b + 1, avem aceleasi 2 cazuri de luat in considerare ca si la KMP:

Cazul in care elementul inserat b + 1 are aceelasi indice in subpermutarea sufixului ca si urmatorul element in subpermutarea prefixul: pur si simplu pi-ul creste cu 1
Daca indicele difera, micsoram pi-ul (mergem in pi[pi[b]]) si repetam procedeul pana avem o potrivire

Pentru a determina al catelea element se afla o valoare intr-o secventa putem usor precalcula cu un simplu aib.
Complexitate: O(N^2 log N)

I. Nucleul Valoros Season 2

Pornim de la solutia brute, programare dinamica in O(N^3).
D[i][j] = costul minim al secventei [i,j]. Recurenta este data in enunt: fixam un k de la i la j - 1 si luam cea mai buna varianta
Notam pentru un interval [i,j], valoarea k pentru acest interval drept optim[i][j].

Prima proprietate foarte importanta este faptul ca: optim[i][j - 1] <= optim[i][j] <= optim[i + 1][j]
Intuitiv este foarte usor de vizualizat acest lucru:
Daca am secventa [i, j - 1] si adaug un element nou in dreapta, k se poate muta doar la dreapta
Daca am secventa [i + 1, j] si adaug un element nou in stanga, k se poate muta doar la stanga
O sa demonstram ca daca facem for dupa k de la optim[i][j - 1] pana la optim[i + 1][j], in loc sa il facem de la i la j, obtinem complexitate O(n^2).

Demonstratie: Consideram toate intervalele de lungime x. Avem proprietatea optim[a][b - 1] <= optim[a][b] <= optim[a + 1][b] si optim[a + 1][b] <= optim[a + 1][b + 1] <= optim[a + 2][b + 1], unde b - a + 1 = x. Observam ca sfasitul unui interval de lungime x este inceputul urmatorului interval de lungime x. Amortizat, obtinem O(N) pentru fiecare lungime x de interval, O(N ^ 2) in total.