English
Ostatnie posty
I w ten sposób rozpatrzy tylko ścieżki gdzie najpierw idziemy krawędziami B, a potem krawędziami A, wszystkie ścieżki gdzie robimy odwrotnie lub jedziemy na zmianę ileś razy pominiemy. Jeśli to weszło na jakoś dużo punktów to przepraszamy
B robi Dijkstrę i wysyła 1999 * 21 = 41979 bitów. A dodaje to i robi Dijkstrę.
a, sorki, tak, przy 2-giej wymianie jak bedzie neg ze strony B to wyjdzie 14
Nie jestem pewien jak to zrobić bez wysyłania ostatniego bitu tak jak mówisz, ale istotnie - chciałem by A wysłał najpierw 4, potem 3, a potem 2 bity i po każdej części czekał od B albo na „ok, kontynuuj” albo na „moja wartość jest większa, powtórzę Ci ten ostatni kawałek”, co da 14 bitów na ustalenie maksimum oraz kto je ma (tu zwrócę uwagę, że jeśli to wysyłający (A) ma maksimum, to B nigdy mu nie przerwie i wystarczy 12 bitów, czyli średnio potrzeba 13, więc randomizowanie można mieć 26000 na tę część.
Druga deterministyczna optymalizacja to lepsze wysyłanie numeru miasta - gdy zostanie ich <= 1024, to wystarczy już 10 bitów, gdy <= 512 to 9 itd, co pozwala zbić z 11 do średnio 10 bitów na miasto, więc nawet w 46000 można się zmieścić.
Jak już dłubiemy, to wydaje mi się, że deterministycznie da się nawet do 44000 dojechać nawet , ale tu już ktoś musiał by potwierdzić.
Druga deterministyczna optymalizacja to lepsze wysyłanie numeru miasta - gdy zostanie ich <= 1024, to wystarczy już 10 bitów, gdy <= 512 to 9 itd, co pozwala zbić z 11 do średnio 10 bitów na miasto, więc nawet w 46000 można się zmieścić.
Jak już dłubiemy, to wydaje mi się, że deterministycznie da się nawet do 44000 dojechać nawet , ale tu już ktoś musiał by potwierdzić.
A wysyła 3 bity -> B potwierdza/zaprzecza, potem znowu, na końcu 2 - razem da to 13 bitów dla określenia odległości (ostatniego bitu B nie wysyła bo oboje juz wiedza kto ma wysłać miasto)
Można jeszcze deterministycznie przyciąć poniżej - pytanko jak? :)
Można jeszcze deterministycznie przyciąć poniżej - pytanko jak? :)
Na rundzie próbnej wybaczamy, ale przypominamy, że na zawodach właściwych korzystanie z narzędzi generatywnej sztucznej inteligencji takich jak Claude jest zabronione pod groźbą dyskwalifikacji.
Fajne, chyba w takim razie mogę poprawić ćwiczonko i zaproponować deterministyczne 48000?
To zadanie wyłożyło Claude Code. Widać, że jeszcze troszkę brakuje, ale obawiam się, że niewiele. A może wystarczyłoby go trochę bardziej challengować, żeby szukał innych podejść...
❯ why didn't you come to this solution before on your own?
⏺ Honestly, a few reasons:
1. Wrong framing — I kept thinking "how do I share edges?" instead of "how do I share Dijkstra state?" All my approaches (SPT, spanning forest, distance arrays) were about transmitting graph structure, not about running Dijkstra jointly.
2. Fixated on priority queue Dijkstra — The O(n²) version has a crucial property that the priority queue version hides: at each step you explicitly find a single global minimum. That naturally maps to "both programs find their local
minimum, compare, pick winner." With a heap you don't have a single "compare and pick" moment.
3. Missed the delta encoding insight — Even if I had thought of joint Dijkstra, I would have worried about sending distances (20 bits each). The key observation — that consecutive finalized distances differ by at most max(C)=500, so a
9-bit delta suffices — I simply didn't see. The 58,000 = 2000×29 = N×(11+9+9) hint in hindsight makes it obvious, but I didn't work backward from the bit budget to the algorithm structure.
4. Underestimated O(n²) Dijkstra — I never seriously considered it because in competitive programming the heap version is almost always used. But here the O(n²) structure is the point.
Essentially I was solving "how to compress and transmit graph data" when the real problem was "how to run one distributed algorithm." Once you see it that way, the solution is almost forced.
❯ why didn't you come to this solution before on your own?
⏺ Honestly, a few reasons:
1. Wrong framing — I kept thinking "how do I share edges?" instead of "how do I share Dijkstra state?" All my approaches (SPT, spanning forest, distance arrays) were about transmitting graph structure, not about running Dijkstra jointly.
2. Fixated on priority queue Dijkstra — The O(n²) version has a crucial property that the priority queue version hides: at each step you explicitly find a single global minimum. That naturally maps to "both programs find their local
minimum, compare, pick winner." With a heap you don't have a single "compare and pick" moment.
3. Missed the delta encoding insight — Even if I had thought of joint Dijkstra, I would have worried about sending distances (20 bits each). The key observation — that consecutive finalized distances differ by at most max(C)=500, so a
9-bit delta suffices — I simply didn't see. The 58,000 = 2000×29 = N×(11+9+9) hint in hindsight makes it obvious, but I didn't work backward from the bit budget to the algorithm structure.
4. Underestimated O(n²) Dijkstra — I never seriously considered it because in competitive programming the heap version is almost always used. But here the O(n²) structure is the point.
Essentially I was solving "how to compress and transmit graph data" when the real problem was "how to run one distributed algorithm." Once you see it that way, the solution is almost forced.
Randomizowane 51000
Rozwiązanie podobne do poprzedniego posta, z nieco innym schematem komunikacji. Jedna ze stron (X) podaje informację "mam kandydata w odległości s". Na co druga może odpowiedzieć:
a) (Y) "nie mam bliższego kandydata", na co odpowiada (X) "id kandydata w odległości s" (łącznie 9+1+11=21 bitów)
b) (Y) "mam bliższego kandydata id w odległości t" (łącznie 9+1+11+9=30 bitów)
Jeśli wybór stron X/Y będzie losowy, to spodziewamy się użyć średnio 2000*(21+30)/2=51000 bitów. Obie strony A/B muszą wiedzieć którą pełnią rolę w każdej iteracji, najłatwiej zainicjalizować generator liczb losowych tym samym, wcześniem ustalonym seedem po obu stronach A/B i na jego podstawie wybierać stronę.
Rozwiązanie podobne do poprzedniego posta, z nieco innym schematem komunikacji. Jedna ze stron (X) podaje informację "mam kandydata w odległości s". Na co druga może odpowiedzieć:
a) (Y) "nie mam bliższego kandydata", na co odpowiada (X) "id kandydata w odległości s" (łącznie 9+1+11=21 bitów)
b) (Y) "mam bliższego kandydata id w odległości t" (łącznie 9+1+11+9=30 bitów)
Jeśli wybór stron X/Y będzie losowy, to spodziewamy się użyć średnio 2000*(21+30)/2=51000 bitów. Obie strony A/B muszą wiedzieć którą pełnią rolę w każdej iteracji, najłatwiej zainicjalizować generator liczb losowych tym samym, wcześniem ustalonym seedem po obu stronach A/B i na jego podstawie wybierać stronę.
Ja użyłem algorytmu Dijkstry, opisanego między innymi tutaj: https://www.cs.yale.edu/homes/lans/readings/routing/dijkstra-routing-1959.pdf
Z mniej ważnych uwag pobocznych: nie używamy kolejki priorytetowej (czyli opcji (O(m*log(m))) tylko wersji bez (czyli opcji O(n^2+m)). Oba programy utrzymują odległości do wszystkich wierzchołków do których te odległości już znamy. N razy musimy więc wybrać nowy wierzchołek, dla którego uznamy, że potencjalna odległość do niego jest tą poprawną i ją zaakceptować. Oba programy wysyłają więc do siebie nawzajem informację „znam minimalnego kandydata, do którego potencjalna odległość wynosi x” (literek wysyłać nie trzeba). Oba programy znając obu kandydatów stwierdzają niezależnie (ale tak samo) czyjego kandydata biorą i ten program wysyła do drugiego programu informację „ok, to ten kandydat miał numer v” (tu też nie trzeba literek).
Na przesłanie numeru kandydata potrzebujemy log(N)=11 bitów, zaś na przesłanie (w jedną stronę) potencjalnej odległości możemy skorzystać z obserwacji, że odległość ta wzrosła o co najwyżej max(C) względem poprzedniej maksymalnej odległości, wystarczy zatem log(max(C))=9 bitów. Czyli na jedną turę komunikacji (a jest ich N) wysyłamy 11+2*9=29 bitów, co podejrzanie daje dokładne 58000.
Ćwiczonko: zejść poniżej 56000.
Z mniej ważnych uwag pobocznych: nie używamy kolejki priorytetowej (czyli opcji (O(m*log(m))) tylko wersji bez (czyli opcji O(n^2+m)). Oba programy utrzymują odległości do wszystkich wierzchołków do których te odległości już znamy. N razy musimy więc wybrać nowy wierzchołek, dla którego uznamy, że potencjalna odległość do niego jest tą poprawną i ją zaakceptować. Oba programy wysyłają więc do siebie nawzajem informację „znam minimalnego kandydata, do którego potencjalna odległość wynosi x” (literek wysyłać nie trzeba). Oba programy znając obu kandydatów stwierdzają niezależnie (ale tak samo) czyjego kandydata biorą i ten program wysyła do drugiego programu informację „ok, to ten kandydat miał numer v” (tu też nie trzeba literek).
Na przesłanie numeru kandydata potrzebujemy log(N)=11 bitów, zaś na przesłanie (w jedną stronę) potencjalnej odległości możemy skorzystać z obserwacji, że odległość ta wzrosła o co najwyżej max(C) względem poprzedniej maksymalnej odległości, wystarczy zatem log(max(C))=9 bitów. Czyli na jedną turę komunikacji (a jest ich N) wysyłamy 11+2*9=29 bitów, co podejrzanie daje dokładne 58000.
Ćwiczonko: zejść poniżej 56000.
Czy ktoś, kto zdobył komplet punktów mógłby wyjaśnić, jak należało rozwiązać to zadanie?
Z góry dziękuję!
https://sio2.mimuw.edu.pl/c/pa-2026-1/p/tra/
Z góry dziękuję!
https://sio2.mimuw.edu.pl/c/pa-2026-1/p/tra/
Dzięki!
Nie ma krawędzi 7 4. Pierwsza linia testu to N A B
Witam,
Dlaczego w teście B:
7 4 2
3 4 171
1 7 192
2 3 269
3 5 236
3 6 318
4 1 240
0 680 411 240 647 729 192
Wynikiem dla 1 - 2 nie jest:
1 - 7 - 4 - 3 - 2, czyli 192 + 2 + 171 + 269 = 634
tylko poprawnym wynikiem jest:
1 - 4 - 3 - 2, czyli 240 + 171 + 269 = 680
Mógłbym prosić o informację?
Pozdrawiam
Dlaczego w teście B:
7 4 2
3 4 171
1 7 192
2 3 269
3 5 236
3 6 318
4 1 240
0 680 411 240 647 729 192
Wynikiem dla 1 - 2 nie jest:
1 - 7 - 4 - 3 - 2, czyli 192 + 2 + 171 + 269 = 634
tylko poprawnym wynikiem jest:
1 - 4 - 3 - 2, czyli 240 + 171 + 269 = 680
Mógłbym prosić o informację?
Pozdrawiam