# [WIP] Contest poziomujący - Rozwiązania zadań

Notatka zawiera opisy rozwiązań (na ten moment wybranych) zadań z contestu poziomującego. Opisy zadań są mniej lub bardziej dokładne, oraz zawierają mniej lub więcej błędów ortograficznych i stylistycznych (starałem się ograniczyć je do minimum, ale nie wszystko pewnie wyłapałem :) )

## Hello World!
Najłatwiejsze zadanie na liście. Najczęstrzym błędem w tym zadaniu było wypisanie nie tego napisu (brak wykrzyknika, różnie wielkości liter, itp.). W takich zadaniach najlepiej jest skopiować oczekiwane wyjście z polecenia. Przykładowe rozwiązanie

#include <iostream>
using namespace std;

int main()
{
    cout<<"Hello world!\n"
    return 0;
}

## Warunki 2
Proste zadanie na użycie instrukcji warunkowej `if`

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin>>n;
    if (n == 42)
        cout<<42;
    else
    {
        if (n > 0)
            cout<<"dodatnia ";
        else
            cout<<"ujemna ";
        if(n % 2 == 0)
            cout<<"parzysta";
        else
            cout<<"nieparzysta";
    }
    return 0;
}

## Prosta pętla
Kolejne zadanie z kategorii proste. Tym razem za pomocą pętli liczmy iloczyn $n$ liczb

#include<iostream>
using namespace std;

int main()
{
    int n, x, iloczyn=1;
    cin>>n;
    for(int i = 0; i < n; i++)
    {
        cin>>x;
        iloczyn *= x;
    }
    cout<<iloczyn;
    return 0;
}

## n-ta różnica w ciągu jeszcze raz
### Sposób 1 - Uczciwy

Podany w zadaniu ciąg liczb naturalnych można zapisać jako
$$
a_n=
\begin{cases}
1 & n=0 \\
a_{n-1} + (n-1) & n \gt 0
\end{cases}
$$

Niestety nie możemy wyznaczyć $n$-tego wyrazu ciągu korzystając ze wzoru rekurencyjnego, ponieważ przekroczymy czas. Musimy więc znaleźć wzór zwraty.

Spróbujmy rozpisać wyraz $a_n$

$$a_n=a_{n-1} + (n - 1) = a_{n-2} + (n - 2) + (n - 1) = \ldots = 1+( n - n) + \ldots + (n - 2) + (n - 1)$$

Okazuje się, że $a_n$ jest równa sumie od $1$ do $n-1$, plus $1$.
Czyli wzór zwarty na $a_n$ to:
$$a_n=\frac{(n-1)n}{2}+1$$
**UWAGA:** Należy zwrócić uwagę na limity w zadaniu. Być może dla odpowiedno dużych wartości $n$ wynik może nie zmieścić się w naszej zmiennej
*Przypomnienie: Wzór na sumę od $1$ do $n$ to $\frac{n(n+1)}{2}$*

### Sposób 2 - Wątpliwy moralnie
[OEIS](https://oeis.org/) to internetowa encyklopedia ciągów. Możemy wyszukać w niej jakiś bardziej znany ciąg wprowadzając kilka pierwyszch jego wyrazów. Strona zwraca nam informacje o ciągach, które zawierają wyszukiwaną sekwencję. Nasz ciąg ma oznaczenie `A152947` oraz możemy się dowiedzieć, że jego wzór zwarty to:
$$a_n=\frac{(n-1)n}{2}+1$$
**UWAGA:** Na stronie pierwszy wyraz ciągu ma indeks `1`. U nas jest to `0`

## SP1LOLUB3/4/17_7
W zadaniu należy posortować nablicę dwuwymiarową w wierszach o wymiarach `NxM`. Można dosyć szybko zauważyć że zadanie można sprowadzić do posortowania `N` tablic o `M` elementach. Do sortowania elementów można było zaimplementować własne sortowanie (np mergesort lub quicksort), albo użyć funkcji `sort` z biblioteki standardowej

#include <iostream>
#include <algorithm>
using namespace std;

int tab[512];
int main() 
{
	int n, m;
	cin>>n>>m;
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
			cin >> tab[j];
		sort(tab, tab+m);
		for(int j = 0; j < m; j++)
			cout << arr[j] << ' ';
		cout << '\n';
	}
    return 0;
}

## Bez średnika ;)
Zadanie z kategorii mocno dziwne.
Wskazówką było to, żeby przyjżeć się instrukcją `if` oraz `while`, więc zróbmy to.

Na początku weźmy `if`'a. Wygląda on następująco:
`if(expr) { body }`
Gdzie `expr` jest wyrażeniem, które zostanie wyliczone, a `body` jest kodem, który wykona się, jeżeli wyliczony `expr` jest prawdą (dla przypomnienia, `0` oznacza fałsz, a cała reszta prawdę)
Wyrażeniem może być dowolna operacja, byleby zwracała jakąś wartość.
Zauważmy że w w ten sposób 'za darmo' możemy wykonywać operacje które zwracają wartość. Wystarczy zapakować je do `if`'a
Analogicznie zachowuje się pętla `while`

Przykładowe rozwiązanie

#include <iostream>
using namespace std;

int main()
{
    if (int n = 1)
    {
        if (cin >> n) {}

        if (int i = 1)
        {
            while (i <= n)
            {
                if (cout << i << ' ') {}
                if (i++) {}
            }
        }
    }
    if (cout << '\n') {}
}

## Prosty kopiec
W zadaniu należało zaimplementować strukturę danych - kopiec - która posiada 3 metody:
- `push x` - dodaj liczbę `x` do struktury
- `pop` - usun największą liczbę ze struktury (o ile taka istnieje)
- `top` - wypisz największą liczbę w strukturze (o ile taka istnieje)

Rozwiązanie można było rozwiązać na 2 sposoby
### Sposób 1 - uczciwa implementacja kopcu
Rozwiązania opiera się na implementaci kopcu binarnego. Operacje `pop` i `push x` będą miały złożoność `O(log n)`, gdzie `n` to ilośc elementów w kopcu, a `top` `O(1)`. Główna ideea jest następująca: do implementacji posłużymy się drzewem binarnym, które będziemy przechowywać w tablicy. Dla wierzchołka o indeksie `i` jego lewe i prawe dziecko będą miały indeksy odpowiednio `2i+1` oraz `2i+2`. Każdy wierzchołek, o indeksie `> 0`, będzie miał dokładnie jednego rodzica, leżącego pod indeksem `(i - 1) / 2`. Dodatkowo chcemy zachować 2 własności
- Drzewo wypełniamy 'na maksa', od lewej strony. Innymi słowami, checemy żeby nasze drzewo było pełnym drzewem binarnym, może poza ostatnim poziomem, w który wypełniamy od lewej strony.
- Dla każdego wierzchołka o indeksie `v` i jego dzieci `u`, `w` `heap[v] >= heap[u]`, oraz `heap[v] >= heap[w]`.

Dokładnie o pomyśle oraz o implementacji można przeczytać [tutaj](https://en.wikipedia.org/wiki/Binary_heap)

#include <iostream>
using namespace std;

#define MAX_SIZE (50000 + 7)
int heap[MAX_SIZE];
int heap_size = 0;

int parent(int i)
{
	return (i - 1) / 2;
}

int leftChild(int i)
{
	return 2 * i + 1;
}

int rightChild(int i)
{
	return 2 * i + 2;
}

void swap(int &x, int &y)
{
	int temp = x;
	x = y;
	y = temp;
}

void push(int x)
{
	if (heap_size >= MAX_SIZE)
		return;

	// first insert the time at the last position of the array
	// and move it up
	heap[heap_size] = x;
	int i = heap_size;
	heap_size++;

	// move up until the heap property satisfies
	while (i != 0 && heap[parent(i)] < heap[i])
	{
		swap(heap[parent(i)], heap[i]);
		i = parent(i);
	}
}

// moves the item at position i of array a
// into its appropriate position
void maxHeapify(int i)
{
	int left = leftChild(i);
	int right = rightChild(i);

	// largest node
	int largest = i;

	if (left < heap_size && heap[left] > heap[largest])
		largest = left;

	if (right < heap_size && heap[right] > heap[largest])
		largest = right;

	// swap the largest node with the current node
	// and repeat this process until the current node is larger than
	// the right and the left node
	if (largest != i)
	{
		int temp = heap[i];
		heap[i] = heap[largest];
		heap[largest] = temp;
		maxHeapify(largest);
	}
}

int top()
{
	return heap[0];
}

void pop()
{
	// replace the first item with the last item
	heap[0] = heap[heap_size - 1];
	heap_size--;

	// maintain the heap property by heapifying the
	// first item
	maxHeapify(0);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, arg;
	string cmd;

	cin >> n;
	while (n--)
	{
		cin >> cmd;
		if (cmd == "push")
		{
			cin >> arg;
			push(arg);
		}
		else if (cmd == "pop")
		{
			if (heap_size > 0)
				pop();
		}
		else if (cmd == "top")
		{
			if (heap_size > 0)
				cout << top() << '\n';
		}
	}

	cout << "all done\n";
	return 0;
}

### Sposób 2 - Kolejka priorytetowa
Można zauważyć że daną struktórę można łatwo zasymulować przy użyciu `priority_queue`. `proprity-queue` to kontener ze standardowej biblioteki języka C++, który umożliwia dodawanie elementu i usunięcie oraz pobranie największego elementu. O kontenerze można doczytać [tutaj](https://en.cppreference.com/w/cpp/container/priority_queue)

## ALLIN1

W zadaniu należy znaleźć długość najkrótszego **spójnego** podciągu który zawiera 3 różne liczby. Możemy zastosować algorytm gąsienicy. Niech zmienne `l` i `r` oznaczają kolejno pozycję początku rozpatrywanego podciągu oraz pozycję jego końca, a w zmiennej `res` znajduje się wynik, który na początku ma wartość `L`. Jeżeli podciąg opisany przez 2 wskaźniki spełnia warunki zadania do sprawdźmy czy jego długość (w tym wypadku `r - l + 1`) jest minimalna, jeżeli tak to aktualizujemy zmienną `res` oraz skracamy rozpatrywany podciąg, przesuwając wskaźnik początku. Jeżeli podciąg nie spełnia warunki to go rozszerzamy przesówając prawy wskaźnik. Należy pilnować żeby nie doszło do: `l > r` oraz `l >= L || r >= L`. Złożoność takiego rozwiązania to `O(n)`

## Policz wyspy
Zadanie polega na wczytaniu 'mapy' złożonej ze znaków `0` i `1` i policzeniu ile jest spójnych obszarów złożonych z samych `1`.
### Sposób 1 - grafy
Zadanie można sprowadzić do zliczenia spójnych składowych w grafie. Graf tworzymy w następujący sposób:
- Wierzchołkami są pola ze znakiem `1`
- Dwa wierzchołki są ze sobą połączone, jeżeli dzielą ze sobą krawędź na 'mapie'

Na tak zbudowanym grafie uruchamiamy algorytm `DFS` dopóki w grafie znajdują się wierzchołki nie odwiedzone. Naszym wynikiem jest ilość wywołań algorytmu `DFS`. Alternatywnie zamiast `DFS` można wykorzystać `BFS`

### Sposób 2 - grafy, ale nie wprost
Sposób jest równoważny ze sposobem 1, ale nie wymaga zrozumienia grafów. Po wczytaniu 'mapy' przechodzimy po niej wiersz po wierszu. Jeżeli natrafimy na `1` to zwiększamy wynik o 1, a następnie zerujemy rekurencyjnie wszystkie sąsiadujące `1`. Po wykonaniu operacji zerowania usunęliśmy wyspę którą właśnie policzyliśmy. Tym sposobem policzmy każdą wyspę, ponieważ jeżeli istnieje to ją odwiedzimy, oraz nie policzymy żadnej więcej niż raz, ponieważ po dodaniu wyspy do wyniku usuwamy ją.

## K-pokrycie zbioru
Na początku przyjżyjmy się limitom zadania. Mamy potencjalnie `10^6` zapytań, a limit czasowy to niecała sekunda. Oznacza to że musimy odpowiadć na zapytania w czasie co najwyżej `0(n log n)`.

Zauważmy, że jeżeli liczba $x$ jest $k$ wyrażalna oraz to $k$ jest najmniejsze takie możliwe, to liczba $x+a$, jest $k+1$ wyrażalna, oraz nie istnieje $j \lt k+1$ takie że $x+a$ jest $j$ wyrażalna. W dużym skrócie, jeżeli znamy wynik dla liczby będącej sumą pewnych elementów naszego zbioru, to umiemy łatwo obliczyć wynik dla tej sumy powiększonej o dodatkowy element z naszego zbioru.

Dostajemy więc funkcję rekurencyjną
$$
f(x)=
\begin{cases}
1 & \exists c \in C: c = x \\
\infty & \text{x nie jest wyrażalny}\\
\min\limits_{c \in C}f(x-c)+1
\end{cases}
$$

Korzystając z tej funkcji umiemy wyznaczyć najmniejsze takie $k$, że liczba $x$ jest $k$ wyrażalna. Jeżeli jednak będziemy wywoływać funkcję za każdym razem to przekroczymy czas (otrzymamy rozwiązanie o złożoności wykładniczej!). Możemy spróbować stablicować wyniki funkcji dla każdej wartości z przedziału $1..N$ i później odpowiadać w czasie stałym na zapytania.

*Wskazówka: najlepiej tablicować wartości funkcij od największych do najmniejszych argumentów, dla kolejnych liczb $C_i$*

## Operacje AND
W zadaniu musimy znaleźć parę liczb $A_i$, $A_j$, taką że $i \neq j$ oraz $A_i \space \& \space A_j$ jest największe.

Bit nazywamy 'zapalonym' jeżeli ma wartość `1`, oraz 'zgaszonym' jeżeli ma wartość `0`

Pierwsza obserwacja:
Zawsze opłaca nam się zapalić bit w rozwiązaniu, jeżeli tylko możemy (całkiem oczywiste, wynika z zapisu binarnego)

Druga obserwacja:
Zauważmy że liczba `10...0` w zapisie binarnym jest większa od wszystkich liczb postaci `0X...X`, gdzie `X` jest `0` lub `1`. Oznacza to że bardziej opłaca nam się brać do rozwiązania bity będące 'najbardziej po lewo' (najbardziej znaczące)

Pierwsza obserwacja:
Jeżeli możemy wziąć $k$-ty bit do rozwiązania (w rozwiązaniu $k$-ty bit będzie miał wartość 1) jeżeli conajmniej 2 liczby z naszego zbioru będą mieć, oprócz zapalonych wszystkich bitów z rozwiązania tj. (`A[l] & res == res`), dodatkowo zapalony $k$-ty bit

Łącząć powyższe obserwacje możemy wymyśleć stosunkowo proste rozwiązanie zadania