FRAKTAL X - opinie

Jeżeli chodzi o zadanie “Kwadratowy świat II” to szczerze mówiąc spodziewaliśmy się większej liczby AC. W zadaniu mamy n punktów i musimy stwierdzić ile różnych kwadratów równoległych do osi układu współrzędnych możemy ułożyć. Mamy również zagwarantowane, że punkty się nie powtarzają.

Rozwiązanie naiwne to oczywiście 4 zagnieżdżone pętle, z których każda wybiera 1 wierzchołek kwadratu. Mając wybrane 4 wierzchołki sprawdzamy czy tworzą kwadrat równoległy do osi układu współrzędnych. Takie rozwiązanie ma złożoność O(n^4), biorąc pod uwagę, że maksymalna wartość n wynosi 10^6 to nie ma możliwości żeby zmieściło się ono w czasie bo w 4s musielibyśmy wykonać 10^24 operacji.

Rozwiązanie naiwne moglibyśmy przyspieszyć stosując wyszukiwanie binarne. Jeżeli mamy wybrane 2 wierzchołki, które tworzą bok kwadratu to współrzędne pozostałych 2 możemy sobie łatwo wyznaczyć, a następnie za pomocą wyszukiwania binarnego sprawdzić czy takie punkty występują w naszym zbiorze. Pojedyncze wyszukiwanie binarne na zbiorze 10^6 elementów wynosi maksymalnie 20 operacji, co oznacza, że jest to bardzo duże przyspieszenie w porównaniu z wyszukiwaniem liniowym. Złożoność takiego podejścia wynosi O(2 * n^2 * log(n)) czyli dla maksymalnych danych byłoby to 4 * 10^13 operacji. To dalej jest za dużo.

W tym momencie możemy zauważyć, że nawet gdyby udało nam się zejść do złożoności O(n^2) to prawdopodobnie i tak dostaniemy TLE, gdyż będzie to 10^12 operacji. Wiemy jednocześnie, że nie rozwiążemy tego zadania bez wyznaczenia co najmniej 1 boku kwadratu. Co zatem należy zrobić?

Kluczowa obserwacja jest taka, że powierzchnia, na której występują punkty jest mała. W pionie lub poziomie nie będziemy mieli nigdy więcej niż 2001 punktów. Wiemy również, że nasz kwadrat będzie miał wszystkie boki równoległe do jednej z osi. W związku z powyższym łatwo można wywnioskować, że nie opłaca się tworzyć boku z punktów, które nie mają takiej samej wartości współrzędnej x albo y. Skorzystajmy z tych faktów. Posortujmy punkty rosnąco po współrzędnej x, a jeżeli punkty mają taką samą współrzędną x to rosnąco po współrzędnej y. Mając posortowane punkty wyznaczamy bok naszego kwadratu stosując dwie zagnieżdżone pętle tak jak to robiliśmy w poprzednich podejściach. Różnica w tym rozwiązaniu polega na tym, że wewnętrzną pętlę przerywamy w momencie, gdy trafimy na punkt o innej współrzędnej x niż współrzędna x punktu wybranego przez pętlę zewnętrzną. Pseudokod poniżej:

for i = 0 to n - 1 do
  for j = i + 1 to n - 1 do
    if P[j].x != P[i].x then
      break
    // Tutaj sprawdzamy czy istnieją pozostałe 2 punkty, które utworzą kwadrat

Takie podejście gwarantuje nam, że w najgorszym wypadku wykonamy 2001^2 * (n / 2001) operacji. Dla ułatwienia obliczeń załóżmy, że mamy po 2000 punktów w 500 kolumnach. Da to nam 2000^2 * (10^6 / 2000) = 2 * 10^9 operacji. Biorąc pod uwagę limit 4s i szybkość Cube’a (serwer sprawdzający SPOJa) jest to akceptowalna wartość. Pozostaje kwestia szybkiego sprawdzenia czy istnieją pozostałe 2 punkty, które mają utworzyć kwadrat z naszym bokiem. Znowu korzystając z tego, że powierzchnia jest mała możemy to zrobić w czasie stałym. W tym celu tworzymy sobie tablicę o rozmiarach 2001 na 2001 elementów i zapisujemy wartość true w komórkach, w których są punkty. Oczywiście współrzędne punktów musimy zamienić na nieujemne dodając 1000 do każdej z nich.

Takie rozwiązanie gwarantowało AC.

Z tego co widzę w Twoim ostatnim zgłoszeniu to nie porządkujesz punktów wg. współrzędnych tylko dla każdego punktu starasz się odpowiednio przechodzić tablicę z punktami. Obawiam się, że przy takim podejściu problemem wydajnościowym może być to, że za dużo “skaczesz” po pamięci, ale nie mam 100% pewności bo to była taka 2 minutowa analiza Twojego rozwiązania Jak jesteś zainteresowany to wklejam link do mojego rozwiązania: https://ideone.com/1OC2Vh23

Masz błąd na tym samym teście, na którym wywalała się większość rozwiązań. Jego uproszczona wersja wygląda tak:
50117
Odpowiedzią jest 5, Twój program zwraca 6. Co ciekawe dla 5017 odpowiedź masz prawidłową. Rzeczywisty test w zadaniu prezentuje się następująco:
5013611499391318666414491496888118839396836143811634996198389384634133991634493896963181689646319187
Odpowiedzią jest 100, Twój program zwraca 196.

Uwaga! Poniższe rozwiązanie jest niepoprawne ponieważ Mariusz zmodyfikował zadanie po moich testach. Dzisiaj wrzucę poprawione omówienie. Przepraszam za wprowadzenie w błąd.

W tym zadaniu naszym celem jest stwierdzenie czy istnieje spójny niepusty podciąg trasy Jasia, który utworzy pętlę.

Pierwsze spostrzeżenie jest takie, że trasa jaką pokonał Jasiu jest krótka i zawiera co najwyżej 100 znaków, a zatem spokojnie możemy zbadać wszystkie możliwe podciągi.

Przejdźmy zatem do weryfikacji czy dany podciąg jest poprawną pętlą (łamaną). Sprawdźmy definicję łamanej.

Łamaną nazywamy figurę geometryczną, która jest sumą skończonej liczby odcinków takich, że każde dwa kolejne mają wspólny koniec oraz:

• każde dwa kolejne odcinki i tylko dwa kolejne odcinki mają wspólny koniec,
• żadne dwa następujące po sobie odcinki nie są zawarte w jednej prostej.

Zgodnie z treścią zadania nasz bohater może na trasie wykonywać skręty o 90 lub 180 stopni. Jednak jak widzimy w definicji łamanej nawroty (skręty o 180 stopni) spowodują, że dana figura nie będzie już łamaną ponieważ 2 następujące po sobie odcinki będą zawarte w jednej prostej. I to jest główny haczyk w tym zadaniu. W związku z powyższym pierwszym etapem jest sprawdzenie czy w wybranym podciągu trasy występują nawroty czyli: NS, SN, WE lub EW. Jeżeli występują to dany podciąg nie będzie poprawną pętlą.

Jeżeli nawroty nie występują to pozostało nam sprawdzić czy po przejściu całego podciągu wróciliśmy do punktu, z którym się zaczynał. Można to zrobić np. zliczając liczbę wystąpień liter N, S, E, W. Jeżeli N = S i E = W tzn. że wróciliśmy do punktu wyjścia, a co za tym idzie znaleźliśmy poprawną pętlę.

Wybranie podciągu do sprawdzenia ma złożoność O(n^2), sprawdzenie tego podciągu O(n), a zatem całość ma złożoność O(n^3) co przy maksymalnej wartości n = 100 jest w zupełności wystarczające.

Oczywiście, że można. Możemy założyć sobie, że startujemy z punktu 100,100 i generować kolejne współrzędne. Wchodząc na dany punkt sprawdzamy czy byliśmy na nim wcześniej (co możemy odczytać właśnie z tablicy 2 wymiarowej) i jednocześnie sprawdzamy czy to nie jest nawrót itd.

Jednak specjalnie opisałem wolniejsze rozwiązanie, żeby uczyć ludzi, że nie ma sensu wytaczać armaty na muchy jeżeli zadanie tego nie wymaga. Ostatecznie drugim kryterium po liczbie rozwiązanych zadań jest czas ich rozwiązania.

Julia, testowałem Twoje ostatnie zgłoszenie i np. dla takiego testu:

1
NSEESSWWNNS

Twój program zwraca NIE, a powinien TAK, bo mamy pętlę EESSWWNN począwszy od 3 znaku.