Informatyczny kącik olimpijski

Klocki z numerami i piłeczki na podłodze

W tym odcinku omówimy rozwiązania dwóch zadań z pierwszego etapu XIII Młodzieżowej Olimpiady Informatycznej.

Zadanie (Klocki z numerami). Danych jest $n$ klocków z zapisanymi na nich numerami. Ciąg $a = (a1,a2,...,an)$ opisuje numery zapisane na kolejnych klockach. Mówimy, że kolekcja klocków jest imponująca, jeśli każdy naturalny numer $x$ występuje $x$ razy albo nie występuje wcale. Imponującymi kolekcjami są $(3,2,2,3,3)$ i $(4, 4,1,4,4),$ zaś nie są: $|(1,2,3,4)$ i $|(2,2,3,3).$ Możemy zmienić numer dowolnego klocka na dowolny inny numer. Ile minimalnie zmian numerów należy dokonać, aby otrzymać imponującą kolekcję?

Rozwiązanie $|O$
Nasze rozważania rozpocznijmy od prostej obserwacji:

Obserwacja. W ostatecznym ponumerowaniu żaden klocek nie będzie miał numeru większego niż $n.$

Na mocy powyższej obserwacji możemy ograniczyć się do numerów nie większych niż $n,$ gdyż tylko takie numery będą w ostatecznym ponumerowaniu. Zliczmy, dla każdego $|1⩽ i⩽ n,$ liczbę klocków z numerem $i$ (niech $wi$ oznacza tę wartość). Teraz problem możemy opisać następująco. Mamy $n |$ numerów, a $|i$ -ty numer ma wartość $|w$ Intuicyjnie, wartość numeru oznacza, ile już klocków z tym numerem mamy. Naszym celem jest wybrać najbardziej wartościowy podzbiór numerów sumujących się do $n.$ Wówczas liczba klocków, które należy przenumerować, to $n$ pomniejszone o znalezioną wartość podzbioru.

Otrzymany problem jest podobny do problemu plecakowego (numery są przedmiotami). Z jedną różnicą, chcemy zapełnić plecak "po brzegi", tzn. wybrać podzbiór, którego numery sumują się do $n.$ Opiszemy teraz, w jaki sposób znaleźć taki podzbiór.

Niech $|T[ j],$ dla $0 ⩽ j⩽ n,$ oznacza wartość najbardziej wartościowego podzbioru o sumie numerów równej $j.$ Początkowo $|T[0] = 0$ oraz $|T[ j] = −∞$ dla $1 ⩽ j ⩽ n.$ Następnie przeglądamy kolejne numery, które mogą tworzyć finalny podzbiór (numery od $1$ do $n$ ). Załóżmy, że rozpatrujemy numer $i$ o wartości $wi.$ Chcemy policzyć nowe wartości tablicy $T$ (z uwzględnionym $|i$ -tym numerem), oznaczmy te wartości przez $|T′.$ Wówczas:

T ′[ j] = max(T [ j],T [ j− i]+ w ) jeś liT j−i ~−∞

( $T[ j]$ oznacza przypadek, kiedy do podzbioru o sumie $| j$ nie bierzemy $|i$ -tego oraz wyższych numerów, zaś $T [ j− i]+ w$ oznacza przypadek, kiedy $i$ -ty numer włączamy do podzbioru). Po obliczeniu $′ T ,$ przepisujemy wartości $T ′$ do $|T.$

Dla każdego z $|n$ przedmiotów przeglądamy $n + 1$ elementową tablicę $|T,$ zatem otrzymujemy rozwiązanie w złożoności czasowej $O(n2).$

Zadanie (Piłeczki na podłodze). Danych jest $|n$ punktów na płaszczyźnie, ponumerowanych od $1$ do $n,$ $|i$ -ty punkt ma współrzędne $|(xi,yi).$ Naszym zadaniem jest pokolorować te punkty (każdy punkt na czerwono albo niebiesko). Chcemy, aby odległość pomiędzy najbliższymi dwoma punktami w tym samym kolorze była jak największa.

Rozwiązanie $|O$
Stwórzmy graf pełny $=(V,E), G$ gdzie:

$V = {1,2,...,n}$ - zbiór $n$ wierzchołków,
$E = {(u,v) 1⩽ u < v⩽ n}$ - zbiór $n n−1- | 2$ krawędzi nieskierowanych.

Niech $|i$ -temu punktowi odpowiada $|i$ -ty wierzchołek. Wagą krawędzi $|(u,v)$ niech będzie kwadrat odległości pomiędzy $u$ -tym i $v$ -tym wierzchołkiem, tj. $w(u,$ Na potrzeby tego rozwiązania wprowadźmy nowe pojęcie: $d$ -porządek, czyli takie przyporządkowanie kolorów wierzchołkom, że waga krawędzi pomiędzy dowolnymi dwoma wierzchołkami w tym samym kolorze wynosi przynajmniej $|d.$ Naszym zadaniem jest znaleźć takie największe $|d,$ dla którego istnieje $|d$ -porządek.

Zauważmy, że $d$ -porządek jest również $|d′$ -porządkiem dla $′ |d < d.$ Zatem wartość $|d$ możemy znaleźć za pomocą wyszukiwania binarnego. Pozostało nam więc opisać algorytm, który dla ustalonego $|d$ sprawdzi, czy istnieje $d$ -porządek. Zbudujmy graf $′=(V,E′), G$ gdzie $|E′= {(u,v) (u,v) ∈E ∧ w(u, .$ Otrzymaliśmy graf $′ |G$ z grafu $|G$ poprzez usunięcie krawędzi o wadze większej lub równej $d.$ Nie musimy uwzględniać tych krawędzi, ponieważ ich końce mogą być pokolorowane na ten sam kolor. $G$ będzie $|d$ -porządkiem, jeśli $′ |G$ będzie grafem dwudzielnym. Aby sprawdzić, czy $′ G$ jest dwudzielny, należy sprawdzić, czy każda spójna tego grafu jest dwudzielna. Sprawdzenie, czy spójna jest dwudzielna, rozpoczynamy od wybrania dowolnego wierzchołka i pokolorowania go na czerwono. Następnie przeszukujemy graf (np. za pomocą algorytmu DFS) i odwiedzanym wierzchołkom przypisujemy kolor przeciwny do koloru poprzednika. Jeśli natrafimy na krawędź, która łączy dwa wierzchołki z przyporządkowanym tym samym kolorem, to wiemy, że graf nie jest dwudzielny. Jeśli natomiast nie wystąpi żadna kolizja, to znaczy, że graf jest dwudzielny.

Liczba krawędzi w $G$ jest rzędu $O(n2).$ Zatem algorytm wyszukiwania binarnego wykona $O(log(n))$ faz. W każdej fazie budujemy graf rozmiaru $|O(n$ i w czasie liniowym od jego rozmiaru sprawdzamy, czy graf jest dwudzielny. Całkowita złożoność czasowa to $O(n2$