Runda 21 - omówienie zadań

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

Runda 21 - omówienie zadań

Postautor: macbon » 08 mar 2015, 21:07

Metro

Było to najprostsze zadanie w całym zestawieniu. Żeby pociąg zmieścił się w tunelu (okręgu) musiał być węższy od powierzchni na której ułożono tory, czyli cięciwy okręgu, i nie stykać się z jego sufitem. Pierwszy warunek jest banalny, wystarczy sprawdzić czy w < c. Drugi warunek polega na sprawdzeniu czy wartość w + h jest mniejsza od sumy promienia okręgu r i długości odcinka, którego końcami są środek cięciwy i środek okręgu. Długość promienia jest znana pozostaje nam jedynie obliczenie drugiej wartości. Ponieważ szukany odcinek razem z połową cięciwy i promieniem tworzą trójkąt prostokątny, to możemy tutaj skorzystać z twierdzenia Pitagorasa. Złożoność obliczeniowa: O(1)

Moonwalk

To zadanie w założeniu miało być drugim pod względem prostoty rozwiązania, jak się jednak okazało sprawiło ono sporo trudności zawodnikom. W zadaniu mamy stwierdzić czy Michael Jackson podczas wykonywania swojego tańca kiedykolwiek znajdzie się na polu a,b startując z pola 0,0. Najprostszym rozwiązaniem jakie od razu przychodzi na myśl jest przeprowadzenie zwykłej symulacji. Niestety takie podejście zaowocuje otrzymaniem werdyktu przekroczenia limitu czasu ponieważ wartości bezwzględne a i b mogą wynosić nawet 10^9.

Rozwiązanie wzorcowe wygląda następująco. Po pierwsze musimy obliczyć o ile nasz bohater przesuwa się na osi X oraz osi Y po wykonaniu pełnej sekwencji ruchów. W tym celu przechodzimy raz całą sekwencję zapisując sobie kolejne pozycje x[i],y[i] na jakich byliśmy, pamiętając aby na początku zapisać punkt startowy czyli 0,0. Ostatnia pozycja zapisana na naszej liście to oczywiście przesunięcie po wykonaniu pełnej sekwencji, oznaczmy je jako px,py. Teraz wystarczy przejść po naszej liście i dla każdego punktu sprawdzić czy istnieje taka liczba całkowita k, która spełnia poniższe równania:

  • k * px + x[i] = a
  • k * py + y[i] = b

Jeżeli istnieje to Michael dotrze na pole a,b. To na co należy jeszcze zwrócić uwagę to zerowe wartości px lub py i fakt, że k nie może być ujemne. Złożoność obliczeniowa: O(n)

Bank

W zadaniu tym możemy dowolną liczbę razy zmieniać typ dokładnie n z 2n-1 operacji, w celu uzyskania jak największego salda. W związku z tym, że w każdym kroku mamy pełną swobodę jeżeli chodzi o wybór n spośród 2n-1 operacji, to nasze zadanie tak naprawdę sprowadza się do wyznaczenia ile maksymalnie dodatnich kwot (wpłat) możemy uzyskać. Do tego celu możemy wykorzystać np. algorytm wyszukiwania w głąb (DFS). Dla danej liczby dodatnich kwot analizujemy jakie mogą być następne ruchy i rekurencyjnie rozpoczynamy ich analizę. Np. dla n = 3 i liczby dodatnich kwot p = 2 (+ + - - -) mamy następujące zamiany:

  • + + + + + p = 5
  • + - + + - p = 3
  • - - + - - p = 1

Kiedy już wyznaczymy maksymalną liczbę dodatnich kwot p, zamieniamy wszystkie wczytane kwoty na dodatnie. Następnie sumujemy p największych spośród 2n-1 kwot i odejmujemy od nich pozostałe. Złożoność obliczeniowa: O(n^2)

Tort 2

Zadanie to najłatwiej rozwiązać w wersji geometrycznej. Początkowo znajdujemy się w punkcie 0,0. Teraz analizujemy kolejne porcje naszego tortu. Jeżeli trafiliśmy na bitą śmietanę to rysujemy odcinek z bieżącego punktu x,y do punktu z prawej x+1,y, w przeciwnym wypadku rysujemy odcinek do punktu u góry x,y+1. Na koniec rysujemy odcinek od punktu początkowego do końcowego. Punkty przecięcia (o współrzędnych całkowitych) tego odcinka z wcześniej narysowanymi wyznaczają nam miejsca, w których tort powinien zostać przekrojony, aby zachować proporcję. Złożoność obliczeniowa: O(n)

Babki

To zadanie można było rozwiązać na dwa sposoby. Pierwszy z nich to użycie preprocessingu czyli wcześniejsze wygenerowanie wszystkich możliwych wyników i zapisanie ich w kodzie. Rozwiązanie takie było możliwe, ze względu na mały rozmiar danych wejściowych.

Rozwiązanie wzorcowe polega na wykorzystaniu twierdzenia Sprague-Grundy'ego. Przedstawimy tutaj wersję rekurencyjną. Tworzymy funkcję f(n) gdzie n to liczba babek w rządku, z którego mamy zabrać k bezpośrednio sąsiadujących. W przypadku gdy n < k możemy od razu zwrócić nimliczbę 0, oznaczającą pozycję przegrywającą. W przeciwnym wypadku rozpatrujemy wszystkie możliwe wybory k sąsiadujących ze sobą babek spośród n jakie mamy dostępne. Dla każdego możliwego wyboru zostaje nam pewna liczba babek l z lewej strony k wybranych oraz liczba p z prawej strony. Liczymy nimsumę (XOR) gier f(l) i f(p) i wynik f(l) XOR f(p) wstawiamy do zbioru Z. Wynikiem wywołania funkcji f(n) jest mex(Z) czyli najmniejsza liczba całkowita >= 0, która nie występuje w zbiorze Z. mex(Z) = 0 oznacza pozycję przegrywającą, zaś mex(Z) > 0 wygrywającą. W związku z tym, że funkcja f może być wielokrotnie wywoływana dla tego samego parametru powinniśmy zapamiętywać obliczone już wyniki.
macbon
Koordynator AlgoLigi
 
Posty: 184
Rejestracja: 19 wrz 2012, 23:38

Re: Runda 21 - omówienie zadań

Postautor: Crucian » 09 mar 2015, 16:36

Słowa
Drzewo przedziałowe
W zadaniu trzeba napisać program wykonujący następujące operacje:
  • Sprawdzenie czy w obu słowach podsłowa znajdujące się na pozycjach od a do b są takie same.
  • Znalezienie i zamienienie na # najbliższej litery będącej na lewo od indeksu a.
Drugą operacje można bardzo łatwo wykonywać za pomocą seta z STLa (jeśli programuje się w C++). Najpierw zapełniamy set liczbami od 0 do n-1 (n to początkowa długość słów) i podczas znajdowania litery będącej na lewo od indeksu a wykonujemy lower_bound, czyli wyszukiwanie binarne i znajdujemy najmniejszą liczbę nie mniejszą niż a. Wtedy cofamy się o jedną pozycję do tyłu i liczba którą otrzymaliśmy jest indeksem najbliższej litery będącej na lewo od a (jeśli nie możemy się cofnąć ponieważ jesteśmy na początku seta to znaczy, że nie ma takiej litery). Po tym oczywiście usuwamy tą liczbę z seta.
Aby sprawnie wykonywać pierwszą operację wykorzystamy fakt, że zawsze porównujemy słowa znajdujące się na tych samych określonych pozycjach. Dla każdej pozycji będziemy trzymać 0 jeśli litery na tych pozycjach są takie same w obu słowach i 1 jeśli nie są takie same. Teraz jeśli suma liczb znajdujących się od indeksu a do b jest równa 0 to słowa są równe, ponieważ między tymi indeksami są same zera. Gdy zamieniamy jakąś literę na # to ustawiamy liczbę dla tej pozycji na 0. Można to zaimplementować na drzewie przedziałowym.

Złożoność obliczeniowa:

Puzzle
Preprocessing, potęgowanie macierzy
Rozwiązanie wykorzystujące preprocessing:
Gdy n jest nieparzyste, wynikiem zawsze jest 0, dla parzystych liczb wynikiem jest .
Wiedząc to możemy obliczyć każde znając tylko wartości i . Tu wkracza preprocessing. Dla wszystkich obliczmy wartości i i wrzućmy je do naszego programu (powinny zając nie więcej niż 50Kb). Teraz jeśli chcemy znaleźć wynik dla pewnej liczby to znajdujemy najbliższą mniejszą wielokrotność i od niej zaczynami liczenie.


Sieć dróg
Cayley's formula
W tym zadaniu można wykorzystać fakt, że dla wierzchołków istnieje dokładnie drzew rozpinających.
Załóżmy, że mamy dokładnie składowych w naszym grafie i kolejno są wielkościami tych składowych.
Szukanym wynikiem jest wtedy:


Złożoność obliczeniowa:

Sortowanie topologiczne i permutacja
Rozważmy pewną liczbę x znajdującą się na pozycji i. Jeśli na lewo od tej liczby wszystkie liczby są mniejsze to liczba ta nie będzie miała żadnych krawędzi wchodzących. Jeśli jest jakaś liczba y na pozycji j, taka że y > x, j < i oraz j jest największe możliwe, to liczba ta musi zostać połączona do jednej z liczb znajdujących się na lewo od i i nie będących na lewo od j, inaczej mówiąc mamy j - i możliwości dodania nowej krawędzi. Problem sprowadza się więc do zadania gdzie dla każdej liczby chcemy znaleźć najbliższą na lewo większą liczbę. Można to łatwo zaimplementować liniowo za pomocą stosu.
Złożoność obliczeniowa:

Złożoność obliczeniowa:

Gra Planszowa
Twierdzenie Sprague-Grundy'ego, sortowanie topologiczne
W tym zadaniu będziemy rozważać wszystkie pionki jako oddzielne gry. Warto od razu wspomnieć, że jeśli na jednym polu znajdują się dwa pionki to są one równoważne sytuacji, w której na tym polu nie ma żadnego pionka. Czemu tak jest ? Jeśli jeden gracz poruszy jednym z tych pionków to drugi gracz może bardzo łatwo powtarzać ruchy pierwszego gracza wykorzystując do tego drugi pionek. W pewnym momencie pionki dojdą do pozycji z której nie będzie można wykonać ruchu i plansza będzie wyglądała tak samo jakby wyglądała bez tych dwóch pionków na początku. Możemy więc dla każdego pola zmniejszyć liczbę pionków do 1 (jeśli liczba pionków na tym polu jest nieparzysta) lub do 0 (jeśli jest parzysta).
Teraz chcemy obliczyć dla każdego pola wartość funkcji Sprague-Grundy'ego. Najpierw wszystkim polom, z których nigdzie nie da się dojść nadajemy wartość 0, bo te pola są przegrywające. Sortujemy graf topologicznie tak, aby wszystkie krawędzie prowadziły w lewo. Teraz możemy przejść uzyskany porządek topologiczny od lewej do prawej i dla każdego wierzchołka odwiedzać wszystkie wierzchołki do których da się bezpośrednio dojść i na ich podstawie obliczać funkcje Sprague-Grundy'ego (dla tych wierzchołków mamy już obliczoną funkcje Sprague-Grundy'ego bo są one w porządku topologicznym na lewo od wierzchołka na którym aktualnie się znajdujemy).
Po obliczeniu funkcji Sprague-Grundy'ego dla wszystkich pól robimy XOR funkcji tych pól na których znajduje się 1 pionek.

Złożoność obliczeniowa:

Bombowa Ucieczka
Brute-force
W tym zadaniu jedyną rzeczą którą trzeba zauważyć jest fakt, że wynik nigdy nie będzie większy niż 4. W najgorszym wypadku po prostu zmienimy licznik wybuchu na 0 wszystkim polom znajdującym się tuż obok pola startowego lub końcowego.
Mając na uwadze ten fakt możemy napisać program kolejno sprawdzający, najpierw czy bez usuwania czegokolwiek w ogóle możliwe jest dojście do wyjścia. Jeśli jest niemożliwe to wynikiem jest 0. Następnie sprawdza wszystkie pojedyncze pola, później wszystkie pary, później wszystkie trójki, i jeśli dla jakiegoś zestawu pól dojście do wyjścia staje się niemożliwe to zwraca odpowiedni wynik. Jeśli dla wszystkich trójek dojście jest możliwe to wynikiem jest albo 4 albo -1. Wtedy wystarczy sprawdzić czy pole wejściowe jest ustawione tuż obok pola wyjściowego. Jeśli tak to wynikiem jest -1, jeśli nie to wynikiem jest 4. Do sprawdzania dojścia do wyjścia można zastosować algorytm BFS.

Złożoność obliczeniowa:





Jeśli znajdziecie jakieś błędy, lub macie inne ciekawe rozwiązania, komentujcie.
Ostatnio zmieniony 13 maja 2015, 19:25 przez Crucian, łącznie zmieniany 3 razy
Awatar użytkownika
Crucian
Organizator AlgoLigi
 
Posty: 37
Rejestracja: 07 sie 2014, 10:07

Re: Runda 21 - omówienie zadań

Postautor: KaMyLuS » 10 mar 2015, 11:08

Można prosić o szersze wytłumaczenie skąd się wziął końcowy wzór z zadania 'Sieć dróg'? W szczególności, czemu w podstawie potęgi jest a nie ? Bo gdyby wersja z była prawidłowa, to można to spróbować uzasadnić na takiej zasadzie, że każdą składową traktujemy jak jeden wierzchołek, zatem trzeba znaleźć drzewo dla wierzchołków. Ale że każdy wierzchołek (składowa) to może być więcej punktów, zatem możemy wybrać każdy z tych 'małych' wierzchołków do finalnego drzewa, stąd trzeba domnożyć rozmiary składowych.

Ale skoro tam jest to nie mam zielonego pojęcia dlaczego, a bardzo mnie to ciekawi.
KaMyLuS
 
Posty: 1
Rejestracja: 10 mar 2015, 10:59

Re: Runda 21 - omówienie zadań

Postautor: witman » 13 mar 2015, 16:04

Bank można obrobić w O(n) 8-)
witman
Koordynator AlgoLigi
 
Posty: 78
Rejestracja: 10 kwie 2013, 21:03

Re: Runda 21 - omówienie zadań

Postautor: macbon » 13 mar 2015, 17:51

Można i takie zadanie zostanie dodane na polskiego SPOJa.
macbon
Koordynator AlgoLigi
 
Posty: 184
Rejestracja: 19 wrz 2012, 23:38

Re: Runda 21 - omówienie zadań

Postautor: spectral_ » 14 mar 2015, 00:37

Można wiedzieć ile % osób zrobiło O(n) podczas Algoligi?
spectral_
Organizator AlgoLigi
 
Posty: 18
Rejestracja: 15 lip 2014, 15:27

Re: Runda 21 - omówienie zadań

Postautor: kokosek » 14 mar 2015, 01:42

20 osób miało O(n) a 14 O(n log n).
~59% miało optymalny algorytm.
kokosek
Koordynator AlgoLigi
 
Posty: 107
Rejestracja: 20 wrz 2012, 16:04

Re: Runda 21 - omówienie zadań

Postautor: narbej » 22 mar 2015, 13:06

Zdanie Tort 2 --> http://pl.spoj.com/problems/AL_21_04/

Można też skorzystać z funkcji nwd
Trzeba najpierw policzyć wszystkie składniki tortu a potem policzyć nwd. Jeżeli nwd == 1 to oczywiście nie ma możliwości podzielić tortu na jakiekolwiek kawałki, bo nie dzielimy ogórka na plasterki, ani 1 porcji zbitej śmietany na mniejsze porcje.
Jeżeli nwd > 1, to możnaby podzielić tort, pod warunkiem odpowiedniego ułożenia składników. Można to sprawdzać np tak:
dla i = 0 do i = cały tort
if ( O / B == suma oi / suma bi) kawałek++
gdzie O i B to całkowite ilości składników, skrócone --> nwd = nwd(O, B); O = O / nwd i B = B / nwd
lecz czy nie można tego równania tak przekształcić, aby uniknąc dzielenia?
Oczywiście:
O * (suma bi) == B * (suma oi)
A czy mnożenia też możemy uniknć?
Oczywiście:
Kod: Zaznacz cały
For (i = 0 to cały tort)
  if ( kawałek == ogórek) to
       suma_O += B;
  else suma_B += O
 if (suma_O == suma_B) kawałki++


PS
Zadanie to na algolidze, zrobiłem z wykorzystaniem nwd, ale trochę inaczej. Tej, opisanej wyżej metody jeszcze nie testowałem, więc jeżeli ktoś to zrobi, to prosiłbym o wzmiankę tu lub na forum spoja i ewentualne umieszczenie takiej wersji w udostępniach kodach w bazie: http://www.mariosoft.pl/spoj/rank.php?id=kody
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Re: Runda 21 - omówienie zadań

Postautor: zaro » 30 mar 2015, 21:31

Crucian pisze:Będzie później.

Czyli będzie kiedyś? :) Zwłaszcza chodzi mi o Puzzle, w których miałem TLE mimo że miałem preprocessing (zapamiętywałem obliczone wcześniej wartości) oraz potęgowanie modulo (a tu już bez preprocessingu, bo wydaje mi się ciężko by było :)).
Obrazek
zaro
 
Posty: 6
Rejestracja: 30 mar 2014, 22:30

Re: Runda 21 - omówienie zadań

Postautor: quenthui » 01 kwie 2015, 23:07

Skoro udało Ci się ułożyć Puzzle z preprocessingiem, to mogłeś zauważyć, że odpowiedzi dla kolejnych parzystych licz układają się w ciąg An = 4*A(n-1) - A(n-2). A1 = 3, A2 = 11.
Wiedząc to i korzystając z szybkiego mnożenia macierzy (http://was.zaa.mimuw.edu.pl/?q=node/36) dało się to sprawnie policzyć.
Był jeszcze jeden problem, mianowicie podczas obliczeń pojawiało się odejmowanie, co prowadziło do ujemnych wartości dzielonych modulo. W efekcie końcowy wynik potrafił wyjść ujemny. Wtedy wystarczyło odjąć wartość bezwzględną wyniku od 1e9+7 i otrzymywało się AC z bardzo ładnym czasem.
quenthui
 
Posty: 3
Rejestracja: 01 kwie 2015, 22:50

Następna

Wróć do Zadania

Kto jest online

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

cron