Potwierdzam!

20 testów z n = q = 1e5, ceny bananów i przejazdu <= 1e9
https://drive.google.com/open?id=11GzDK2hIS6uGRutIQtJRHnp7iHPwcPLp

No tak, są sklejone, rzeczywiście

Moja druga część algorytmu wygląda mnie więcej tak:
- jest procedura dfs (v):
dla każdej krawędzi u -> v:
---- wyślij wiadomość z jednym zerem do u
---- poczekaj na dane zwrócone przez u i dopisz je do swoich informacji (te dane to: numery wierzchołków z których pochodzą i wartości akcji firm)
- wszystkie wierzchołki poza 0 (który jest na początku korzeniem) nasłuchują, nasłuchiwanie polega na tym, że jeśli odbierzemy wiadomość od kogoś to:
a) jeśli wiadomość nie pochodzi od kogoś, do kogo mamy krawędź lub pochodzi od kogoś, kto już nam wysyłał takiego requesta, to przełączamy się w tryb korzenia, w przeciwnym wypadku:
b) jesli nie robiliśmy dfsa to robimy
c) jeśli nie wysyłaliśmy nikomu naszych informacji to wysyłamy
jeśli wysyłaliśmy to wysyłamy -1 albo coś w tym stylu
- można zauważyć, że jeśli w grafie jest cykl to może się zrobić deadlock, więc tak naprawdę, kiedy jest ta linijka "poczekaj na dane zwrócone...", to trzeba wtedy nasłuchiwać od wszystkich i jeśli dostaniemy wiadomość "0" to od razu odpowiadamy "-1"
- wierzchołek 0 jest na początku korzeniem, czyli robi następujące rzeczy:
a) odpala dfsa
b) sprawdza, czy posiada informacje od wszystkich. Jeśli tak, to udziela odpowiedzi
c) w przeciwnym wypadku wysyła wiadomość do wierzchołka o kolejnym numerze - teraz on się staje korzeniem

Na koniec trzeba zadbać, żeby wszystkie wierzchołki wyszły ze stanu nasłuchiwania - to już są jakieś szczegóły z wykorzystaniem wierzchołka 0, któremu trzeba zgłosić, że się znalazło odpowiedź, a potem on wysyła wiadomość o zakończeniu do n - 1, ten wysyła do n - 2 itd.

Tak jak ja to napisałem, wysyłanych jest O(liczba krawędzi) wiadomości, jedna po drugiej, co może być trochę słabe (ale raczej nie jest jedynym powodem TLE na SIO, bo w trzecim teście i tak jest tylko 99 krawędzi). Da się jednak zrównoleglić tego dfsa, tak że najpierw wysyłamy wszystkie wiadomości z prośbą o dane, a potem nasłuchujemy na wszystkie odpowiedzi

jeśli dobrze rozumiem, to u Ciebie przedziały sąsiadujące są sklejone w secie, i w ten sposób masz w secie tyle elementów, ile dziur, a ja mam tyle, ile kwadratów, i pewnie to przesądziło.
dzięki za wyjaśnienie

Soga, thanks a lot :)

Bardzo nietypowe i bardzo ciekawe, przyłączam się do gratulacji. (też nie wiem jak je zrobić :P)

> Maciek, nie próbujesz każdej z NODES^2 krawędzi? DFS-y rzeczywiście odwiedzą O(NODES) wierzchołków, ale problemem jest być może liczba wiadomości, które zgaduję że są wolne. Czyli liczba próbowanych krawędzi. Czy może od razu szybko znajdujesz postać drzewa i tylko O(NODES) krawędzi dotkniesz?

W DFSie na pełnym grafie wszystkie krawędzie będą odwiedzone. Ale jest trochę równoległe :) W pierwszym "takcie" wiadomości rozsyła korzeń, w drugim wierzchołki odległe o 1, itd. Także wszystkie wierzchołki zostaną odwiedzone po co najwyżej N taktach, a ich odpowiedzi wrócą do korzenia po co najwyżej N kolejnych.

No chyba że wiadomości wysyłane z jednego węzła do różnych innych węzłów też się nawzajem istotnie blokują? Mam nadzieję, ze nie, ale i tak nie przychodzi mi do głowy scenariusz, w którym kwadraciło by to czas oczekiwania.

Zgadzam się. Mój kandydat na zadanie roku 2017 =)

Maciek - no jeśli tak to pewnie skminiłeś wzorcówkę i gratki.

Jarek - opisałem to samo z (a, b, c) ;p

Nie uważam, by potem było z górki. Możesz dokładniej opisać co potem robisz?

Też miałem TLE na ostatnim, mimo że na kompie działa szybko. Być może dlatego, że wiadomości się wolniej przesyłają.

EDIT: chwila moment. Maciek, nie próbujesz każdej z NODES^2 krawędzi? DFS-y rzeczywiście odwiedzą O(NODES) wierzchołków, ale problemem jest być może liczba wiadomości, które zgaduję że są wolne. Czyli liczba próbowanych krawędzi. Czy może od razu szybko znajdujesz postać drzewa i tylko O(NODES) krawędzi dotkniesz?

Ja chyba znalazłem sposób, żeby bez żadnych hacków z czasem przesłać informację o tym, kto do kogo może wysyłać normalnie wiadomości. Załóżmy, że wierzchołek a chce powiedzieć wierzchołkowi b, czy z b istnieje krawędź do a. Będzie potrzebny jeszcze do pomocy jakiś inny wierzchołek c. Wtedy na początku b i c nasłuchują (Receive(-1)), natomiast a wysyła wiadomość do b jeśli ta krawędź istnieje lub do c jeśli nie istnieje. Jeden z wierzchołków b, c odbierze teraz wiadomość i przekaże ją do drugiego z nich. W ten sposób b na pewno dostanie jedną wiadomość i w zależności od nadawcy, może się dowiedzieć, czy ma krawędź do a czy nie.

Da się to uogólnić tak, żeby a mógł każdemu innemu wierzchołkowi (poza wierzchołkiem pomocniczym, ale go da sie łatwo ogarnąć na koniec) wysłać jakąś zero-jedynkową wiadomość w jednym przebiegu (nie będę wchodził w szczegóły, da się to łatwo wykminić). Potem każdy wierzchołek musi wysłać wierzchołkowi a info, że już odebrał to co miał odebrać. Jak wierzchołek a od każdego odbierze taki sygnał to wysyła info kolejnemu wierzchołkowi, że teraz jego kolej na wysyłanie informacji o wchodzących do niego krawędziach itd.

Potem już jest z górki, ja tam robię takiego jakby DFSa po odwróconych krawędziach (każdy pełną informację o firmach przesyła tylko jednemu gościowi - swojemu ojcu w drzewie DFS).

Złożoność to jakieś N * całkowita liczba firm, ale z jakiegoś powodu na sprawdzaczce mam TLE na ostatnim teście, chociaż u mnie na kompie działa w sekundę i wysyłam wiadomości mniejsze niż 64kb. Miał ktoś jeszcze problem ze sprawdzaczką?

EDIT: widzę, że Kamil napisał przede mną prawie to samo :/

Wydaje mi sie, że tam nie ma O(NODES^2).

Dla ustalonego korzenia dwie długie operacje (DFS osiągalności i poszukiwania nowego korzenia) przejdą w czasie liniowym względem wielkości tego drzewa. ALE: po zmianie korzenia na nowy, stare drzewo nie będzie już w nich uczestniczyć:
1. DFSa na starym korzeniu nie wywołujemy drugi raz, bo mamy informację w tokenie o osiągalności z niego
2. zapytanie o ścieżkę do kolejnego korzenia też nie dojdzie do starego drzewa - z definicji nowy korzeń nie jest w stanie do niego dojść krawędziami wychodzącymi.

Mnie też się bardzo podobało. I dalej się podoba, mimo że wciąż nie umiem go zrobić.

Propsy dla autora. Jedno z najlepszych zadań, jakie kiedykolwiek robiłem.

No dobra, może nie od razu jak wiem, w sumie robię podobnie tylko najpierw dla każdego punktu wyznaczam sobie jego maksymalny bok jaki może mieć, żeby się z niczym nie przecinał. Oczywiście też jak widzę jakieś miejsce, gdzie poniżej musi być punkt, a go nie ma to kończę. Dodatkowo, nie wiem czy to coś zmienia, ale nie patrzę na pola, tylko trzymam sobie na secie dolny kontur tego co ułożyłem i na końcu na secie musi być tylko jeden przedział, żeby działało. Plus biorę na kandydatów minimum z liczby różnych iksów i igreków na wejściu. Jakieś takie opty...