Mini Liga 2

Omówienie zadań

Para liczb pierwszych

Generujemy w pętli wszystkie możliwe wartości dla liczby x od 1 do s-1. Mając wyznaczoną wartość x wiemy, że wartością y będzie s-x. Kiedy znamy już wartości x oraz y wystarczy sprawdzić czy są one liczbami pierwszymi. W tym celu możemy napisać funkcję, która sprawdza czy dana liczba jest większa od 1 i czy nie ma żadnych dzielników większych od 1, a mniejszych od niej samej.

Oczywiście takie rozwiązanie moglibyśmy przyspieszyć. Pętla mogłaby generować wartości x od 2 do s/2, bo jak wiadomo 1 nie jest liczbą pierwszą, a wartości x większe od s/2 spowodują ponowne sprawdzanie tych samych par liczb. Analogicznie przy sprawdzaniu czy dana liczba jest pierwszą wystarczy sprawdzić czy nie ma żadnych dzielników mniejszych bądź równych jej pierwiastkowi. Biorąc jednak pod uwagę fakt, że maksymalna wartość s wynosi 400 to nie jest to konieczne.

Złożoność czasowa: O(ts²)

Rozwiązanie wzorcowe

Pomiar czasu

Jednym ze sposobów rozwiązania zadania jest obliczenie wyników dla wszystkich możliwych wartości n przed rozpoczęciem wczytywania zestawów danych.

Tworzymy 3 tablice pomocnicze C, B oraz W. Pod i-tym indeksem tablicy C zapisujemy ile segmentów jest zapalonych podczas wyświetlania cyfry i. Pod i-tym indeksem tablicy B będziemy przechowywać najlepszy czas jaki mógł uzyskać Marcin przy i zapalonych segmentach. Analogicznie pod i-tym indeksem w tablicy W będziemy przechowywać najgorszy czas jaki mógł uzyskać Marcin przy i zapalonych segmentach.

Rozpatrujemy każdą liczbę sekund z przedziału od 15×60 do 60×60-1. Są to wszystkie możliwe czasy jakie mógł uzyskać Marcin. Mając dany czas t (w postaci liczby sekund) możemy za pomocą tablicy C w prosty sposób obliczyć ile segmentów jest potrzebnych do jego wyświetlenia. Kiedy znamy już liczbę segmentów s, sprawdzamy czy dany czas t nie jest najlepszym lub najgorszym czasem, jaki możemy dla niej uzyskać. W tym celu aktualizujemy tablice B (B[s] = min(B[s], t)) i W (W[s] = max(W[s], t)).

Po rozpatrzeniu każdej możliwej liczby sekund i uzupełnieniu tablic B oraz W możemy przejść do wczytywania zestawów danych i wypisywania odpowiednio sformatowanych czasów z wymienionych tablic.

Złożoność czasowa: O(T+t) gdzie T to liczba możliwych czasów jakie mógł uzyskać Marcin

Rozwiązanie wzorcowe

Mecz koszykówki

Uwaga! Żeby omówienie było bardziej przejrzyste całkowicie pominięta została kwestia liczenia reszty z dzielenia przez 10⁹+7. Rozwiązanie wzorcowe uwzględnia ją.

Zadanie możemy rozwiązać za pomocą programowania dynamicznego. Tworzymy tablicę pomocniczą DP, w której pod indeksem i będziemy przechowywali liczbę sekwencji rzutów, które sumują się do i punktów.

Wiemy, że 0 punktów możemy uzyskać tylko za pomocą pustej sekwencji rzutów, tak więc ustawiamy DP[0] = 1. Następnie liczymy po kolei wartości dla kolejnych indeksów od 1 do 25. Zastanówmy się teraz jak policzyć liczbę sekwencji rzutów dla i punktów. Rozpatrzmy trzy przypadki jakie były możliwe:

1. Jeżeli ostatni rzut w kwarcie był za 1 punkt to do liczby sekwencji musimy dodać liczbę sekwencji uzyskania i-1 punktów. DP[i] = DP[i] + DP[i-1].
2. Jeżeli ostatni rzut w kwarcie był za 2 punkty to do liczby sekwencji musimy dodać liczbę sekwencji uzyskania i-2 punktów. DP[i] = DP[i] + DP[i-2].
3. Jeżeli ostatni rzut w kwarcie był za 3 punkty to do liczby sekwencji musimy dodać liczbę sekwencji uzyskania i-3 punktów. DP[i] = DP[i] + DP[i-3].

Podsumowując liczba sekwencji rzutów dla i punktów jest równa sumie DP[i] = DP[i-1] + DP[i-2] + DP[i-3]. Oczywiście w 2 i 3 przypadku musimy sprawdzić czy rzut za daną liczbę punktów był w ogóle możliwy.

Kiedy mamy już policzone wszystkie wartości w naszej tablicy DP odpowiedzią dla każdego zestawu danych jest iloczyn DP[p₁] × DP[p₂] × DP[p₃] × DP[p₄].

Złożoność czasowa: O(max(p) + t)

Rozwiązanie wzorcowe

Skracanie ścieżek

Kluczową obserwacją w tym zadaniu jest zauważenie jak zmieniają się najkrótsze ścieżki w drzewie po dodaniu krawędzi przez Jana. Otóż jeżeli w oryginalnym drzewie mieliśmy jakąkolwiek ścieżkę o długości parzystej np. 1 - 2 - 3 - 4 - 5 to łatwo zauważyć, że najkrótsza ścieżka w nowym grafie będzie o połowę krótsza 1 - 3 - 4 ponieważ pojawiły się krawędzie 1 - 3 i 3 - 5. Analogicznie skrócone zostaną ścieżki o długości nieparzystej. Podsumowując dowolna ścieżka o długości x będzie w nowym grafie miała długość x / 2 + x mod 2.

Ta obserwacja w łatwy sposób doprowadza nas do pełnego rozwiązania. Jeżeli oznaczymy przez a sumę wszystkich najkrótszych ścieżek w drzewie, a przez ao liczbę ścieżek o długości nieparzystej to suma ścieżek w nowym grafie jest równa (a - ao) / 2 + ao.

Sumę najkrótszych ścieżek w drzewie i liczbę ścieżek o długości nieparzystej możemy obliczyć za pomocą przejścia grafu w głąb i programowania dynamicznego na drzewie. Dla każdego wierzchołka u obliczamy następujące informacje dotyczące jego poddrzewa:

1. P[u] - sumę długości ścieżek biegnących od korzenia do wszystkich wierzchołków w poddrzewie
2. PE[u] - liczbę ścieżek o długości parzystej biegnących od korzenia do wierzchołków w poddrzewie
3. PO[u] - liczbę ścieżek o długości nieparzystej biegnących od korzenia do wierzchołków w poddrzewie
4. A[u] - sumę wszystkich najkrótszych ścieżek w poddrzewie (nie tylko tych biegnących od korzenia)
5. AO[u] - liczbę ścieżek o długości nieparzystej w poddrzewie

Jeżeli kogoś interesuje szczegółowa implementacja to zapraszam do zapoznania się z rozwiązaniem wzorcowym.

Złożoność czasowa: O(n)

Rozwiązanie wzorcowe