[SMWP_116] Ranking Gildii

Link do zadania:
http://www.spoj.com/SMWP/problems/SMWP_116/

Opis problemu:
W zadaniu należy posortować dane składające się z nazw gildii, punktów gildii, liczby graczy, nazwy graczy, poziomów graczy oraz ich współczynnika K/D. Priorytety sortowania zostały określone w następujący sposób:
1) Gildie według malejącej liczby punktów, malejącej liczby graczy, alfabetycznie względem nazwy gildii.
2) Gracze w obrębie danej gildii według malejącego poziomu, malejącego współczynnika K/D, alfabetycznie względem nazwy gracza.

Rozwiązanie:
Zadanie jest dosyć proste, lecz jednocześnie odmienne od problemów zamieszczonych na spoju. W większości tamtejszych zadań mamy określoną jedną strukturę i to właśnie ją musimy posortować. W tym zadaniu każda z gildii zawiera określoną liczbę graczy, którzy są również indywidualnie obdarzeni pewnymi cechami takimi jak nazwa, lvl, K/D, dzięki czemu są oni rozróżnialni. Musimy więc stworzyć dwie struktury, które są ze sobą połączone. Struktura gildii pełni tutaj rolę nadrzędną, dlatego to w niej umieszczamy strukturę graczy. Natomiast priorytety sortowania umieszczamy w obydwu zgodne z wymaganiami.
Należy jednocześnie pamiętać o odpowiednim formacie wyjścia, który zawiera tylko same nazwy zarówno graczy jak i gildii. A ponadto po nazwie gildii występuje znak „:” oraz po wypisaniu graczy z danej gildii pusty wiersz.

[SMWP_117] Niebezpieczna Droga

Link do zadania:
http://www.spoj.com/SMWP/problems/SMWP_117/

Opis problemu:
Celem naszego zadania jest znalezienie takiej drogi dla Jasia z domu do szkoły, aby bohater przeszedł przez najmniejszą liczbę skrzyżowań oraz przy tym w jak najkrótszym czasie. Następnie dla wyznaczonej drogi musimy policzyć czas jej przebycia i odjąć uzyskaną sumę minut od godziny 10:00, czyli zakończenia roku szkolnego. Przyjmujemy, że czasy wchodzenia/wychodzenia do/z budynków jest pomijalnie mały. Ponadto czas zawiera się w tym samym dniu, więc maksymalny czas dojścia do szkoły to 600 minut.

Rozwiązanie:
Jednym z rozwiązań jest zastosowanie algorytmu opierającego się na przeszukiwaniu wszerz grafu wagowego. Metodą BFS odwiedzani są najpierw wszyscy sąsiedzi wierzchołka startowego, a następnie zostają odwiedzeni wszyscy sąsiedzi tych sąsiadów. Jednocześnie podczas przechodzenia grafu aktualizujemy w odpowiedni sposób dla każdego wierzchołka odległości od wierzchołka startowego. Mianowicie musimy pamiętać o tym, że na przykład połączenie 1-3 o koszcie 1000 jest „tańsze” od dwóch połączeń 1-2-3 o koszcie łącznym 2. Zatem nasze odległości są aktualizowane tylko wtedy, gdy docieramy do danego wierzchołka po raz pierwszy lub gdy liczba wierzchołków składająca się na obecny wynik jest równa aktualnej liczbie wierzchołków na rozpatrywanej ścieżce i przy tym bardziej opłacalna czasowo. Tym samym nie wyznaczamy co prawda minimalnego kosztu dojścia pomiędzy domem a szkołą, ale za to BFS’em wyznaczamy ścieżkę złożoną z najmniejszej ilości wierzchołków,a więc jest to szukana minimalna liczba skrzyżowań do pokonania przez Jasia. Aktualizowanie odległości od startu ponadto pomaga nam wybrać najszybszą drogę wśród określonych już dróg o minimalnej liczbie skrzyżowań.

[SMWP_106] Diament Bez Skazy

Link do zadania:
http://www.spoj.com/SMWP/problems/SMWP_106/

Opis problemu:
Musisz pomóc Jasiowi sprawdzić czy podany diament jest warty zakupu. Wartym określamy go wtedy, gdy konstrukcja przyjmijmy dla ułatwienia fizyczna diamentu jest grafem pełnym, a więc takim, który zawiera każde możliwe połączenie z innym wierzchołkiem. Zakładając, że graf jest spójny, a relacje są różne i wzajemne tak naprawdę musimy tylko sprawdzić, czy dana liczba połączeń może być konstrukcją grafu pełnego. Jeśli może wypisujemy „TAK”, gdy na pewno nie może wypisujemy „NIE”.

Rozwiązanie:
Aby rozwiązać ten problem musimy najpierw zastanowić się jaka ilość połączeń może występować w grafie pełnym. Odpowiedz brzmi: n(n-1)/2, dla n będącego liczbą wierzchołków grafu. Teraz pozostaje nam jedynie utworzyć odpowiednie równanie: n(n-1)/2=K, gdzie K jest liczbą połączeń podaną w zapytaniu. Jeśli podane równanie posiada takie n naturalne, dla którego równanie jest prawdziwe wówczas istnieje taki graf pełny o n wierzchołkach i K połączeniach. W bardzo łatwy sposób możemy to także sprawdzić korzystając z obserwacji Diofantosa. Mianowicie jeśli sqrt(K*8+1) jest liczbą wymierną to wtedy z danej liczby połączeń różnych i wzajemnych możemy zbudować graf pełny. Warto również zauważyć, że kolejne liczby będące ilością połączeń w grafach pełnych o n wierzchołkach są tak naprawdę kolejnymi liczbami trójkątnymi, gdzie grafpełny(n)=trójkatne(n-1).

[SMWP_105] Respekt

Link do zadania:
http://www.spoj.com/SMWP/problems/SMWP_105/

Opis problemu:
Jaś planuje dołączyć do grona najlepszych graczy. Warunkiem dołączenia do grupy jest pokonanie kilku losowych graczy. Jaś próbuje określić swoje szanse poprzez sprawdzenie ilu graczy posiada więcej krążków niż on. Wówczas liczba ta odzwierciedla listę osób z którymi Jaś będzie miał większe problemy podczas rozgrywek. Naszym zadaniem jest policzenie liczby osób, które mają więcej krążków niż Jaś.

Rozwiązanie:
Naiwnie możemy dla każdego zapytania sprawdzać każdorazowo wejściowy ciąg danych i zliczać ile wartości jest większych od danej liczby pokemonów Jasia. Jednakże spotka to się z komunikatem „TLE”. Co więc możemy zrobić, aby przyśpieszyć czas przeszukiwania ciągu? Możemy go posortować w czasie logarytmicznym, a następnie przeszukać, lecz nie wyraz po wyrazie, a metodą dziel i zwyciężaj. Dzięki temu znacznie zmniejszymy ilość porównywanych elementów. Stosujemy tutaj algorytm przeszukiwania binarnego przekształconego na wyszukiwanie ostatniego elementu zbioru o danej wartości.
Funkcja zwraca nam ostatnią pozycję, na której występuje liczba równa liczbie krążków Jasia. Tym samym wiemy, że wartości „na prawo” od tej liczby są większe. Naszą odpowiedzią jest wówczas liczba wszystkich graczy minus jeden, ponieważ elementy w tablicy liczymy od 0, odjąć pozycja wskazana przez funkcję.

Rozwiązanie sprytne:
Jeszcze łatwiej możemy to zadanie rozwiązać używając zamiast przeszukiwania binarnego gotowej funkcji upper_bound(first,last,valuable), która działa w identyczny sposób wyznaczając nam ostatni element zbioru o danej wartości.

Uwaga! Samo zastosowanie przeszukiwania binarnego na posortowanym ciągu a następnie iterowanie do momentu napotkania większej wartości spotka się również z komunikatem „TLE”.