Atenţie! Aceasta este ultima versiune a paginii, scrisă la 2021-01-01 20:48:49.
Revizia anterioară   Revizia următoare  

Solutii Algoritmiada 2013, Runda 4

Lumanari

Drumetii

Sah3

Fie un pătrat şah arbitrar. Observăm că o condiţie echivalentă ar fi ca toate pătratele de mărime 2×2 din pătratul nostru să fie pătrate şah.

Construim o matrice auxiliară de marime (n - 1, m - 1) în care ţinem minte 1 pe o poziţie (i, j) daca pătratul de dimensiune 2×2 din matricea iniţială cu colţul stânga sus pe poziţia (i, j) este pătrat şah, 0 altfel.
Am redus astfel problema la a afla câte pătrate care conţin doar valori egale cu 1 există într-o matrice, un algoritm bine cunoscut.

Trebuie să avem grijă să numărăm şi pătratele de dimensiune 1×1, deoarece paşii de mai sus au grijă doar de pătratele de latură mai mare sau egală cu 2.

Alianta

Multumim lui mihai50000Mihai-Cristian Popescu •mihai50000 pentru editorial!

Definiţii

Complementul unui graf

Fie G(E, V) un graf neorientat. G'(E', V) este complementul lui G dacă oricare două noduri adiacente în G nu sunt adiacente în G' şi invers.

Clică

O clică este un subgraf cu proprietatea că oricare două noduri sunt adiacente.
O clica maximală este o clică cu proprietatea că nu există nici un nod care adăugat la aceasta să formeze o clică.

Cerinţa

Pe scurt problema ne cere sa afisăm dimensiunea maximă a unui set de noduri astfel încât să nu existe muchie între oricare două noduri din set.

Soluţia

Pentru aproximativ 40 de puncte

Putem rezolva problema prin metoda backtrack.
Se generează toate seturile posibile şi se verifică dacă setul respectiv reprezintă o soluţie.

O mică observaţie

Dacă analizăm graful complementar se observă că soluţia este dimensiunea maximă a unei clici.
Astfel căutăm toate clicile maximale şi afişăm dimensiunea maximă.

Algoritmul pe care îl voi prezenta în continuare se numeşte Bron-Kerbosch.

Pentru început împărţim nodurile în 3 seturi:

  • R - conţine noduri care formează o clică
  • P - conţine noduri pe care dacă le adaugăm la R se formează o clică mai mare.
  • X - conţine noduri care au fost deja procesate sau care deja se află într-o clică pentru a evita dublurile

Iniţial P conţine toate nodurile.
Pentru a rezolva problema ne vom folosi de o funcţie recursivă cu parametrii R , P şi X . f(R, P, X)

Se observă că dacă P = X = 0 nu pot să formez o clică mai mare decat R şi atunci R este o posibilă solutie.

La fiecare pas încercăm să mărim clica curentă prin adăugarea unui nod V \in P .
Când introducem un nod V \in P în R trebuie să scoatem toate nodurile care nu sunt adiacente cu V din X şi P deoarece după apelul recursiv nu s-ar mai respecta proprietatea că orice nod V' \in P \cup X adaugat la R formează o clică.

f(R \cup V, P \cap vecini(V), X \cap vecini(V) )

După apelul recursiv scoatem nodul V din P şi îl introducem în X pentru a evita dublurile. (1\rightarrow 2\rightarrow3, 1\rightarrow 3\rightarrow2)

P = P \backslash V
X = X \cup V

Această soluţie obţine aproximativ 50 de puncte din cauza numărului mare de apeluri ale funcţie recursive.

Pentru 100 de puncte este nevoie de încă o observaţie.

Fie V \in X \cup P . Putem alege ori nodul V ori un nod V' neadiacent cu el deoarece V si V' nu se pot afla simultan în aceeaşi clică.
Avantajul este că putem să alegem nodul cu grad maxim în P \cup X pentru a micşora numărul de apeluri ale funcţiei.
V se numeşte pivot.

Cum n \leqslant 36 este indicată stocarea grafului prin numere şi folosirea operaţiilor pe biţi.

Radacina2

Rama

Solutia O(N^3)

Inainte sa cautam dreptunghiul, trebuie sa ne calculam doua matrice: C[i][j] = numarul de elemente din lantul de 1 de pe coloana j care incepe pe linia i (formal: numarul maxim x astfel incat toate elementele de la (i,j) pana la (i+x-1,j) au valoarea 1) si P[i][j] = indicele minim x care e mai mare decat j si elementul de pe pozitia (i,x) are valoarea 1.
Fixam liniile in care incepe si se termina dreptunghiul. Fie acestea i1 <= i2. Parcurgem coloanele de la stanga la dreapta. Observam ca daca suntem la coloana j, urmatoarea coloana pe care o vom vizita este max(P[i1][j],P[i2][j]) (pentru a sari cele inutile). Vom actualiza la fiecare moment un contor k = numarul de coloane consecutive care incep cu o latura verticala de la i1 pana la i2 (cate coloane am parcurs de la latura din stanga a dreptunghiului). Daca am intalnit deja o latura verticala de lungime cel putin i2-i1+1, incrementam contorul k. In cazul in care coloana j contine o latura verticala de la (i1,j) la (i2,j) (verificarea se face utilizand matricea C), actualizam rezultatul cu dreptunghiul curent care are aria k*(i2-i1+1). Daca mergem la o coloana diferita de j+1, k devine 0.
Cu aceste optimizari obtinem 100 de puncte.

Solutia O(N^2 logN)

Aceasta solutie se bazeaza pe tehnica Divide et Impera. Ne definim o functie recursiva f(i1,j1,i2,j2) care returneaza rezultatul pentru dreptunghiul cu coltul stanga-sus (i1,j1) si coltul dreapta-jos (i2,j2). La fiecare apel impartim dreptunghiul curent in jumatate (pe verticala sau pe orizontala - depinde care e mai mare) si apelam recursiv functia f. Luam maximul dintre cele doua jumatati. Dar, vor exista si dreptunghiuri care incep in prima jumatate si se termina in a doua jumatate. In continuare le vom cauta pe acestea.
Presupunem ca dreptunghiul curent are mai multe coloane decat linii si, deci, l-am impartit in jumatatea stanga si cea dreapta. Celalalt caz e similar. Deci, avem dreptunghiurile (i1,j1)-(i2,m) si (i1,m+1)-(i2,j2). Pentru fiecare pereche de linii (L1,L2) dorim sa gasim dreptunghiul de arie maxima care are laturile de sus si de jos pe L1 si L2, latura stanga in jumatatea stanga si latura dreapta in jumatatea dreapta. Pentru aceasta, fixam L1 si incercam toate L2 urile de la L1+1 pana la i2, actualizand informatiile pe parcurs. In fiecare moment dorim sa stim cea mai mica valoare st astfel incat drumurile (L1,st)-(L1,m) si (L1,st)-(L2,st) contin doar valori de 1. Analog si o valoare dr pentru partea dreapta. La fiecare pas, in cazul in care drumul (L1,st)-(L2,st) nu contine 1, incrementam st pana gasim o valoare buna. La fel si pentru dr.
Pana acum am cautat forme ca si acestea
####           ####
#         si      #
#  (1a)           #  (2a)
#                 #

Trebuie sa le cautam si pe acestea
#                 #
#         si      #
#  (1b)           #  (2b)
####           ####

Acest lucru il facem parcurgand liniile invers, adica fixand L2 si mergand cu L1 de la L2-1 pana la i1.
Toate formele gasite au dimensiunea(latimea in cazul tratat de noi) maxima posibila. Deci, pentru fiecare pereche (L1,L2) partea stanga are dimensiunea maxima posibila cea mai mica forma dintre 1a si 1b. Analog si pentru partea dreapta. Combinand partile, obtinem un dreptunghi candidat si actualizam rezultatul.

Aceasta solutie se incadreaza fara nicio problema in timp.