Ostatnie posty:

Temat Uruchomienie próbne #76596 | jiuer7845 jiuer7845 | Dodany: 2022-10-08 06:22:41

Świetny konkurs! Czekam z niecierpliwością na oficjalne omówienia zadań i aż będzie można je dobijać na Szkopule!

Temat PA 2019 #6466 | Kamil Niziński | Dodany: 2019-12-23 14:24:33

Również składam wielkie podziękowania! :) Przygotowanie prostych zawodów już wymaga dużo roboty, a wymyślenie zadań na tak wysokim poziomie i opracowanie ich na tak wysokim poziomie jest już naprawdę ogromnym wysiłkiem :) Ale mam nadzieję, że mieliście z tego co najmniej tyle frajdy, co ja z pisania rozwiązań ;)

Jeśli chodzi o trudność zadań, to rzeczywiście była ona wyższa niż w poprzednich latach. Jeśli chodzi o zadania A, to uważam to za plus, w końcu po to ona jest, żeby była trudna. Jeśli chodzi o zadania B, które też były trudniejsze niż w poprzednich latach, to mi osobiście to nie przeszkadzało, ale nie wiem co na to inni zawodnicy.

Bardzo podobało mi się to, że w zadaniach podana była informacja o tym, że można dostać też punkty za rozwiązania w gorszej złożoności. Na niektórych konkursach idzie się nawet o krok dalej i podaje się dokładną liczbę punktów, którą można dostać za rozwiązania mieszczące się w danym limicie, co też wydaje mi się fajnym rozwiązaniem.

Rundy rozproszone zawsze bardzo lubiłem, bo wymagały bardziej analizy problemu i kombinowania niż znajomości wyszukanych algorytmów. Jednakże ich testowanie było dość skomplikowane, więc nigdy nie wiedziałem, czy dostanę za nie 10 czy 1 punkt. Świetną alternatywą okazało się zadanie sonda! Wymagało ono dużo kombinowania i zmagania się z częściową nieznajomością grafu. Do tego bardzo łatwo można było sobie wygenerować testy i samemu zweryfikować czy rozwiązanie jest poprawne. Mimo, że w tej rundzie nie miałem za dużo czasu, żeby rozwiązać to zadanie, to baaardzo mi się podobało :)

Także podsumowując, to miło spędziłem tydzień i dziękuję ;)

Temat PA 2019 #6461 | Artur Kraska | Dodany: 2019-12-18 23:52:48

I ja dziękuję za konkurs oraz za bardzo ciekawe zadania.

Temat Podziękowania #6459 | Karol Kosiński | Dodany: 2019-12-18 17:44:57

Brawo :) ale wygląda na to że z tych co mają 15 punktów, tylko 10+5 dostaną koszulki (tym razem nie będzie zaokrąglania).

Temat koszulki #6458 | Michał Kaczmarczyk | Dodany: 2019-12-18 16:33:32

Zadanie Sonda było super. Jedna z nielicznych okazji, by napisać na konteście kilkaset linii kodu i nie mieć wrażenia, że to straszny syf.
Trochę mi brakowało rundy rozproszonej

Temat PA 2019 #6457 | Konrad Paluszek | Dodany: 2019-12-18 13:56:59

pool is just a list, pool[i]+pool[j] is not always a valid path because i and j may come from the same subtree of the centroid. So I must do binary search even when there is no more than 2e5 candidates.

Temat [POD] Rozwiązania #6456 | Claris Claris | Dodany: 2019-12-18 10:43:43

Zgadłem!

Temat koszulki #6455 | Jakub Sygnowski | Dodany: 2019-12-18 00:46:57

Także dziękuje, jak dla mnie zadania bardzo trudne. Kiedy można spodziewać się koszulek? Po finale?

Temat PA 2019 #6454 | Dawid Jasiak | Dodany: 2019-12-17 20:17:00

Dołączam się do podziękowań dla organizatorów, szczególnie za dobre testy! Moim zdaniem kombinacja trudności zadań z długością konkursu jest bardzo dobra. Zadania również były ciekawe i sporo się nauczyłem próbując je rozwiązać. A czy za trudne to zawsze jest sprawa do dyskusji. To czego mi brakowało, to omówienia możliwych rozwiązań, bo jednak po paru godzinach (nieudanych) prób chciałbym znać jakie były algorytmy użyte w rozwiązaniu wraz ze złożonością, przypadkami szczególnymi itd. A nawet po udanym rozwiązaniu warto znać czy były inne sposoby. Na szczęście tę rolę przejmują ludzie z forum, to trochę pomaga :)

Temat PA 2019 #6453 | Tomasz Jarosik | Dodany: 2019-12-17 18:54:22

Myślę, że brak rundy rozproszonej w tym roku nie zależał od organizatorów. Dopóki Google nie postawi platformy z powrotem i nie przywróci DCJ, nie będzie także rozprosznych PA.

Temat PA 2019 #6452 | Przemysław Derengowski | Dodany: 2019-12-17 18:14:26

Oh, all right. Thank you. In this case I actually don't know how to translate it to a solution using small-to-large instead of centroid decomposition.

I suppose you need to be careful when the answer is among more than 2e5 of the same distances just like we have to be careful when we want write the Selection Rank Algorithm when the elements are not unique (then we need to partition the set inside which we search into three chunks: less than pivot, equal to pivot, and greater than pivot). I wonder if there was such a test. This is also a thing I would need to fix in what I wrote.

And when you have not more than 2e5 candidates for the answer and you generate them, I suppose you could run a linear Selection Rank Algorithm to find the answer. And if you sort all these candidates, then you can just pick the element with the required rank from them in constant time, you don't need to a binary search, do you?

Temat [POD] Rozwiązania #6451 | Kamil Niziński | Dodany: 2019-12-17 17:30:46 | Ostatnia modyfikacja: 2019-12-17 17:55:40

Też chciałbym podziękować. Tak jak co roku, zadania były na wysokim poziomie i sprawiały dużo radości z rozwiązywania. Najciekawsze dla mnie to były Sonda i Podatki drogowe – bardzo dobrze się przy nich bawiłem.

Temat Podziękowania #6449 | Marek Sommer | Dodany: 2019-12-17 15:23:08

Nie trzeba wprost utrzymywać ścieżek. Wystarczy dla każdego wiersza/kolumny utrzymywać najbardziej wysuniętą warownie, będącą w obszarze ścieżki (tzn warownia należy do obszaru górnej ścieżki gdy na niej leży lub jest powyżej), a dla warowni czy należy do obszaru górnej lub dolnej ścieżki.
Aktualizować strukturę możemy dfs-em, który odwiedza warownie i sprawdza czy można coś zaktualizować. Aby znajdować "sąsiadów" wierzchołka w dfs-ie utrzymywałem dla każdego wiersza/kolumny set zawierający warownie w tym wierszu/kolumnie.

Temat [OIW] Rozwiązania #6448 | Bartosz Podkanowicz | Dodany: 2019-12-17 15:19:24 | Ostatnia modyfikacja: 2019-12-17 15:20:40

Ja trzymałem na secie par intów wszystkie punkty, w których ścieżka skręca. Kod wyszedł na tyle prosty, że mogłem bez większych problemów po prostu skopiować i przerobić dla dolnej ścieżki.

Temat [OIW] Rozwiązania #6447 | Konrad Paluszek | Dodany: 2019-12-17 12:47:14