###### tags: `xivlo`

# Zajęcia 28.04.2021

## Zadanie "Województwa"
To zadanie pokazuje, że niewielka modyfikacja porządku danych, może bardzo pomóc - w tym przypadku jest to sortowanie.
Pomysł na rozwiązanie jest następujący. Musimy znaleźć pierwsze takie miasto, którego suma z jeszcze mniejszymi na pewno nie da rady 'przebić' wielkości pozostałych.

Pokażmy sobie to na przykładzie.

Dostajemy dane wejściowe:
`10 3 2 6 7`
które oznaczają, że miasto o nazwie "1" jest wielkości `10`, miasto o nazwie "2" jest wielkości `3`, miasto "3" ma wielkość `2` i tak dalej.

Posortujmy wielkościami te miasta.

wielkości: 2 3 6 7 10
   miasta: 3 2 4 5 1

Dla każdego miasta musimy znać sumę jego samego i jego poprzedników (czyli mniejszych miast) - posłużymy się w tym celu sumami prefiksowymi.
:::warning
Uwaga. Sumy mogą być duże. Gdy suma zaczyna przekraczać $10^{18}$ należy zostawić jako wynik liczbę $10^{18}$. Nie zepsuje nam to rozwiązania, bo szukamy miasta którego suma byłaby mniejsza od 'następnego' miasta, a max. wielkość miasta to właśnie $10^{18}$.
:::

             ↓
sumy pref: 2 5 11 18 28
wielkości: 2 3 6  7  10
   miasta: 3 2 4  5  1

Gdy mamy już przygotowane sumy prefiksowe, wystarczy znaleźć pierwsze miasto, które zsumowane wielkościami z poprzednikami, na pewno nie wygra zawodów na nazwę nowego województwa. Naturnie wszystkie mniejsze od znalezionego, również taką walkę przegrają.

W przykładzie naszym miastem, którego szukaliśmy jest miasto o nazwie "2".
A zatem miasto "2" i wszystkie mniejsze (czyli w tym przypadku tylko miasto "3"), na pewno nie wygrają walki o to, by bajtocja była nazwana ich nazwą.

Pozostałe miasta ("4", "5" i "1"), wystarczy posortować i wypisać, by otrzymać wynik w formacie przyjętym w zadaniu.

Odpowiedź:
`1 4 5`

## Zadanie "Polska Międzygalaktyczna Stacja Kosmiczna"
Ważnym elementem zadania jest fakt, że stacja kosmiczna jest drzewem (w rozumieniu grafowym), a to oznacza, że do z każdego do każdego hangaru prowadzi tylko jedna droga.

Naszym zadaniem jest rozmieszczenie straży przy hangarach, by miała ona oko, na wszystkie korytarze, a jednocześnie, żeby jej ustawienie, było możliwie najtańsze.

By rozwiązać zadanie, możemy uruchomić przeszukiwanie po tym grafie od dowolnego wierzchołka (załóżmy, że będzie to wierzchołek nr 1).

Gdy mamy tylko jeden hangar to nie mamy korytarzy, więc nie musimy stawiać żadnej straży - koszt wyniesie 0. Przy dwóch hangarach mamy jedną drogę. Musimy wybrać jeden z dwóch hangarów (ten tańszy), gdzie będzie stać straż.
Gdy do dwóch hangarów dołączymy trzeci... zastanówmy się.

Zaczynamy przeglądać naszą stację od hangaru nr 1. Wykorzystamy algorytm DFS, a zatem schodzimy rekurencyjnie, tak głęboko jak możemy do sąsiadów danego wierzchołka. Wchodząc do hangaru ustawiamy wartość `dp2` danego hangaru na koszt postawienia przy nim straży. Następnie przeglądamy sąsiadów i po powrocie z sąsiada powiększamy `dp` aktualnego hangaru o `dp2` sąsiada i `dp` aktualnego hangaru o `dp2` sąsiada - w skrócie, naprzemiennie.

Po przejrzeniu wszystkich sąsiadów ustalamy ostatecznie wartość `dp` dla aktualnie przeglądanego wierzchołka i jest to po prostu minimum z `dp` i `dp2`.

Odpowiedzią dla danego przypadku testowego jest wartość `dp` dla stacji nr 1.

## Bazgroły z tablicy
https://miro.com/app/board/o9J_lHLhwYQ=/
<iframe width="768" height="432" src="https://miro.com/app/live-embed/o9J_lHLhwYQ=/?moveToViewport=-1403,-446,4210,2054" frameBorder="0" scrolling="no" allowFullScreen></iframe>