3x3 Subrectangles malowane siatki

Question

Ostatnio brałam udział w konkursie kodującej i nie mógł dowiedzieć się this question. Oświadczenie Problem jest następujący

Masz 10^9 * 10^9 siatkę białych komórek 10^5 z nich pomalowane na czarno. Dla każdej liczby całkowitej j z 0 do 9, wypisz liczbę podwzorów trójkątnych 3x3, które zawierają dokładnie czarne komórki o rozmiarze j. Limit czasu wynosi 3 sekundy, a limit pamięci to 256 MB.

miałem mgliste pojęcie, które brzmi mniej więcej tak: iterację czarnych komórek i zbadać komórki w prostokącie 5x5 skupione na swojej czarnej komórce, a następnie policzyć prostokąty 3x3 (które moim zdaniem byłoby rozwiązanie O(n) gdzie n to liczba czarnych komórek, ale nie jestem pewna, jak ją wdrożyć, ani jak poradzić sobie z podwójnym liczeniem.

Strona ma artykuł na to pytanie, ale jest w języku japońskim, a Google translate ma był bezużyteczny

Answer 1

Mój algorytm wygląda następująco:

Masz 2 uporządkowane zestawy, 1 dla punktów i 1 dla górnego lewego współrzędnego każdego subrectangle 3x3. Jest to na efektywne wyszukiwanie duplikatów i czarne komórki

1. Dla każdego czarne komórki sposób prostokąty 9 3x3 Jest w

2. Dla każdego 3x3 prostokąta sprawdzić, czy lewej górnej współrzędnych już jest zestaw

   2a. Jeśli tak, zignoruj ​​prostokąt 2b. Jeśli tak nie jest, policz liczbę czarnych komórek w prostokącie (sprawdzając, czy w każdej komórce znajduje się czarna komórka).

3. Wprowadź nową górną lewą współrzędną do zestawu i dodaj 1 do odpowiedniego licznika.

Aby obliczyć liczbę 3x3 prostokątów, które nie mają żadnych czarnych komórek, można wziąć (H-2)*(W-2) - number of rectangles with at least 1 black cell

Algorytm powinna podjąć kroki, ~O(Nlog(N)). Krok 1 zajmuje czas O(N), krok 2 zajmuje O(9*9*logN) = O(logN). Krok 3 zajmuje czas O(logN).