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.