Zadanie OIG - Kafelki

Question

Hej!

Rozwiązywałem ostatnio zadanie pt. Kafelki z ubiegłorocznej edycji Olimpiady informatycznej gimnazjalistów

Treść zadania:

Piotrek jest nowym administratorem systemu Olimpiady Informatycznej 
Gimnazjalistów. Jednym z jego obo- wiązków jest opieka nad serwerownią. 
Pomieszczenie musi spełnić szereg kryteriów zarówno technicznych, jak i 
estetycznych. Aby zapewnić poprawne działanie serwerów, ważne jest, aby podłoga 
została pokryta no- woczesnymi kafelkami chłodzącymi.
Piotrek może wybrać jeden z n rodzajów kwadratowych kafelków. Zakładamy, że 
kafelków danego rodza- ju można kupić dowolnie wiele, ale nie wolno w jakikolwiek 
sposób zmieniać ich wymiarów. Piotrek musi rozpatrzyć wszystkie rodzaje kafelków, 
którymi da się całkowicie wyłożyć podłogę i zdecydować, które kupi. Niestety, 
nigdy nie był w serwerowni, i nie wie, jakie ma ona wymiary. Pomóż młodemu 
administratorowi i napisz program, który dla zadanych wymiarów podłogi w 
serwerowni wyliczy, ile różnych rodzajów kafelków może użyć.

 

Wejście:

W pierwszym wierszu standardowego wejścia zapisano dwie liczby naturalne n i m 
(1 <= n, m <= 200 000), oznaczające odpowiednio liczbę rodzajów kafelków i liczbę 
zapytań o wymiary serwerowni. W drugim wierszu zapisano n liczb naturalnych xi 
(1 <= xi <= 106), oznaczających długość boku i-tego rodzaju kafelków. 
W ko-lejnych m wierszach zapisano po jednej parze liczb naturalnych ai, bi (1 <= ai, bi <= 106),
oznaczających zadane wymiary. W testach wartych 50% punktów możesz założyć,
 że podłoga serwerowni jest zawsze kwadratem (ai = bi).

Wyjście:

W i-tym wierszu wyjścia powinna znaleźć się jedna liczba naturalna, oznaczająca 
liczbę różnych rodzajów kafelków, którymi można wyłożyć podłogę o wymiarach 
zadanych w i-tym zapytaniu.

Najprostsze rozwiązanie problemu to po prostu sprawdzenie czy dany rozmiar pokoju jest podziely bez reszty przez i-ty kafelek, ale będzie to rozwiązanie o złożoności m * n => ok. O(n^2), więc w tego typu konkursie nie byłoby to zbyt wysoko punktowane.

Wymyśliłem, że można by to zoptymalizować w taki sposób, że tablicę z wartościami kafelków sortujemy rosnąco quicksortem, i sprawdzamy czy NWD wymiarów pokoju jest podzielny przez i-ty kafelek iterując do czasu aż i-ty kafelek jest mniejszy bądź równy NWD wymiarów pokoju. Jest jednak pewien problem. Mianowicie przy najbardiej pesymistycznym założeniu (czyli takim, że wszystkie kafelki będą mniejsze od NWD każdego pokoju) ten algorytm będzie jeszcze mniej wydajny niż najprostszy o którym wspomniałem wyżej.

Moje pytanie jest następujące - czy w takim przypadku warto "zaryzykować", że zestawy danych będą w miarę optymistyczne i algorytm będzie działał znacząco szybciej niż O(n^2)? Dzięki za pomoc ;)

Comments

O(n2) to kiepska zlozonosc na olimpiadzie gimnazjalnej :D?

Answer 1

Witaj,

Moim zdaniem opisywane przez ciebie rozwiązanie nie zdobyłoby dużo więcej punktów niż rozwiązanie siłowe. Nie liczyłbym na przychylność testów. Oczywiście można spróbować je zoptymalizować, stosując różnego rodzaju heurystyki. Ja rozwiązywałbym to zadanie następująco:

1. Zliczyć wystąpienia rozmiarów kafelków

2. Wykorzystaj pomysł z sitem Eratostenesa tzn. dla wszystkich możliwych wymiarów serwerowni, sprawdź ile spośród rozmiarów kafelków je dzieli

3. Na zapytania odpowiadaj za pomocą algorytmu Euklidesa, odwołuje się do odpowiednich komórek tablicy

Jeżeli chodzi o pytanie czy warto ryzykować? Twoje rozwiązanie działa w pesymistycznej złożoności O(n*m*log(k)), gdzie k to maksymalny wymiar serwerowni. Nie jest to dużo wolniej od O(n*m), więc uważam, iż warto zaryzykować.

Pozdrawiam