No dobra, niech będzie. Podokładam jeszcze jakieś lore momentami bonusowo. Wyjaśnienia posortowane po rosnącej trudności skojarzenia moim zdaniem.

Duży obrazek po lewej na górze to chyba najprostszy z całego zestawu legendarny Bilard Hilberta, który pojawił się także na najfajniejszej historycznie koszulce PA (najfajniejszej, bo on tam był). Zabawne były te długie godziny szukania bardzo dziwnych patternów, które pojawiają się dopiero od jakoś krzywej rzędu 5 czy 6 i wklepywania ich do kodu bez żadnego ogarniania czemu to ma mieć jakikolwiek sens. https://sio2.mimuw.edu.pl/c/pa-2016-1/p/hil/?fbclid=IwAR2AgHCouWXVqxsPHRqElcsA5Tg-zyPcnWz1dI6-PJ7anw9iIU1ymnStS4c

Duży obrazek po lewej na dole to oczywiście milusia geometria Gobeliny z pierwszego etapu OI, która mnie już szczęśliwie ominęła https://szkopul.edu.pl/problemset/problem/ET8hwff-zMJ9sm1GsnKlRl3i/site/?key=statement

Po prawej legendarny Pająk z PA 2012 6B. Można było albo zrobić tragicznie skomplikowanymi rekurencjami na setki linii, które jakoś wyznaczały ten cały obszar i i tak nie dostawały maxa albo w kilku linijkach ze wzoru Eulera https://szkopul.edu.pl/problemset/problem/X2yoqrLzTo4vhyt2gZncOIsx/site/?key=statement

Sześcianik w lewo-prawo-dół to nic innego jak Trzy Kule z PA 2019 5B https://szkopul.edu.pl/problemset/problem/FNaKWWH3aylkg-NAJxVxAHrC/site/?key=statement

Rodzinka słodziaśnych zwierzątek to oczywiście Wombats z niezbyt fajnego IOI 2013 (na którym wymagane było jakieś szastanie żyłowanymi na każdy możliwy sposób drzewami 2D i to chyba nawet w dwóch zadaniach jednego dnia?) https://oj.uz/problem/view/IOI13_wombats

Owy niepozorny domek to niepozorne E z ostatniego AMPPZ, które wygląda na prościutkie a jest tak naprawdę głębokim rabbit holem https://szkopul.edu.pl/problemset/problem/VQ4ZjNTsr4moTWAM2USatfjZ/site/?key=statement

Jenga z metalowych belek to zadanie, które nawet ja sam opracowywałem (albo weryfikowałem? not sure) i to był mój jedyny wkład w legendarny Pokemonowy contest autorstwa Radeusza i Soko z letniego Petro 2019. Szkoda tylko, że sprawdzaczka się nie polubiła z interaktywnym Cloysterem i w sporej części zepsuła wtedy owy contest https://codeforces.com/gym/102341/problem/G

Co do pozostałych zadanek to shoutout dla użytkownika _o którym nikt się nie dowie_, który to użytkownik zamiast robić 3B wolał szukać godzinami tych rysuneczków, aby wspólnymi siłami dojść do celu.

Urokliwa dżdżownica oczywiście pochodzi z Codeforces i jest ulubienicą naszego Szefa Potyczek i nawet pamiętałem jak wygląda reszta rysunku razem z podziemnym tunelem, ale jakoś nie byłem pewien jak ją dokładnie zlokalizować. Okazuje się to być to owe zadanie https://codeforces.com/contest/516/problem/D

No i final boss, czyli chłopczyk z monetą. Cluesy takie, że owa moneta to "5zł", więc musi to być polskie zadanie. No i po art stylu widać, że nie jest to żaden konkurs, który ma do siebie jakikolwiek szacunek, więc OI albo PA odpadają. Bardzo do takowego opisu pasuje jednak OIG, gdzie rzeczywiście owy rysunek znaleźć można w zadaniu Kieszonkowe. Samo zadanie jest swoją drogą raczej bardzo trudne (i bardzo fajne) jak na OIG i wypuszczono do niego omówienie, które prezentował śp. Błażej Magnowski. Potem identyczne zadanie pojawiło się na rundzie Codeforces https://codeforces.com/contest/436/problem/E, gdzie nie wiedząc jak je zrobić obejrzałem owe omówienie i udało mi się dzięki temu zająć całkiem przyzwoite 31 miejsce (tym bardziej biorąc pod uwagę, że byłem wtedy żółty). Nie jestem pewien skąd wiedziałem o tym połączeniu i chyba to było tak, że powiedział mi o tym Karol Kaszuba, z którym pisałem ten contest w jednym pokoju w trakcie obozu Mszany Dolnej xd https://szkopul.edu.pl/problemset/problem/PJA7VC3zOTwh1qPU43Wu9O4v/site/?key=statement

Dziękuję

Jak w temacie. Zapraszam do porównania.
https://easyupload.io/fbszdz

EDIT: Jeśli ktoś pobrał poprzednią paczkę przed 14:50, to może ją usunąć, bo podmieniłem teraz outy.

Potwierdzam

Można też w ogóle najpierw przeprowadzić pierwszy graf na gwiazdę bez dodatkowych krawędzi (czyli np. 1 połączone ze wszystkim i całą resztę usunąć), a potem tę gwiazdę na docelowy graf - być może trochę łatwiej o tym myśleć, bo graf "pośredni" zależy tylko od liczby wierzchołków, a maksymalna liczba kroków jest taka sama.

Ponadto pomocny do wykminienia/implementacji może okazać się fakt, że ruchy są swoimi wzajemnymi "odwrotnościami", więc przeprowadzenie grafu pośredniego na końcowy to to samo, co przeprowadzenie końcowego na pośredni, tylko "puszczone od tyłu" i z zamienionymi plusami-minusami.

Potwierdzam.

Potwierdzam

Taka jest idea uruchomienia próbnego. Różnice które opisujesz u siebie mogą wynikać np z różnych optymalicji kompilatora, spróbuj użyć dokładnej komendy podanej w ustaleniach technicznych i zobacz czy będzie dalej tak samo

Graf ma co najwyżej 30k wierzchołków / 50k krawędzi, co przy limicie 200k ruchów daje niezły zapas.
Żeby móc modyfikować krawędzie, potrzebujemy żeby istniał atom sąsiadujący z obydwoma jej końcami... To może utwórzmy atom, który sąsiaduje ze wszystkimi innymi?

Więc przyjmując że atom #1 to root:
1) odpalam BFS na pierwszym grafie, startując od roota i w tej kolejności dodaję połączenia do/z roota (jeśli nie istnieją);
2) dodaję w dowolnej kolejności pozostałe krawędzie, których brakuje (już mogę, bo wszystko jest połączone z rootem);
3) usuwam w dowolnej kolejności krawędzie nie prowadzące do/z roota;
4) odpalam BFS na docelowym grafie i w odwrotnej kolejności (od najdalszych wierzchołków) usuwam krawędzie do/z roota, których być nie powinno;

Maksymalne oszacowanie liczby ruchów to:
1) 30k operacji
2) 50k operacji
3) 50k operacji
4) 30k operacji
co spokojnie mieści się w limicie

Może i przekombinowane, ale wystarczyło na 10/10.

Czy ktoś podzieliłby się rozwiązaniem do ALC? Ja zrobiłem w O(nm), ale to starczyło tylko na 4/10. Pewnie mógłbym żyłować stałą, ale podejrzewam, że brakuje mi jakiejś ostatniej obserwacji. Robiłem tak:

1. Szukamy jakiegoś wspólnego nadgrafu danych grafów, rozwiązanie to będzie zbiór krawędzi dodanych do pierwszego grafu (A) z plusem, i zbiór krawędzi dodanych do drugiego grafu (B) z minusem, w odwrotnej kolejności.
2. Żeby znaleźć ten nadgraf, biorę krawędzie B - A, i dla każdego wierzchołka X odpalam bfs, szukając alternatywnej ścieżki do wierzchołków Y, takich, że X-Y jest w B - A. Kiedy znajdę taką ścieżkę X, x_1, ... x_k, Y, to mogę dodać połączenia X - x_2, X - x_3, ..., X - Y.
3. (B - A) + te ekstra krawędzie + ekstra krawędzie z procesu dla (A - B) to wszystkie krawędzie, które trzeba dodać.

Potwierdzam

Potwierdzam

Potwierdzam

Potwierdzam

Potwierdzam i wpycham się tutaj ze swoim pytaniem skoro poruszono temat czasów:

Czy wykonanie próbne jest uruchamiane i mierzone w taki sam sposób jak właściwe testy?

Mój komputer wykonuje testy do ALC 4x wolniej niż SIO2. Za to w ZEL jest 15x szybszy niż wykonanie próbne SIO2. Bardzo możliwe, że sam robię coś źle, tak tylko pytam czy to może jest w jakiś sposób spodziewane.