Jul 2017
3 / 3
Jul 2017
Jul 2017
avrilq
Jul '17

Link: http://pl.spoj.com/problems/AL_10_05/9
Mój kod: TLE (na razie nie umieszczam, chodzi o podejście do problemu :smiley: )

Problem: Szybkie znalezienie drogi pomiędzy wierzchołkami A i B o najniższej maksymalnej wysokości.
Vertices=5000
Edges=50000
Queries=10000

Sposób nr1: Mamy zapytania, więc czemu by nie wygenerować sobie tabelki szczytów pomiędzy wszystkimi wierzchołkami i z niej nie podawać odpowiedzi. Floyd-Warshall. O(V^3) TLE.

Sposób nr2: Q jest dosyć małe, więc czemu by nie odpowiadać na zapytania "w locie". Djikstra. O(VlogV+E)*Q TLE.

Sposób nr3: A można przecież wyznaczyć sobie najpierw tę tabelkę i odpowiadać w czasie stałym, gdyż Q>V. O(VlogV+E)*V TLE.

Sposób nr4: A jakby tak jeszcze zminimalizować liczbę wywołań tej Djikstry i wywoływać ją tylko dla tych wartości, które autentycznie pojawią się na wejściu. W zależności od testów, czasem zaoszczędzimy trochę czasu, a skoro graf jest nieskierowany to wystarczy wywoływać ją dla min(A,B) lub max(A,B). TLE.

Chętnie przyjmę jakieś wskazówki :slight_smile:

  • created

    Jul '17

  • last reply

    Jul '17
  • 2

    replies

  • 366

    views

  • 3

    users

  • 1

    like

  • 1

    link

mariusz193
Jul '17

zadanie robiłem dość dawno, i nie do końca rozumiem obecnie jak :slight_smile:

gdybym miał czas, to pewnie w końcu bym zrozumiał jak to zrobiłem, ale obecnie mogę jedynie powiedzieć, że w jakiś (obecnie dla mnie niejasny) sposób liczyłem całą tablicę połączeń, przerywając liczenie, gdy znalazłem połączenia dla wszystkich zapytań

trochę później wymyśliłem inny sposób rozwiązania zadania, bez korzystania z tabeli wszystkich połączeń, działający w czasie O((V + Q) * log (V) + E * log(E)), ze względu na dość złożony kod nie chciało mi się go zrealizować

sądząc po czasie rozwiązań i zużyciu pamięci rozwiązań, kilka osób taki/podobny algorytm zrealizowało

narbej
Jul '17
1

Q jest duże, a q małe :wink:
A tak serio w treści zadania nie widzę nic na temat wielkości q, ale jeżeli masz tle, to raczej preprocesing i przygotowanie odpowiedzi w tabeli [oczywiście 1/2 tabeli] [i ja tak mniej więcej mam]

Czy te algorytmy są tutaj dobre?
Nie chodzi o najkrótszą/najtańszą drogę/trasę.
Jeżeli między dwoma punktami jedna droga prowadzi przez szczyt o wys 100, a druga droga prowadzi przez x [tu wstaw dowolną wartość większą od 2] szczytów o wys 55, to odpowiedzią będzie 55 a nie 100.
Czy na pewno dobrze przemyślałeś zadanie? Dobrze jest narysować sobie odpowiedni rysunek.

PS
jednak jest
max q = 10000
Może to i nie jest dużo.