A ja popieram propozycję Jakuba. Motywacja już zdąży opaść zanim zadania pojawią się na szkopule... o ile w ogóle się pojawią, bo tych bardziej nietypowych (w tym rozproszonych) nie ma. A tak można dostać np. tydzień po PA na zaklepanie zadania na spokojnie, po ewentualnym wcześniejszym zapoznaniu się z rozwiązaniami na forum. I dopiero po tym tygodniu można by było zwyczajowo opublikować konkursowe kody źródłowe uczestników.

Nie popieram natomiast zmiany formuły konkursu - cały jego urok jest w tym, że ma się limitowany czas na rozwiązania. Złe pomysły, głupie błędy i niezdążanie z implementacją to duża część uroku Potyczek.

Też chciałem zaproponować możliwość wysyłania rozwiązań przez pewien czas po zakończeniu konkursu. Po zakończeniu rund zdalnych robię jeszcze zadania, których nie zrobiłem wcześniej i fajnie byłoby mieć możliwość wysłania rozwiązań. Wiem, że istnieje "Szkopuł", ale to już nie to... :)

To chyba musiałaby być osobna „funkcyjna” runda albo dywizja. Na przykład jedno lub dwa zadania z dywizji „A” wymagałyby rozwiązań funkcyjnych albo w niektórych rundach pojawiłyby się zadania z osobnej dywizji „F”.

Co do propozycji Jakuba: zadania z "Potyczek" pojawiają się regularnie w serwisie "Szkopuł", a tam warunki są takie same. No tylko rankingu już nie ma...

Mnie się wydaje, że jakkolwiek formuła "Potyczek" jest w pewnym sensie wyczerpująca i wymaga dużego zaangażowania jeżeli ktoś chce zająć się wszystkimi zadaniami, to powinna być jednak utrzymana. Co prawda biorę w niej udział pierwszy raz, ale jak przez mgłę pamiętam, że próbowałem się zmierzyć z pierwszą edycją "Pogromców Algorytmów" i wtedy było bardzo podobnie.

Z drugiej strony rozumiem, że chciałoby się mieć luźniejszą formułę i bardziej rozłożone w czasie rozwiązywanie zadań i zdobywanie punktów. Tylko wtedy chyba lepiej byłoby pomyśleć o zorganizowaniu zupełnie innego, dodatkowego konkursu, coś a'la "Liga Potyczek Algorytmicznych" która trwa przez jakiś dłuższy czas (może miesiąc, może pół roku) i tam powiedzmy co tydzień pojawiają się zadania. Tym sposobem zadowoleni byliby tacy uczestnicy, którzy nie mogą wygospodarować czasu na intensywną pracę przez tydzień, ale mogą sobie pozwolić na mniej intensywne, ale regularne poświęcenie się zadaniom. Dodatkowym bonusem takiego rozwiązania jest 'ćwiczenie' się przed "Potyczkami" właściwymi, taki regularny trening.

Oczywiście wymagałoby to sporego nakładu pracy od Organizatorów, a dla nich to też może nie być takie łatwe, biorąc pod uwagę ich normalne, codzienne obowiązki.

A co myslicie po prostu o mozliwosci wysylania rozwiazan przez jakis czas po zakonczeniu konkursu?
- tylko "przez jakis czas" - bo chcielibysmy byc oceniani w tych sanych warunkach (np. programy odpalane na tym samym komputerze, z tym samym kompilatorem), a utrzynywanie tych warunkow dluzej moze byc klopotem
- od razu "po zakonczeniu konkursu", bo wtedy jest najwieksza chec do rozwiazania tych zadan

Spróbuj sam napisać. Przyda się to: https://pl.wikipedia.org/wiki/Sortowanie_topologiczne

Dwie uwagi do forum.

1. Przydało by się pokazywać na głównej stronie kiedy jest ostatni post w każdej kategorii (żeby od razu było widać czy coś się nowego pojawiło bez wchodzenia do środka).

2. Prośba o nieusuwanie spacji i użycie czcionki o stałej szerokości. W tym momencie wklejenie dowolnego kodu albo jakiegoś diagramu w ASCII-art jest mało przewidywalne, a często niemożliwe w sposób czytelny.

Może się ktoś podzielić sprawdzaczką do DAG, w sensie programem który wypisze n i k dla danego grafu?
A może organizatorzy wrzucą swoją do plików?

Jest chyba jeszcze lepiej: dla trójkowej drabinki mi wyszło n=57 dla k od 774840978=2*3^18 do 1162261466=3^19-1, czyli dla k=10^9 również.

To może po prostu dodać możliwość wysyłania zadań po terminie, ale wyniki takich zgłoszeń lądują w oddzielnym rankingu? Wtedy format jest tylko minimalnie zmieniony (testy nie mogłyby być widoczne zaraz po rundzie), a deadline jest do niedzieli. Wtedy przegapienie jakieś rundy ciągle umożliwia rozwiązania zadania "trochę pod presją".

Wpasowuje sie w scenariusz Pana Wladyslawa (zakladam, ze powinienem zwracac sie przez Pan :P), ale nie podzielam opinii o zmianie formatu.

O Haskellu: obawiam się, że w tym języku da się, ale może być trudno napisać wydajny kod -- wszystko przez to, że obliczenia są domyślnie leniwe, co często może spowolnić kod wielokrotnie, jeśli nie jest się bardzo ostrożnym pod tym względem. Więc to może być na Potyczkach frustrujące doświadczenie.

Osobiście prędzej używałbym nie-leniwego języka funkcyjnego, jak SML albo Ocaml, ale z jakiegoś powodu niestety wyszły one trochę z mody.

Ja spróbuję opisać swój pomysł na deterministyczny algorytm, którego nie próbowałem implementować.
Bazowane na 2 prackach. Jedna bardziej standardowa, która wyznacza 3-edge spójne składowe w grafie, np. https://sci-hub.se/10.1016/j.ipl.2013.09.010 3-edge spójne składowe to podział wierzchołków na grupki taki, że pomiędzy dwoma wierzchołkami jest flow >=3 iff są w tej samej grupce. Zauważę, że wbrew nazwie, takie grupki nie muszą być spójne.
Druga robiące prawie że to samo zadanie co to to Optimal Offline Dynamic 2,3-Edge/Vertex Connectivity https://arxiv.org/abs/1708.03812
W tej drugiej jest de facto opisany m.in. sposób na odpowiadanie offline czy dwa dane wierzchołki są w tej samej 3-edge spójnej składowej w dynamicznym grafie, do którego wchodzą i wychodzą krawędzie i wystarczy tego algosa lekko dostosować. Stosujemy tę metodologię, gdzie modelujemy ten dynamiczny graf tak aby i-ta krawędź żyła w każdym momencie poza i-tym, tzn. na prefiksie [1, i-1] oraz sufiksie [i+1, m]. To co tam się dzieje to taki mniej więcej tak rozbijanie przedziału życia krawędzi na przedziały bazowe albo też można inaczej o tym myśleć jak o plecaku bez jednego. Jak schodzimy w głąb drzewa przedziałowego, to mamy część krawędzi już scomittowanych, a część, która gdzieś się jeszcze pojawi niżej i zbiór końców takich krawędzi nazwijmy aktywnym zbiorem W. Chcemy nasz duży graf G zastąpić mniejszym H, który będzie równoważny pod względem 3-edge spójności na aktywnym zbiorze W, tzn. dla każdej pary wierzchołków u,v \in W zachodzi że min(flow_G(u, v), 3) = min(flow_H(u, v), 3). Na początek wyznaczamy w nim liniowo te 3-spójne składowe i każdą z nich ściągamy do 1 wierzchołka (nie jest to ściągnięcie w standardowym sensie, bo taki zbiór nie musi być spójny, ale wiadomo). To co zostanie to graf, gdzie nie ma pary wierzchołków o flow>=3. Takie grafy to kaktusy, gdzie każda krawędź leży na max 1 cyklu (wierzchołki mogą). Niestety taki kaktus wciąż może być duży w porównaniu do rozmiaru W, a chcielibyśmy aby jego rozmiar był liniowy względem W. Na szczęście standardowo można pościągać wszelkie długie ścieżki pamiętając o tym aby aktualizować odpowiedź i jak ściągamy ścieżkę to trzeba też pamiętać jej długość, zatem mamy krawędzie z krotnościami. Odcinamy też "liście" kaktusa, w których nie ma już aktywnych wierzchołków, tzn. takie "liściowe cykle", na których nie ma nic z W. Łatwo zauważyć, że po wykonaniu takich operacji nasz kaktus skurczy się do rozmiaru liniowego od W, zatem operując na przedziale o długości k mamy preserver 3-spójności o rozmiarze liniowym od k i wszystko śmiga. Złożoność jakiś O(n polylog(n)), być może jak się uważnie zaimplementuje to nawet się da O(n log n).

Poruszyłem temat innych języków programowania w "Kwestie techniczne" (bo tego subforum jeszcze nie było).

Mateusz Radecki napisał:

> Inne języki są problematyczne głównie przez zadania interaktywne, chcielibyśmy mieć możliwość zaskakiwania nimi i nieodcinania nagle kogoś piszącego w innym języku. To samo z zadaniami rozproszonymi, których powrotu nie wykluczamy.

Pomysł rozwiązania tego dla zadań interaktywnych: prowadzić interakcję przez stdin / stdout tak jak w innych zadaniach. To rozwiązałoby problem różnych języków, a także ma dodatkowe zalety: program ma dostęp tylko do swojej pamięci (więc nie ma ryzyka, że dwa moduły będą sobie nawzajem psuć dane), a także limit na pamięć nie byłby dzielony z nieznanym cudzym kodem. Łatwiej też przetestować rozwiązanie, bo można prowadzić interakcję bezpośrednio z terminala bez potrzeby pisania dodatkowego kodu testującego.