Runda 28 - omówienie zadań

Tutaj możesz uzyskać pomoc w rozwiązywaniu zadań dostępnych w ramach AlgoLigi

Runda 28 - omówienie zadań

Postautor: Crucian » 26 cze 2016, 18:36

Piszcie jeśli macie jakieś pytania, inne ciekawe rozwiązania lub znaleźliście jakieś błędy w omówieniu.










Piramidka
W rozwiązaniu mamy wypisać N / 2 + 1 wierszy każdy zawierający N znaków.
W i-tym wierszu (liczone od 1) pierwsze oraz ostatnie N / 2 - i + 1 znaków to '.'
Pośrodku znajduje się wycięta część słowa od N / 2 - i + 2 do N / 2 + i indeksu (indeksowane od 1).
Złożoność:

Kolejki
Ze względu na małą liczbę kiosków w zadaniu można rozważyć wszystkie możliwe wybory których jest 6 (3! = 6).
Można też to zadanie rozwiązać bez rozważania wszystkich możliwości, a rozważając tylko jeden przypadek w którym kioski są posortowane względem czasu w którym wszystkie osoby w danym kiosku zostaną obsłużone.
Gdy mamy już daną kolejność kiosków wystarczy je po kolei przejść aktualizując czas przy każdym kiosku w następujący sposób:
czas = max(czas, A_i * B_i) + B_i
A_i to ilość osób w kolejce do i-tego kiosku, B_i to czas obsługiwania jednej osoby.
Złożoność:

Jaś i UFO
Żeby znaleźć rozwiązanie zadania można każdy wiersz rozważyć oddzielnie i dla każdego znaleźć najdłuższy fragment zawierający tylko wycięte pola. Jeśli najdłuższy z takich fragmentów ma długość x to pole największego z kwadratów jest równe x * x.
Złożoność:

Zawody sportowe
Rozwiązanie można zapisać dość krótkim wzorem:
wynik = M + 1 - powtórzenia - mniejsze - większe
powtórzenia: ilość powtórzeń w wynikach rywali
mniejsze: ilość wyników pośród rywali, które są równe lub mniejsze niż najmniejszy możliwy do uzyskania wynik przez Jasia
większe: ilość wyników pośród rywali, które są większe niż największy możliwy do uzyskania wynik przez Jasia

Powtórzenia można obliczyć na wiele sposobów np. sortując tablicę z wynikami rywali by następnie liniowo ją przejść sprawdzając dla każdego elementu (z wykluczeniem pierwszego) czy jest on równy elementowi na poprzedniej pozycji.
Mniejsze oraz większe można obliczyć w dość trywialny sposób, który chyba nie wymaga wyjaśnienia. Należy tu pamiętać, żeby nie odejmować po raz kolejny wyników które są powtórzeniami.
Złożoność:

Jaś i UFO 2
W rozwiązaniu tego zadania rozważymy wszystkie maksymalne spójne fragmenty wyciętych pól. Dwa różne pola należą do tego samego fragmentu jeśli da się z jednego do drugiego dojść używając tylko wyciętych pól oraz wykonując pojedyncze ruchy w pionie, w poziomie lub po skosach.
Dla każdego takiego fragmentu potrzebne nam jest 5 informacji:
  • ilość = ilość wyciętych pól jaka w tym fragmencie się znajduje
  • lewo = indeks kolumny w której najbardziej na lewo położone pole tego fragmentu się znajduje
  • prawo = to samo co wyżej ale pole ma być położone najbardziej na prawo
  • góra = to samo co wyżej ale chodzi nam o indeks wiersza położonego najbardziej na górze
  • dół = to samo co wyżej ale chodzi o pole położone najbardziej na dole
Dla każdego takiego fragmentu muszą zostać spełnione dwa warunki, żeby ten fragment był kwadratem:
  • prawo - lewo = dół - góra
  • ilość = (prawo - lewo) * (dół - góra)
Jeśli w danym fragmencie oba warunki są spełnione to znaczy że dany fragment jest kwadratem spełniającym warunki Jasia.
Wymagane informacje można zdobyć wykorzystując algorytm DFS lub BFS.
Złożoność:

RPG
Dla każdej walki można oddzielnie obliczyć oczekiwaną ilość otrzymanych obrażeń i następnie dodać wszystkie te oczekiwane wartości by otrzymać wynik.
Dla i-tego przeciwnika oczekiwana liczba otrzymanych obrażeń wynosi (1 - d) / (1 - a_i).
Wynika to stąd, że jeśli mamy na pewne zdarzenie szansę p to średnia liczba prób żeby to zdarzenie po raz pierwszy miało miejsce wynosi 1 / p (dowód można znaleźć w wielu miejscach w internecie, przykładowo tu).
Gdy mamy już oczekiwaną liczbę otrzymanych obrażeń to wystarczy tą liczbę przemnożyć przez szansę na to, że nie uda nam się wykonać uniku.
Złożoność:

Kontroler biletów
Rozwiązanie opiera się na wyszukiwaniu binarnym po wyniku. Szukamy najmniejszej ilości przejazdów potrzebnej do sprawdzenia biletów we wszystkich wagonach.
Oryginalne zadanie zostało więc sprowadzone do problemu w którym mamy daną liczbę wagonów oraz czasy przejazdów i chcemy sprawdzić czy istnieje możliwość sprawdzenia biletów we wszystkich wagonach w czasie tych przejazdów. Optymalną strategią w takim wypadku jest sprawdzenie najdalszych wagonów w czasie najdłuższych przejazdów lub sprawdzanie najbliższych wagonów w czasie najkrótszych przejazdów. Obie strategie można zrealizować poprzez przejście posortowanych czasów przejazdów oraz aktualizowanie sprawdzonych wagonów.
W przypadku drugiej strategii należy najpierw ustawić sobie wagon = 0 i następnie aktualizować tą wartość w następujący sposób:
wagon = wagon + floor((czas - 2 * wagon) / 3)
Jeśli pod koniec wartość wagon jest nie mniejsza niż ilość wagonów to wszystkie wagony da się sprawdzić w danym wypadku.
Złożoność:

Niesprawiedliwa gra
Rozważmy liczby zapisane na kartce z punktu widzenia Jasia. Możemy je podzielić na dwa rodzaje.
  • Rodzaj [A] to liczby których wartość możemy dokładnie ustalić. Są to liczby w których zapisie znajduje się przynajmniej jedna cyfra 9 lub są to liczby z przedziału [1, 9].
  • Rodzaj [B] to wszystkie pozostałe liczby których wartości oraz systemu nie możemy dokładnie ustalić.
Teraz rozważmy 3 sytuacje.
  • Sytuacja [1] to sytuacja w której jest ruch dowolnego gracza oraz wszystkie liczby zapisane na kartce są rodzaju [A]. Taka sytuacja sprowadza się do zwykłej gry Nim więc wystarczy obliczyć Nimber czyli xor wszystkich liczb oraz sprawdzić czy jest równy 0.
  • Sytuacja [2] to sytuacja w której jest teraz ruch Stasia oraz przynajmniej jedna liczba jest rodzaju [B].
    W takiej sytuacji zawsze wygrywa Staś. Może on dla dowolnej liczby rodzaju [B] ustalić jej system liczbowy, jej wartość i do końca gry się tej wartości trzymać, a Jaś w żaden sposób nie może wartości tej liczby zmienić. Rozważmy pewną liczbę rodzaju [B]. Jaś jest w stanie na podstawie jej zapisu ustalić do jakich systemów liczbowych może należeć. Jeśli największa cyfra tej liczby to X to liczba ta może należeć do jednego z systemów X + 1'ego, ..., dziesiętnego. Staś może sobie wybrać jeden z tych systemów, powiedzmy że wybrał system Y. Jeśli Jaś chciałby w jakiś sposób wpłynąć na decyzję Stasia to musiałby wykonać ruch, który sprawiłby że w danej liczbie liczba możliwych systemów to Y + 1'y, ..., dziesiętny. Nie jest jednak w stanie wykonać takiego ruchu ponieważ Staś może w takiej sytuacji powiedzieć, że system w jakim ta liczba była zapisana to system Y i Jaś wykonał ruch wbrew zasadom. Skoro więc Staś może sobie w dowolny sposób ustalić wartości liczb rodzaju [B] to z jego punktu widzenia po ustaleniu wszystkich wartości gra sprawdza się do gry Nim, a skoro istnieje przynajmniej jedna liczba rodzaju [B] to Staś może uzyskać co najmniej dwie różne wynikowe wartości Nimbera, więc zawsze może uzyskać sytuację wygrywającą, czyli taką w której Nimber nie jest równy 0.
  • Sytuacja [3] to sytuacja taka jak powyżej jednak osobą wykonującą teraz ruch jest Jaś, czyli sytuacja którą mamy w zadaniu daną i dla której musimy określić czy da się wygrać.
    Jaś chce wygrać, a żeby wygrać nie może przede wszystkim dopuścić do sytuacji [2]. Musi więc wszystkie liczby rodzaju [B] sprawdzić do rodzaju [A]. Po drugie musi sprawić, że po jego ruchu sytuacja z punktu widzenia normalnego Nima będzie przegrywająca, czyli Nimber będzie równy 0.
Znając już te wszystkie możliwe sytuacje możemy określić warunki, które musi spełnić wygrywające ustawienie:
  • Jeśli nie ma żadnej liczby rodzaju [B] to Nimber nie może być równy 0.
  • Jeśli pośród liczb znajduje się dokładnie jedna liczba rodzaju [B] oraz jeśli minimalny system w którym ta liczba może zostać zapisana to M to Jaś może tą liczbę zmienić na jedną z liczb z przedziału [0, M] (jeśli zamieniłby na jakąś inną to albo ta liczba nadal byłaby rodzaju [B] albo wykonałby niepoprawny ruch), więc jeśli Nimber wszystkich liczb z wykluczeniem jedynej liczby rodzaju [B] zawiera się w tym przedziale to Jaś może po swoim ruchu utworzyć sytuację przegrywającą dla swojego przeciwnika.
Złożoność:

Prostokąty-palindromy
W rozwiązaniu będziemy dla każdej litery obliczać ilość prostokątów-palindromów których środkiem jest ta właśnie litera.
Żeby to zrobić najpierw trzeba obliczyć dla każdej litery promień palindromu pionowego oraz poziomego. Można to zrobić wykorzystując algorytm Manacher'a lecz równie dobrze można dla każdej litery liniowo znajdować oba palindromy ponieważ nie zmieni to ostatecznej złożoności rozwiązania.
Niech PION[i][j] oznacza promień najdłuższego palindromu pionowego którego środkiem jest litera w rzędzie i oraz kolumnie j.
Podobnie niech POZIOM[i][j] oznacza promień najdłuższego palindromu poziomego.
Żeby pewien prostokąt o wysokości H i szerokości W był prostokątem-palindromem wszystkie litery w środkowej kolumnie tego prostokąta muszą mieć wartość POZIOM[i][j] nie mniejszą niż W oraz wszystkie litery w środkowym rzędzie muszą mieć wartość PION[i][j] nie mniejszą niż H.

Rozważmy więc każdą literę jako środek prostokąta. Dla każdej litery w i-tym wierszu oraz w j-tej kolumnie najpierw ustawimy szerokość prostokąta W = 1, oraz maksymalną wysokość H = PION[i][j], by następnie pojedynczo zwiększać szerokość prostokąta aktualizując przy tym maksymalną jego wysokość. Żeby uzyskać końcową odpowiedź wystarczy przy każdej iteracji zwiększać ją o maksymalną wysokość dla danego prostokąta: wynik += H. Pytanie pozostaje jak aktualizować maksymalną wysokość prostokąta.
Po pierwsze przy każdym zwiększeniu szerokości trzeba porównać aktualną wysokość z promieniami nowych, skrajnych pól w środkowym wierszu prostokąta, czyli:
H = min(H, min(PION[i][j - W], PION[i][j + W]))
Po drugie trzeba sprawdzić czy wszystkie litery w środkowej kolumnie aktualnego prostokąta mają promień poziomego palindromu nie mniejszy niż H, czyli czy
POZIOM[i - k][j] ≥ W oraz POZIOM[i + k][j] ≥ W dla wszystkich k ≤ H
W wypadku w którym te warunki nie są spełnione zmniejszamy H póki wszystko jest w porządku lub jeśli H osiągnie wartość 0 to kończymy rozważanie aktualnej litery. Żeby dość sprawnie sprawdzać ten drugi warunek możemy dla każdej litery w tej samej kolumnie co sprawdzana litera (czyli środkowej kolumnie prostokąta) obliczyć minimum z poziomych promieni dla danej litery oraz wszystkich liter z tej kolumny które również muszą być w prostokącie-palindromie jeśli dana litera w nim jest . Łatwiej będzie to zobaczyć w praktyce więc oto przykład:

Rozważana litera jest czerwona.
aaaaa
bbacc
baaac
aaaaa
aaaaa
aaaaa
aaaaa


Oto tablica POZIOM dla interesujących nas liter
aa3aa
bb1cc
ba2ac
aa3aa
aa3aa
aa3aa
aa3aa


Oto wyliczone minimum:
aa1aa
bb1cc
ba2ac
aa3aa
aa2aa
aa1aa
aa1aa


Minimum można dość prosto liniowo obliczyć. Wystarczy iść wszerz pionowo od aktualnie rozważanej litery z pozycji [i][j] oraz za każdym razem wpisywać w minimum[] aktualnie najmniejszy napotkany poziomy promień.
Mając to wyliczone można w łatwy sposób sprawdzać drugi warunek w następujący sposób:
while(H > 0 and minimum[i - H + 1] < W + 1) H--;
Złożoność rozwiązania:

Król jest tylko jeden
Przy rozwiązywaniu tego zadania najpierw warto się zastanowić jak dla danego pola, danych wymiarów szachownicy oraz danej ilości ruchów można obliczyć to co mamy w zadaniu dane, czyli ilości kombinacji kończących się na każdym z pól. Myślę, że nie trudno jest tu wpaść na rozwiązanie dynamiczne o złożoności .
Pierwszym ważnym spostrzeżeniem jest to, że liczby kombinacji ruchów bardzo szybko rosną, zwłaszcza jeśli plansza jest dość duża. Dla nieskończenie dużej planszy już po około 25 ruchach największa z liczby kombinacji ruchów osiągnie wartość w okolicach .
Skoro liczba ruchów jest dość mała to również liczba pól dla których ilość kombinacji ruchów jest większa od 0 w wejściowej planszy będzie dość mała, a dokładniej, nie większa niż ilość ruchów podniesiona do kwadratu. Można więc wziąć ten nieduży wycinek z całej planszy oraz dla wszystkich pól przeprowadzić symulację, czyli obliczać dla kolejnych ruchów ilość kombinacji dla tego wycinka planszy oraz sprawdzać czy obie plansze są równe. Można to zrobić na wiele sposobów. Np. można przeprowadzać symulację póki ilość kombinacji w polu z którego zaczęliśmy jest mniejsza niż ilość kombinacji w tym samym polu ale w wejściowej planszy, a gdy to pole osiągnie już nie mniejszą wartość to porównać obie plansze. Takie rozwiązanie powinno mieć złożoność O(s^5) gdzie s to maksymalna liczba ruchów równa około 25 w najgorszym wypadku. Nie jest to jednak rozwiązanie wystarczająco szybkie. Wymaga ono jednej drobnej optymalizacji. Poszukiwane pole zawsze będzie miało jedną z największych ilości kombinacji. Niekoniecznie największą ale jedną z największych, zwłaszcza dla większych planszy. Można więc posortować wszystkie możliwe pola oraz w takiej kolejności przeprowadzać symulacje. Taka optymalizacja w moim przypadku przyspieszyła rozwiązanie ponad dwudziestokrotnie.

Mury
Rozwiązanie odpiera się na programowaniu dynamicznym po maskach bitowych. Dla każdego możliwego podzbioru wsi oraz pierwszych i miast będziemy trzymać najlepszy możliwy do osiągnięcia wynik.
Najpierw będziemy rozważać wszystkie miasta po kolei. Dla każdego miasta przechodzimy wszystkie wsie w posortowanej kolejności od tych najbliżej rozważanego miasta do tych najdalej. Gdy jesteśmy na j-tej wsi to znaczy, że wokół aktualnie rozważanego miasta budujemy mur, który otacza wszystkie wsie od 1 do j-tej. Dla każdej takiej rozważanej budowy muru przechodzimy wszystkie możliwe podzbiory wsi. Dla każdego takiego podzbioru uzupełniamy ten podzbiór o wszystkie wsie od 1 do j oraz sprawdzamy czy z nowym murem rozwiązanie jest lepsze niż do tej pory zapisane.
Można to wszystko rozwiązać wykorzystując operacje bitowe.
Złożoność rozwiązania:

Jaś, drzewo i dziwne pytanie
Przed opisaniem rozwiązania wzorcowego opiszę rozwiązanie prostsze, będące wstępem do wzorcowego, którego złożoność pamięciowa to , a czasowa to .

Rozwiązanie to opiera się na programowaniu dynamicznym. Ukorzeńmy sobie drzewo w wierzchołku 1. Dla każdego wierzchołka v będziemy trzymać dwa drzewa przedziałowe mające N liści dla indeksów od 1 do N. Jedno drzewo na każdej i-tej pozycji będzie trzymało długość Najdłuższego rosnącego podciągu w poddrzewie wierzchołka v zaczynającego się na wierzchołku z liczbą i (jeśli nie ma takiego wierzchołka to wartość = 0). Drugie drzewo będzie takie samo jak pierwsze, jednak będzie trzymało Najdłuższe malejące podciągi. Warto również wspomnieć, że trzymane Najdłuższe rosnące/malejące podciągi zawsze są "skierowane" w dół, czyli każda następna liczba musi być w poddrzewie poprzedniej.
Oba drzewa muszą również obsługiwać następujące operacje:
  • wstaw wartość x na pozycję y: wstaw(x, y)
  • znajdź największą wartość z przedziału [l, r]: wezMax(l, r)
Gdy mamy już gotowe drzewa można przejść do obliczania wartości. Wykonujemy DFS z wierzchołka w którym ukorzeniliśmy sobie drzewo (lub przechodzimy wierzchołki drzewa w takim porządku, żeby każdy z synów wierzchołka v był zawsze odwiedzony przed nim samym) i wykonujemy pewne aktualizacje na drzewach.
Jesteśmy aktualnie na wierzchołku z wpisaną liczbą v.
  • Jeśli wierzchołek jest liściem to w oba drzewa na pozycję v wstawiamy 1 informujące o tym, że istnieje LIS (Najdłuższy rosnący podciąg) oraz LDS (Najdłuższy malejący podciąg) o wielkości 1, czyli zawierający tylko nasz wierzchołek v. Trzeba tu również zaktualizować wynik = max(wynik, 1).
  • Jeśli wierzchołek v nie jest liściem to po kolei przechodzimy wszystkie poddrzewa i "podczepiamy" te poddrzewa do naszego wierzchołka aktualizując w odpowiedni sposób wartości w drzewach. Dla każdego poddrzewa ukorzenionego w wierzchołku u:
    • Pierw aktualizujemy nasz wynik zakładając, że LIS zawiera wierzchołek v. Znajdujemy długość LIS z przedziału [1, v - 1] w drzewie przedziałowym wierzchołka v (czyli najpierw w pustym drzewie przedziałowym, ale potem zawierającym wartości po podczepieniu pewnych poddrzew) oraz LDS z przedziału [v + 1, N] w drzewie przedziałowym rozważanego poddrzewa wierzchołka u i aktualizujemy wynik o obie wartości zwiększone o 1 (1 odpowiada za nasz wierzchołek v). Potem robimy prawie to samo, tylko odwrotnie. Bierzemy LDS z drzewa przedziałowego wierzchołka v oraz LIS z drzewa przedziałowego wierzchołka u i po raz kolejny aktualizujemy wynik.
    • Następnie przechodzimy wszystkie wierzchołki z poddrzewa u i dla każdego wierzchołka w po raz kolejny aktualizujemy wynik tym razem w następujący sposób.
      Z drzewa przedziałowego LIS v bierzemy wezMax(1, w - 1) i dodajemy do niego wezMax(w, w) z drzewa przedziałowego LDS u. Uzyskaną wartość porównujemy z wynik i aktualizujemy jeśli trzeba.
      Później robimy to samo, ale bierzemy LIS z u oraz LDS z v.
    • Gdy mamy już zaktualizowany wynik możemy przejść do "podczepiania" rozważanego poddrzewa. Po raz kolejny przechodzimy wszystkie wierzchołki w z poddrzewa oraz do drzewa przedziałowego LIS wierzchołka v robimy wstaw(w, val), gdzie val jest wartością wziętą z drzewa przedziałowego LIS z wierzchołka u: wezMax(w, w). To samo robimy dla LDS.
  • Gdy już podczepiliśmy wszystkie poddrzewa do wierzchołka v trzeba jeszcze zaktualizować drzewo przedziałowe o LIS i LDS zaczynające się na naszym wierzchołku v. Można to zrobić bardzo prosto, wykonując operację wstaw(v, wezMax(1, v - 1) + 1) dla drzewa przedziałowego LIS dla wierzchołka v oraz wstaw(v, wezMax(v + 1, N) + 1) dla drzewa przedziałowego LDS dla wierzchołka v. Po zaktualizowaniu tych wartości powinno się również zaktualizować wynik o wstawione wartości[/b].
Takie rozwiązanie pozwala na obliczenie wszystkiego w czasie i złożoności pamięciowej .

Żeby zoptymalizować to rozwiązanie skorzystamy z faktu, który mówi, że jeśli utworzylibyśmy ścieżki na drzewie w taki sposób, że z każdego wierzchołka ścieżka prowadziłaby do poddrzewa z największą ilością wierzchołków to jeśli z pewnego wierzchołka szlibyśmy w górę do korzenia to zmienilibyśmy ścieżkę razy (korzysta się z tego faktu przy Heavy Light Decomposition). Udowodnić to można w taki sposób. Jeśli idziemy z pewnego wierzchołka u do jego ojca v oraz zmieniamy przy tym ścieżkę, to znaczy że istnieje pewne poddrzewo v mające nie mniej wierzchołków niż poddrzewo u, więc poddrzewo wierzchołka v ma co najmniej 2 razy więcej wierzchołków niż poddrzewo u. Więc za każdym razem gdy zmieniamy ścieżkę to ilość wierzchołków zwiększa się minimum dwukrotnie, a skoro maksymalna liczba wierzchołków to N, to idąc w górę może być tylko zmian.
Wykorzystamy ten fakt w taki sposób, że podzielimy sobie drzewo właśnie na takie ścieżki, oraz wszystkie wierzchołki należące do jednej ścieżki będą współdzieliły drzewa przedziałowe, przy czym każde drzewo przedziałowe musi mieć tyle indeksów ile wierzchołków zawiera poddrzewo ukorzenione w wierzchołku będącym początkiem danej ścieżki. Można to też inaczej sformułować. Jeśli z pewnego wierzchołka szlibyśmy w górę do korzenia drzewa to przeszlibyśmy pewne różne ścieżki. Ten wierzchołek musi należeć do każdego drzewa przedziałowego ścieżki którą się przeszło. Stąd wynika, że złożoność pamięciowa to . Teraz podczas wykonywania obliczeń, czyli podczas podczepiania poddrzew będziemy podczepiać do każdego wierzchołka wszystkie poddrzewa oprócz tego który należy do tej samej ścieżki, czyli tego z największą ilością wierzchołków. W sumie podczas podczepiania przejdziemy wierzchołków ponieważ każdy wierzchołek jest przechodzony podczas podczepiania tyle razy ile różnych drzew przedziałowych go zawiera czyli dla każdego wierzchołka jest to razy.
Te optymalizacje sprawią, że złożoność pamięciowa będzie wynosiła , a złożoność obliczeniowa .
Ostatnio zmieniony 05 lip 2016, 14:27 przez Crucian, łącznie zmieniany 1 raz
Awatar użytkownika
Crucian
Organizator AlgoLigi
 
Posty: 37
Rejestracja: 07 sie 2014, 10:07

Re: Runda 28 - omówienie zadań

Postautor: macbon » 26 cze 2016, 20:33

Ech lubię te momenty jak człowiek dostaje WA przez zaćmienie umysłu. W zawodach sportowych założyłem, że pierwszy jest zawodnik z minimalnym wynikiem, a nie maksymalnym :P

Moje rozwiązanie wykorzystywało strukturę zbioru (np. set w C++) co już zapewniało mi eliminowanie powtórzeń. Do tego zbioru pakowałem wszystkie wyniki zawierające się w przedziale <suma(a_i), suma(b_i)>. Wynikiem jest liczba elementów w zbiorze. Dodatkowo jeżeli suma(a_i) jest mniejsza od najmniejszego elementu w zbiorze to wynik zwiększamy o 1.

Niestety jak już napisałem wcześniej podczas zawodów sprawdzałem suma(b_i) z największym elementem zbioru :P
macbon
Koordynator AlgoLigi
 
Posty: 184
Rejestracja: 19 wrz 2012, 23:38

Re: Runda 28 - omówienie zadań

Postautor: narbej » 05 lip 2016, 10:17

macbon pisze:.... Dodatkowo jeżeli suma(a_i) jest mniejsza od najmniejszego elementu w zbiorze to wynik zwiększamy o 1....


Można na początku, albo na końcu wrzucić suma(a_i) do seta i wtedy nie trzeba sprawdzać powyższego warunku - zrobi się to automagicznie samo [mechanizmem seta]. Oczywiście nic to nie zmienia [może tylko o jedną linijkę kodu mniej a może nawet nie]

PS
Czy ja się tak zestarzałem, czy poziom wiedzy i konkursów tak się podniósł, czy i to i to? ;-)
W każdym razie gratuluję, brawo.
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Re: Runda 28 - omówienie zadań

Postautor: narbej » 05 lip 2016, 10:35

Jaś i UFO

Fajne zadanie.
Dodatkowo, można uwzględniać znalezione już x i szukać tylko w tych miejscach, gdzie może się jeszcze kryć większe x [większy kwadrat] niestykający się ze znalezionym [x]. A więc gdy już mamy jakieś x, nie musimy sprawdzać całej linii ale także nie do ostatniej linii, ale tylko do N - x.
Dla tak małych danych nie ma to większego znaczenia, [więc tylko teoretyzuję] ale dla większych, kto wie?
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Re: Runda 28 - omówienie zadań

Postautor: Crucian » 05 lip 2016, 10:49

Złożoność to O(n^2) chociażby ze względu na wczytywanie danych.
Nawet jeśli by tylko rozpatrywać właściwy algorytm to wydaje mi się, że optymalizacje o których wspomniałeś nie tylko nie zmienią złożoności, ale również w niczym nie pomogą w sytuacji w której pod sam koniec wynik jest bardzo mały, np. gdy w całym polu jest tylko jedno wycięcie.
Jeśli interesują Cię lokalne optymalizacje to polecam rozwiązać zadanie "Król jest tylko jeden" ;)
Awatar użytkownika
Crucian
Organizator AlgoLigi
 
Posty: 37
Rejestracja: 07 sie 2014, 10:07

Re: Runda 28 - omówienie zadań

Postautor: narbej » 05 lip 2016, 11:05

Jaś i UFO 2

Jeszcze fajniejsze zadanie ;-)
Można:
  1. zapisać całą sytuację w tablicy-planszy
  2. przeglądać planszę wierszami i po natrafieniu na '.' uruchamiac procedurę sprawdzającą
  3. procedura jako parametr dostaje wsp lewego górnego rogu [LG] kwadratu '.' do sprawdzenia i zwraca wartość typu bool czy to UFO czy nie
  4. procedura na podstawie wsp LG sama oblicza szerokość i wysokość kwadratu i sprawdza, czy w środku są kropki '.', a na zewnątrz [krawędź otaczająca] nie ma ich ['.'] - nie ma dotykającego innego kwadratu lub prostokąta.. Gdy wszystko ok, procedura zamienia kropki na '#' i zwraca wynik ok, to UFO.
  5. chyba to by było na tyle...?

PS
Aby ułatwić sobie życie, można planszę otoczyć murkiem: viewtopic.php?f=6&t=86

PS 2
@Crucian Co do złożoności [w poprzednim poście] oczywiście masz rację i się wycofałem z moim pytaniem i wątpliwością [o złożoność] - wyedytowałem i skasowałem tamten fragment.
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Re: Runda 28 - omówienie zadań

Postautor: narbej » 05 lip 2016, 13:45

Kontroler biletów

Też fajne zadanie
Po ponad 10 zgłoszeniach i kilku próbach i testach u siebie i po dokładnym przemyśleniu podpowiedzi udało mi się uzyskać AC. Czas może nie najlepszy - cin+cout więc nawet tylko szybszym i/o mógłbym dużo zyskać, ale najlepsze program mają chyba coś więcej.
Zastanawia mnie co innego. Skąd pomysły na takie zadania i skąd pomysły na ich rozwiązanie? Niebueskie książeczki czy jeszcze co innego?

PS
Wymyśliłem błędny algorytm liniowy, ale dla:
2
2 11
27 21
2 11
21 27
miałem:
2
NIE

PS 2
wagon = wagon + max(0, floor((czas - 2 * wagon) / 3))
można uprościć do:
wagon = wagon + (czas - 2*wagon)/3
bo dzielenie całkowitoliczbowe zawsze jest typu floor
[gdy] bo ciąg jest posortowany i kolejne czasy są nie mniejsze, a więc czas - 2*wagon zawsze będzie co najmniej dodatni lub równy zero. [zobacz np 21, 21, 21, 21, 21 .......]
gdyby był nie posortowany, to przecież algorytm nie zadziała, chyba, że się mylę?

PS 3
Jeżeli celem podpowiedzi [równania] było małe utrudnienie, to soory i oczywiście wyedytuje i usunę PS 2
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Re: Runda 28 - omówienie zadań

Postautor: Crucian » 05 lip 2016, 14:30

To zadanie wymyśliłem wracając pociągiem z Olimpiady Informatycznej kilka miesięcy temu. Spisałem pomysł i wróciłem do niego jakiś czas temu przygotowując rundę.

Co do zapisanego równania to wolałem dodać funkcję floor(), żeby nikt przypadkiem nie pomyślał, że wynik dzielenia ma być ułamkiem. max(0, ...) usunąłem bo faktycznie jest niepotrzebne.
Awatar użytkownika
Crucian
Organizator AlgoLigi
 
Posty: 37
Rejestracja: 07 sie 2014, 10:07


Wróć do Zadania

Kto jest online

Użytkownicy przeglądający to forum: Obecnie na forum nie ma żadnego zarejestrowanego użytkownika i 1 gość

cron