Mój piękny brucik o(n^4), lecz z m.in. losowaniem i konczeniem wczesniej, wchodzi na (aż) 10pkt. Końcowo o(n^3logn)

miałam identyczną wątpliwość co Mikołaj, w teście nr 3 szkoła nie należy do żadnego z przedziałów, a powinna

Potwierdzam

Potwierdzam wszystko.

Rzucę tylko, że można przekazać 1.5% podatku na Fundację Rozwoju Informatyki podając numer KRS: 0000025627. Można nawet wpisać, że to na sprawdzaczki na Potyczki.

O(n^3 log n / 64)

Porównując wyniki w uruchomień próbnych dla bruta do EGZ sprawdzarka była x60 wolniejsza niż budżetowy laptop. 2.4s vs 0.04s.
Sporo:)

Potwierdzam

Potwierdzam

Może lepiej byłoby poprosić o obliczenie średnicy dla każdej pary. Mam rozwiązanie w O(n^3) (które działa wolniej niż O(n^3 * log(n)) xd)

https://easyupload.io/efrfcb

wszystkie testy powstały poprzez wylosowanie prawidłowej wyliczanki, a potem w połowie do losowej wartości zostało dodane 1. We wszystkich testach zachodzi t=1, n=1e6.

Ja też mam 10 za rozwiązanie O(n^4) (max czas 1s), które dla każdego teleporta iteruje się po wszystkich parach wierzchołków, posortowanych malejąco po ich odległości i robi brake gdy tylko można już określić średnicę - ten opt w pojedynkę wystarczał. Mam test* który na uruchomieniu próbnym działa w >3s, i dlatego koniec końców wysłałem O(n^4/w) na bitsetach. Chodzi w 0.3s, mimo że na uruchomieniu próbnym na cyklu długości 399 chodzi ponad 1s.

*krzyż gdzie każde ramie ma n/6 wierzchołków + do dwóch ramion doczepione po n/6 wierzchołków

Jeżeli n^4 log n / 64 wchodziło to kiepsko ze strony opracowujących
Napomknę, że z teoretycznego punktu widzenia ta złożoność to dokładnie to samo co O(n^4), czyli najgorszy brut. W praktyce nie powinny być zbyt odległe też
O(n^4) "z innymi optymalizacjamo" na 10 pkt też mnie niezbyt cieszy
Ale no trudne zadanie do układania testów. Przez swoje n godzin rozkminy wymyśliłem dużo hereł czasowych i myślałem że opracowujący mieliby trudne zadanie je powycinać. Widzę, że się sprawdziło xd

Przede wszystkim na samym początku obliczamy w O(n^3) odległości między wszystkimi parami wierzchołków.

Teraz iterujemy się po możliwych parach miejsc na teleporty i utrzymujemy globalną zmienną na wynik (na początku n). Będziemy potrzebować funkcji check(a, b, x), która sprawdza, czy gdy w wierzchołkach a oraz b damy teleporty, to wynik będzie <=x. Iterując się po tych parach zawsze próbujemy odpalać check(a, b, wynik-1) i dopóki da się go zmniejszyć to zmniejaszamy. W ten sposób funkcję check() odpalimy O(n^2) razy.

Pytanie jak powinna działać nasza funkcja check(a, b, x). Iterujemy się po v i bez straty ogólności zakładamy, że v ma bliżej do a niż do b. To co chcemy sprawdzić, to czy wszystkie wierzchołki odległe od v o ponad x są odległe od b o co najwyżej x-odl(v, a) (ponieważ to do tych wierzchołków musielibyśmy dojść teleportując się z a do b). Tutaj możemy skorzystać z tego, że zapytania zadajemy w kolejności malejącej po x i utrzymywać tablicę najdalszy[v][b], która spośród wszystkich wierzchołków u takich, że odl(v, u)>x, pamięta największą odległość od b do któregokolwiek z nich. Za każdym razem gdy dla x musimy wrzucić do struktury jakąś parę (v, u), to po prostu iterujemy się po b i maxujemy najdalszy[v][b] z odl(b, u). Funkcja check(a, b, x) będzie liniowa, sumaryczna aktualizacja najdalszy[v][b] zajmie O(n^3) i całość również zamknie się w O(n^3).

Ja mam O(n^4) bez "/64" ale z innymi optymalizacjami.