Solutii Algoritmiada 2012, Runda 1

Intfm

Soluţia oficială la această problemă are complexitate O(N^2) şi se rezolvă folosind programare dinamica. Pentru a rezolva problema, este necesară următoarea observaţie: fie două intervale [A B] si [C D], cu B < D. Dacă amândouă se găsesc în soluţie, atunci singurele aşezări posibile ar putea fi [A B] [C D] sau [C [A B] D]. [A {C B] D} este o variantă invalidă.

Iniţial, vom mentine pentru fiecare interval i câte o stare C[i], reprezentând numărul maxim de spectacole ce pot fi vizionate in pauza spectacolului i, respectiv o a doua stare, D[i], reprezentand numărul maxim de spectacole din primele i ce pot fi vizionate, ultimul dintre acestea fiind i (luăm în considerare spectacolul i in soluţie). Observăm că dacă adăugăm un al n + 1 -lea spectacol fictiv, suficient de lung încât să conţină toate intervalele din input în pauza sa, răspunsul problemei se va afla în C[n + 1].

Astfel, pentru un interval i, fixăm toate intervalele conţinute de acesta, fie ele j1,j2..jk. Vom iniţializa D[j1], D[j2]...D[jk] cu 0. Pentru a calcula stările din Dj folosim următoarea recurenţă: D[j] = max(C[j] + D[prev[j]], D[j - 1]), unde prev[j] reprezintă cel mai din dreapta interval care se termină înainte să înceapă intervalul j, şi prev[j] face parte din multimea { j1, j2..jk }. C[i] va fi deci max(D[jt]) unde 1 ≤ t ≤ k. Observăm că pentru a calcula C[i], avem nevoie ca valorile C[] să fie deja calculate pentru spectacolele din pauza spectacolului i. Putem face acest lucru calculând dinamica în ordinea crescătoare a lungimilor intervalelor sau implementând-o ca o funcţie recursivă.

Sccm

Notatie:
ap1[i]=pozitia pe care apare i in primul sir
ap2[i]=pozitia pe care apare i in al 2-lea sir

Solutie O(N^2): Se construieste dinamica D[i]=subsirul de lungime maxima care se termina in i. Recurenta este asemanatoare cu cea de la scmax ; se incearca gasirea penultimului element al subsirului optim ce se termin in i: D[i]=max(D[j])+1 , unde j<i si j apare inaintea lui i in primul sir, iar j apare inaintea lui i si in al 2-lea sir(ap1[j]<ap1[i] si ap2[j]<ap2[i])
Raspunsul va fi reprezentat in mod evident de max(D[i])
Solutie O(N*log^2N): Se optimizeaza recurenta din solutia de mai sus utilizand un arbint 2D 

Mincinosi

Prima observaţie necesară rezolvării problemei este că pentru a nu se contrazice, răspunsurile oferite de toţi prietenii selectaţi în soluţie trebuie să fie egale. Să numim această valoare A. Pentru ca această valoare să fie şi corectă (să ofere legitimitate prietenilor selectaţi), este necesar ca A == N - frecvenţă[A], unde frecvenţă[] contorizează apariţiile fiecărui tip de răspuns în parte. Cu alte cuvinte, deoarece presupunem că restul persoanelor sunt micinioase, acestea ar trebui toate să dea un răspuns diferit de A. Astfel, vom construi vectorul frecvenţă[] odată cu citirea datelor, după care vom itera prin fiecare A posibil şi vom evalua condiţia enunţată mai sus, reţinând soluţia care implică cel mai mare număr de prieteni.

Dreptunghiuri4

De la citire vom aduce punctele in forma standard, adica in forma colt (stanga, jos), colt (dreapta, sus). De asemenea, vom face trecerea de la plan la matrice, adica in loc sa lucram cu coordonate in plan vom lucra cu linii si coloane care definesc o matrice. Trecerea plan-matrice se face inversand abscisa cu ordonata. De exemplu, punctului din plan (3, 1) ii va corespunde intr-o matrice linia 1 si coloana 3. In continuare, vom lucra cu punctele in aceasta forma standard.

O prima solutie ar fi sa folosim o matrice caracteristica count[i][j] = cate dreptunghiuri trec prin punctul cu linia i si coloana j. Vom parcurge fiecare din cele N dreptunghiuri si pentru fiecare vom considera (x0, y0) coltul stanga-jos si (x1, y1) coltul dreapta-sus. Tot ce avem de facut este sa consideram fiecare punct (i, j) cu x0 <= i < x1 si y0 <= j < y1 si sa incrementam count[i][j]. Motivul pentru care am luat inegalitate stricta in partea drepta este pentru ca punctul (i, j) din matrice reprezinta echivalentul in plan al patratului de latura 1 (j, i) - (j, i + 1) - (j + 1, i) - (j + 1, i + 1). Astfel, punctul cu coordonatele cele mai mari cate trebuie incrementat este (x1 - 1, y1 - 1), corespondent al dreptunghiului (y1 - 1, x1 - 1) - (y1, x1 - 1) - (y1 - 1, x1) - (y1, x1) din plan. Dupa executarea celor N incrementari, parcurgem matricea count si incrementam un contor de fiecare data cand count[i][j] = K, apoi afisam contorul.

Dezavantajele solutiei de mai sus sunt evidente: este necesara in primul rand o matrice de 1,000,000,000 × 1,000,000,000 care nu incape in memorie. Apoi, coordonatele pot fi si negative, accesarea unui element negativ ducand la Killed By Signal 11. Solutia problemei reprezinta o rafinare a solutiei de mai sus. Se normalizeaza punctele pe cele 2 axe. Fie un punct (i, j) si fie x = cate puncte au abscisa <= i din cele 2 * N puncte date pe linii, iar y = cate puncte au ordonata <= j din cele 2 * N puncte date pe coloane. Punctul (i, j) se transforma in (x, y). Prin "puncte date pe linii" se intelege valori distincte care apar in input ca fiind linii ale unui colt stanga jos sau dreapta sus. La fel, prin "puncte date pe coloane" se intelege valori distincte care apar in input ca fiind coloane ale unui colt stanga-jos sau dreapta-sus. Sa luam urmatorul exemplu : avem dreptunghiurile ((0, 0) ; (100, 100)), ((1, 1) ; (10, 10)), ((60, 20) ; (100, 40)), ((100, 100) ; (200, 200)). Ce puncte apar pe linii? 0, 100, 1, 10, 60, 100, 200. Ne intereseaza doar valorile distincte sortate crescator : 0, 1, 10, 60, 100, 200. Analog, pe coloane avem valorile 0, 1, 10, 20, 40, 100, 200. Conform principiului de mai sus, pentru a normaliza un punct (i, j) va trebui sa cautam indicele lui i in sirul liniilor si indicele lui j in sirul sortat al coloanelor, presupunand ca numerotarea sirului incepe de la 1 (indicele primului element este 1). Prin normalizare, punctele devin (1, 1) ; (5, 6)), ((2, 2) ; (3, 3)), ((4, 4) ; (5, 5)), ((5, 6) ; (6, 7)). Memoria maxima ocupata acum de matricea caracteristica va fi 2*N x 2*N, adica 2,000 × 2,000.

Pentru o solutie mai buna, se aplica algoritmul brute - force descris mai sus pentru punctele normalizate, cu o exceptie : acum count[i][j] nu mai reprezinta patratul de latura 1 (j, i) - (j + 1, i) - (j, i + 1) - (j + 1, i + 1), acum el reprezinta dreptunghiul (y[i], x[j]) - (y[i], x[j + 1]) - (y[i + 1], x[j]) - (y[i + 1], x[i + 1]), unde x reprezinta sirul valorilor de pe linii si y sirul valorilor de pe coloane. Pentru exemplul de mai sus count [5] [6] ar fi dreptunghiul (100, 100) - (200, 200). De aceea, cand calculam solutia, in loc sa incrementam contorul ca in solutia brute-force vom calcula aria dreptunghiului (y[i], x[j]) - (y[i], x[j + 1]) - (y[i + 1], x[j]) - (y[i + 1], x[i + 1]) si o vom aduna la contor. In afara de acest lucru, pentru o pereche de puncte normalizate (x0, y0) - (x1, y1) vom parcurge ca mai sus toate punctele (i, j) cu x0 <= i < x1 si y0 <= j < y1 si vom incrementa count[i][j]. La sfarsit vor conta doar punctele (i, j) pentru care count[i][j] = K. Dezavantajul acestei metode este timpul mare de executie pe care il poate avea, timp dat de parcurgerea efectiva a fiecarui dreptunghi (x0, y0) - (x1, y1), complexitatea maxima devenind astfel O(N^3).

O a treia solutie, nu sta sa incrementeze pentru un dreptunghi normalizat (x0, y0) - (x1, y1) toate punctele din el in matricea count ((x1 - x0) * (y1 - y0) puncte), ci aplica Smenul lui Mars 2D, astfel fiecare incrementare a lui count pentru un dreptunghi (x0, y0) - (x1, y1) se va face in timp O(1) in loc de O (x1 * y1) cat consuma solutia anterioara. Smenul lui Mars 2D poate fi gasit in acest articol. Complexitate finala O(N * N) necesara pentru calcularea submatricii de solutie (cum spune si articolul, count[i][j] va reprezenta acum suma submatricei (1, 1) - (i, j)) si apoi pentru parcurgerea ei. Pentru a calcula count[i][j] am folosit formula count[i][j] = count[i][j] + count[i - 1][j] + count[i][j - 1] - count[i - 1][j - 1].

O alta problema care foloseste aceleasi idei de rezolvare este Dreptunghiuri3

Sarpe2

Construim de la citire un vector pos, unde pos[i] semnifica pe ce pozitie se afla elementul i in sirul pattern de M elemente (pentru exemplu, pos [1] = 1, pos [5] = 2, pos [4] = 3, restul 0). Cum elementele sirului pattern sunt distincte, nu vom ajunge niciodata sa suprascriem peste un pos[i] alta valoare, acestea avand valoare unica.

In continuare vom rezolva problema prin programare dinamica. Notam val = pos [x[i][j]], unde x e matricea NxN data. dp [i][j] reprezinta numarul de drumuri pana in pozitia (i, j) astfel incat pe ultima pozitie a unui drum sa am pattern [val], pe penultima sa am pattern [val - 1], pe antepenultima sa am pattern [val - 2], .... , pe prima sa am pattern [1]. Este evident ca dp[i][j] va fi 0 daca val e 0 (in caz ca elementul curent nu se alfa in pattern, imi este inutil). Ma uit la cei 8 vecini ai lui (i, j) si daca x[vecin_i][vecin_j] este egal cu pattern[val - 1], cresc dp[i][j] cu dp[vecin_i][vecin_j]. Recurenta functioneaza deoarece in dp[vecin_i][vecin_j] am deja numarul de drumuri pattern [1], pattern [2], ...., pattern[val - 1] pana la pozitia (vecin_i, vecin_j) la care voi adauga pattern[val] si voi ajunge in (i, j) cu dp[vecin_i][vecin_j] drumuri valide. Daca am ajuns cu val la elementul M, adaug la solutie dp[i][j] (toate secventa pattern este atinsa in dp[i][j] moduri). Daca val este 1 voi initializa dp[i][j] cu 1, deoarece aici va incepe un nou drum posibil. Se observa ca nu ajung sa numar acelasi drum de 2 ori.

Este posibil ca atunci cand ajung la un dp[vecin_i][vecin_j] acesta sa fie necalculat inca, de aceea recomand implementarea folosind memoizare, ca in sursa de mai jos. Initial toata matrice dp va fi -1 insemnand ca nu a fost calculata inca. 

// a este matricea data NxN
// x este sirul pattern de lungime M
// sol este matricea de dimanica
// in solution se stocheaza rezultatul

int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0}, dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};

int count (int i, int j) //numarul de drumuri valide pentru pozitia (i, j)
{
    int d, now = 0, last;

    if (sol[i][j] != -1) //solutia a fost calculata inainte
        return sol[i][j];
    if (pos[a[i][j]] == 0) //elementul nu se regaseste in pattern
    {
        sol[i][j] = 0;
        return 0;
    }
    last = x[pos[a[i][j]] - 1]; //ultimul element pe care-l cautam pentru a actualiza solutia curenta
    if (pos[a[i][j] == 1) //primul element, se creeaza un drum nou
    {
        sol[i][j] = 1;
        return sol[i][j];
    }
    for (d = 0; d < 8; d ++) //parcurg toti vecinii
        if (a[i + dx[d]][j + dy[d]] == last) //daca vecinul este cel anterior in pattern
            now = (now + count (i + dx[d], j + dy[d])) % MOD; //actualizez numarul de drumuri

    sol[i][j] = now; //acum optimul curent a fost calculat, deci il actualizez in sol
    if (pos[a[i][j]] == M) //daca a fost completat tot patternul
        solution = (solution + now) % MOD; //actualizez solutia
    return sol[i][j];
}

Complexitatea finala este O(N * N) timp si memorie.

Retea2

Rezolvarea necesita cunostine legate de arbori partiali de cost minim. Acest algoritm are doua implementari, N2 sau MlogN. Pentru aceasta problema se indica folosirea celei in N^2 din motive evidente.

Singura particularitate ce trebuie rezolvata este un numar relativ mare de puncte "centrala", ce nu trebuie conectate neaparat intre ele, dar trebuie conectate cu blocurile. Acest lucru se rezolva relativ simplu, atunci cand algoritmul nostru gaseste la un pas o muchie intre doua noduri centrala, o putem ignora, neactualizand solutia.

Aceasta rezolvare are complexitate O(N2) si obtine punctaj maxim.

Unda

Fie x si y doua dintre cele n puncte date in fisierul de intrare. Daca unda loveste primul punct inaintea celui de-al doilea, inseamna ca toate pozitiile posibile ale centrului de unda se afla in locul geometric determinat de mediatoarea segmentului x - y, de partea punctului x. De ce? Pentru ca orice punct aflat de partea cealalta a mediatoarei nu este un centru de unda viabil (unda ar lovi punctul y inaintea punctului x). Cum avem n2 perechi de puncte, putem sa generam efectiv toate mediatorele si sa intersectam semiplanele determinate de acestea, pentru a determina un semiplan de forma unui poligon convex care are toate punctele posibile solutii. Daca acest semiplan are aria 0, atunci nu exista raspuns.

Pentru a determina acest poligon-solutie aplicam urmatorul algoritm: initial, solutia este reprezentata de tot planul xOy. Il putem considera ca fiind un patrat, cu coltul stanga-jos situat la (-INF,-INF) si coltul dreapta sus situat la (INF, INF), unde INF ~ 2*109. Pe masura ce calculam mediatoarele celor n puncte, va trebui sa intersectam acest poligon cu fiecare mediatoare, si sa ne construim un nou poligon, reprezentat de intersectia dintre vechea solutie si partea "buna" a mediatoare curente. Acest lucru se poate face brute-force, parcurgand fiecare latura a poligonului si vazand daca dispare sau se modifica. Dificultatea problemei consta in implementarea ecuatiilor de geometrie si tratarea numeroaselor cazuri particulare.

Complexitatea solutiei este astfel de O(n4), desi datorita numarului relativ mic de puncte din poligonul solutie, algoritmul se comporta mult mai bine in practica. Inca o problema cu care va puteti antrena ce se rezolva pe aceeasi idee este camera.