@Jakub Sygnowski
"W moim osobistym rankingu wygrywa DAG
(swoją drogą, czy ktoś wie, czy rozwiązanie z Fibbonaccim jest optymalne / optymalne w granicy k -> inf?)"
Jest wątek w "Runda 5 > [DAG] Fibonacci"
Ostatecznie okazało się, że Fibbonacci nie jest optymalny nawet dla k = 100. (Różnica 4 wierzchołków)

Potwierdzam

Cofnięcie terminu na październik-listopad powodowałoby kolizję Potyczek z Olimpiadą Informatyczną, co mogłoby wykluczyć wielu uczniów szkól średnich.

W zadaniach interaktywnych można by rozwiązać ten problem poprzez komunikację przez stdio tak jak w nie-interaktywnych, zamiast linkowania ze sprawdzaczką.

Zalety:
* nie trzeba robić biblioteki w każdym języku
* interfejs taki sam jak w innych typach zadań
* limit pamięci nie jest dzielony ze sprawdzarką
* sama pamięć nie jest dzielona
* łatwiej przetestować rozwiązanie "ręcznie" z klawiatury

Potencjalna wada to że komunikacja międzyprocesowa jest wolniejsza niż wewnątrz-procesowa. Ale to chyba nie jest wielki problem, po prostu może musi być trochę większy limit czasu jeśli tej komunikacji jest bardzo dużo.

(powtarzam się, napisałem to samo w wątku "programowanie funkcyjne", ale piszę też tu dla zachowania kontekstu)

No ale co myślicie pomyśle z dogrywkami? Do C jest osobny wątek.

Mi się C też podobało, (także jako motywator i poprawiacz humoru) - zwróć jednak uwagę, że w tym roku na koszulkę wystarczyło za B dostać 12 punktów. (12!) IMO częściowo wynika to stąd, że zasoby pochłonęło C.

Pomijalność rundy C wiąże się nie tylko z prostotą, a też z odsłanialnością. Proste zadania też można zbugować, a więc wypadałoby je otestować - ale z odsłanialnością można pominąć testowanie i jak działa na przykładowym to ship it.

"Grupa C okazała się bardzo popularna jednak dla osób, które chciałyby spróbować sił w trudniejszych zadaniach (np. zrobić więcej zadań z A), dodatkowe zadania z C są pewnym obciążeniem." - e tam, są na tyle proste w porównaniu do reszty, że czas na nie poświęcony jest pomijalny, a też są przyjemne

Są i tacy, co od prezentów wolą konferencje o machine learningu. Ale ci też byli smutni, zarówno w tym roku (https://nips.cc/) jak i w poprzednim (https://nips.cc/Conferences/2019).

Przydałoby się też wsparcie dla wzorów matematycznych.

Z twierdzenia Kőniga wiemy, że wynik = maksymalne skojarzenie = minimalne pokrycie wierzchołkowe. Czyli chcemy wybrać jak najmniejszy zbiór cyrkowców, tak, żeby w każdym rzędzie i w każdej kolumnie zostali wybrani albo wszyscy z hula-hop, albo wszyscy bez hula-hop.

Zdefiniujmy zmienne:
a(i,j) = 1 jeśli dany cyrkowiec ma hula-hop
x(i) = 1 jeśli w rzędzie i wybieramy do pokrycia wierzchołkowego tych z hula-hop
y(j) = 1 jeśli w kolumnie j wybieramy tych z hula-hop

Cyrkowiec (i,j) zostanie wybrany chyba że x(i) = y(j) ≠ a(i,j).

Więc chcemy zminimalizować sumę:

S = suma(i,j) (1 - a(i,j)(1-x(i))(1-y(j)) - (1-a(i,j))x(i)y(j))
= n^2 - suma(i,j) a(i,j) + suma(i) x(i) suma(j) a(i,j) + suma(j) y(j) suma(i) a(i,j) - (suma(i) x(i)) * (suma(j) y(j))

Zdefiniujmy dalsze zmienne:
b = suma(i,j) a(i,j)
c(i) = suma(j) a(i,j)
d(j) = suma(i) a(i,j)

S = n^2 - b + suma x(i)c(i) + suma y(j)d(j) - (suma x(i))(suma y(j))

Jeśli posortujemy wiersze i kolumny tak, żeby c(i) i d(j) były niemalejące, to wtedy najlepiej x(i) i y(j) ustawić na 1 na jakichs początkowych ich prefiksach.

Czyli musimy wybrać jakieś liczby X i Y i przyjąć:
x(i) = 1 jeśli i <= X
y(j) = 1 jeśli j <= Y

S = n^2 - b + suma(i<=X) c(i) + suma (j<=Y)d(j) - XY

Dla danego X, najlepiej wybrać jak największe Y takie, że d(Y) <= X.
Zdefiniujmy:
e(i) = liczba j takich, że d(j)<=i.

I wtedy:
S = n^2 - b + suma(i<=X) c(i) + suma (i<=X)(Y-e(i)) - XY
= n^2 - b + suma(i<=X) (c(i) - e(i))

Więc w naszym rozwiązaniu będziemy utrzymywać liczbę b (liczba cyrkowców z hula-hop) oraz ciągi:
* nieposortowane c(i)
* nieposortowane d(j)
* posortowane c(i)
* posortowane d(j)
* e(i)
* drzewo przedziałowe liczące i minimalizujące sumy prefiksowe (c(i)-e(i))

Na początku liczymy początkowe ciągi c(i), d(j) zamiatając prostokąty od lewej do prawej oraz od góry do dołu, utrzymując drzewo przedziałowe mówiące nam dla kolejnych kolumn, którzy cyrkowcy mają hula-hop i ilu ich jest. Przy okazji dla każdej poprawki króla tutaj też obliczamy, czy ona doda czy odejmie jedno hula-hop.

Następnie sortujemy ciągi, obliczamy e(i), i inicjalizujemy sumy prefiksowe (c(i)-e(i)).

Dla każdej poprawki króla poprawiamy posortowane ciągi w odpowiednich miejscach przy pomocy wyszukiwania binarnego i wtedy wiemy też gdzie należy poprawić e(i).

Czy ktoś (organizatorzy? xd) chciałby się podzielić rozwiązaniem do tego zadania?

Skoro poprzez wprowadzenie grupy C otwarty został temat formatu potyczek podzielę się następującym pomysłem:

Do grupy A i B wprowadzamy dogrywki - czyli mówiąc językiem studenckim sesję poprawkową ("Pospiesz się chłopcze, nie tylko Ty chciałbyś zdać ten egzamin")

W tym celu:
- Po zakończeniu rundy ujawniane są tylko wyniki (nie są publikowane testy)
- Po zakończeniu rundy rozpoczyna się dogrywka. Dogrywka trwa 24 h.
- Limit zgłoszeń w dogrywce analogicznie jak w rundzie właściwej.
- W trakcie dogrywki można poprawić wynik z ostatniej rundy (nie można go pogorszyć).
- Maksymalna liczba punków do zdobycia w dogrywce to 0.5 * (10 - liczba-punktów-zdobytych-w-rundzie-właściwej)
Jeśli w rundzie właściwej uzyskałem 0, to za rozwiązanie w dogrywce ocenione na 10 punków mogę zdobyć maksymalnie 5 punków. (0.5 * (10 - 0))
Zadanie rozwiązane na 8 pktów, mogę poprawić na 9, itd.
- Po zakończeniu dogrywki publikowane są testy.
- Losowanie koszulek bez zmian (punkty z dogrywek nie są uwzględniane)
- Do rozważenia czy w ostatniej rundzie są dogrywki (wydłużałoby to konkurs o jeden dzień, ale byłoby fajne)

Dogrywki nie stanowią żadnego obciążenia dla czołówki (czyli pod tym względem są lepsze niż C) a tak samo dają szansę osobom, które wykruszały się pod koniec zawodów. (Jest dużo opinii na forum, że konkurs świetny tylko czasu mało.

Grupa C okazała się bardzo popularna jednak dla osób, które chciałyby spróbować sił w trudniejszych zadaniach (np. zrobić więcej zadań z A), dodatkowe zadania z C są pewnym obciążeniem. Może ciekawą propocycją byłaby zasadza, że punkty za C = maks(zadanie-A, zdanie-B, zadanie-C). (Być może też punkty za B = maks(A, B)).

Do zobaczenia za rok!

No wiem, napisałem sobie, ale chciałem mieć coś sprawdzonego.

Jak rozwiązałeś to zadanie na 10 punktów?

Zgadzam się z Wojtkiem. Poza tym, "programowanie funkcyjne" to bardziej nazwa stylu programowania niż użytego języka. W C++ również można programować funkcyjnie. Po prostu niektóre języki mają przyjemniejszą notację i lepsze wsparcie do tego niż inne.