• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zrobienie optymalnego algorytmu, wyznaczającego bezpieczne pasma.

VPS Starter Arubacloud
0 głosów
144 wizyt
pytanie zadane 9 listopada 2020 w Algorytmy przez SmaczySchabowy Początkujący (270 p.)

Dzień dobry,

Chciałbym się spytać o radę, ponieważ nie mam pomysłu jak napisać optymalny program, który radziłby sobie z problemem poniżej.

Otóż, mamy tutaj obrazek, który pokazuje nam drogę do sejfu z lotu ptaka. Korytarz ma n metrów szerokości i m prętów(czyli te czarne linie) szerokość korytarza a także ilość prętów i ich współrzędne wczytujemy z pliku. I teraz co powinien robić algorytm, powinien wyznaczać tak jakby luki(bezpieczne pasma) pomiędzy prętami w taki sposób by dotrzeć do sejfu, na obrazku bezpieczne pasma są oznaczone na niebiesko. Do czego ja doszedłem to do tego, że oś x w tym zadaniu nie ma większego znaczenia raczej interesują nas y. Więc trzeba w jakiś sposób brać te y i robić z nich te bezpieczne przedziały, jednak nie mam zupełnie pojęcia jak te przedziały zrobić, jak optymalnie wykluczać te pręty, do tego algorytm powinien być szybki bo jego złożoność powinna być liniowa czyli Θ(m+n). Z chęcią przyjmę jakieś pomysły jak to zadanie zrobić. Z góry dziękuję za pomoc.

1 odpowiedź

0 głosów
odpowiedź 9 listopada 2020 przez Whistleroosh Maniak (56,980 p.)
wybrane 11 listopada 2020 przez SmaczySchabowy
 
Najlepsza
Masz rację, że oś X nie ma tu większego znaczenia. Można więc się jej pozbyć. W tym celu należy te wszystkie pręty rzutować na oś Y. Załóżmy, że potrafimy to zrobić. Wtedy wynikiem będą wszystkie przedziały na osi Y, które nie zostały pokryte przez żaden zrzutowany pręt.

Pojawia się tylko pytanie jak rzutować te pręty na oś Y. Powiedzmy, że masz pręt o współrzędnych jednego końca (x_1, y_1) i współrzędnych drugiego końca (x_2, y_2), dodatkowo powiedzmy, że y_1 <= y_2. Teraz wystarczy tak naprawdę oznaczyć na osi Y, że przedział [y_1, y_2] został pokryty przez jakiś pręt. Tę operację musimy powtórzyć dla wszystkich prętów.

Sama implementacja zależy trochę od ograniczenia na n. Możesz po prostu każdy pręt rozbić na dwa punkty o współrzędnych Y y_1 i y_2 i posortować. Albo jeżeli n jest mniejsze od miliona to możesz również rozbić pręt na dwa punkty, ale zamiast sortować, wystarczy że w tablicy (którą będziemy utożsamiać z osią Y) dodasz 1 do elementu pod indeksem y_1 i odejmiesz 1 od elementu pod indeksem y_2 i na tym policzysz sumę prefiskową.
komentarz 9 listopada 2020 przez SmaczySchabowy Początkujący (270 p.)
Nie do końca rozumiem tego pomysłu z tablicą, że do elementu pod y_1 dodajemy 1 i odejmujemy 1 od elementu pod indeksem y_2 i na tym liczymy sumę prefiskową. Przed chwilą sobie ją wygooglowałem czym ona jest bo akurat nigdy z niej nie korzystałem i nie rozumiem czemu liczyć sumę elementów tablicy dla [y_1, y_2] skoro nie wiemy co tam konkretnie jest w tym przedziale indeksów tablicy. Sam pomyślałem, tylko to jest tak średnio optymalne, aby dla wszystkich elementów przypisać wartość 0, i dla np. [ y_1, y_2] dla wszystkich elementów w przedziale przypisać wartość 1 albo dodać 1 do elementów, zrobić tak dla każdego pręta a potem sprawdzić, które elementy w tablicy są równe 0.
komentarz 9 listopada 2020 przez Whistleroosh Maniak (56,980 p.)
Sumy prefiksowe mają właśnie na celu zoptymalizowanie tego dodawania na przedziale [y_1, y_2]. Pokażę na przykładzie.

Powiedzmy, że masz sobie dwa pręty, jeden o współrzędnych [(1, 2), (5, 5)] i drugi [(2, 3), (4, 4)], gdzie pierwsza para w nawiasie kwadratowym to jeden koniec pręta, a druga para to drugi koniec pręta.

Nie interesują nas oczywiście współrzędne x, więc pozbywamy się ich. Zostaje nam [2, 5] i [3, 4].

Teraz mamy sobie jakąś tablicę wypełnioną zerami. Dodajmy zatem na pozycji 2 i 3 jeden, a także odejmujemy na pozycji 6 i 5 jeden (zauważ że w tym przypadku odejmuje 1 od pozycji y_2+1, anie y_2 jak mówiłem wcześniej. To tak naprawdę zależy od tego, czy luki mogą przechodzić przez krańce prętów, czy nie).

Dostajemy tablicę (indeksowaną od 1):

0, 1, 1, 0, -1, -1

Obliczmy sumę prefiskową i otrzymujemy:

0, 1, 2, 2, 1, 0

Ta tablica pokazuje, że punkt o współrzędnej Y 1 i 6 nie jest pokryty przez żaden pręt, punkt 2 i 5 pokryty jest przez jeden pręt, a punkt 3 i 4 pokryty jest przez 2 pręty. To wszystko działa liniowo, bo sumy prefiskowe liczymy dopiero, jak naniesiemy wszystkie +1 i -1.

Ten pierwszy pomysł na sortowanie o którym mówiłem działa tak samo jak to tutaj, tylko nie trzymamy bezpośrednio całej tablicy
komentarz 17 listopada 2020 przez SmaczySchabowy Początkujący (270 p.)
Dzięki Panu udało mi się zaliczyć zadanie na max punktów. Dziękuję za pomoc i pozdrawiam.
komentarz 18 listopada 2020 przez Whistleroosh Maniak (56,980 p.)
A dziękuję bardzo

Podobne pytania

0 głosów
1 odpowiedź 77 wizyt
pytanie zadane 17 listopada 2020 w Algorytmy przez SmaczySchabowy Początkujący (270 p.)
0 głosów
0 odpowiedzi 308 wizyt
pytanie zadane 3 sierpnia 2023 w Algorytmy przez Mariusz M Obywatel (1,670 p.)

92,845 zapytań

141,786 odpowiedzi

320,861 komentarzy

62,178 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Wprowadzenie do ITsec, tom 2

Można już zamawiać tom 2 książki "Wprowadzenie do bezpieczeństwa IT" - będzie to około 650 stron wiedzy o ITsec (17 rozdziałów, 14 autorów, kolorowy druk).

Planowana premiera: 30.09.2024, zaś planowana wysyłka nastąpi w drugim tygodniu października 2024.

Warto preorderować, tym bardziej, iż mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy dodatkowe 15% zniżki! Dziękujemy zaprzyjaźnionej ekipie Sekuraka za kod dla naszej Społeczności!

...