Moje podejście "binarne" daje co najwyżej 60 węzłów (2*(log-1)+2) = 2*29+2.

2 3
3 (jeśli 1. bit zapalony, połącz z ostatnim wierzchołkiem; w przeciwnym wypadku -1)
4 5
5 (jeśli 2. bit zapalony, połącz z ostatnim wierzchołkiem; w przeciwnym wypadku -1)
7 8
8 (jeśli 3. bit zapalony, połącz z ostatnim wierzchołkiem; w przeciwnym wypadku -1)
...
itd.

Dla k = 5, dałoby to następujący graf
6
2 3
3 6
4 5
5 -1
6 -1
-1 -1

Ja zrobiłem z ciągiem fibbonacciego, po jednym węźle na liczbę ciągu fib. (aż do największej mniejszej od 'k') + po dodatkowej na każdy zapalony bit w zapisie jako suma elementów ciągu fib.

Zrobił ktoś to zadanko z drabinką w formie:
2 3
3 4
4 5
5 6
6 7
....
która dawała kolejne liczby Fibonacciego? Powinno to dać max koło 66 węzłów.

Standardowe podejście binarne z drabinką w formie:
2 3
4 5
4 5
6 7
6 7
....
lub:
2 3
3 -1
4 5
5 -1
6 7
7 -1
....
mi dało 88 węzłów w najgorszym przypadku (2^30-1-2^27).

Też uważam że trochę zmarnowane, ja np. na to zadanie wysłałem najdłuższy program ze wszystkich :) (a zdobyłem ponad połowę punktów w konkursie).

W tym właśnie rzecz, że ambitne zadanie próbne nie zachęca nowych uczestników do zapoznania się z SIO :)

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.

Kiedyś było więcej:

https://web.archive.org/web/20170929201907/http://potyczki.mimuw.edu.pl:80/l/24/

"Dopuszczalne są jedynie programy w następujących językach programowania:
C
C++
Java (z wyjątkiem zadań rozproszonych)
Pascal (z wyjątkiem zadań rozproszonych)"

Przenośnym assemblerem można w jako tako pisać w c++, pascala nikt nie uzywał a na Javę ludzie narzekali bo wolna była ;-)

IMHO rust mogłby nam zwiększyć zasięgi (i nie ma, jak python, problemu z Java'y). Na pewnej grupie FB byłą nawet niedawno dyskusja o advent of code i dlaczego u nas jest badziwny odpowiednik, ludzie odpowiedzieli: przecież mamy PA:) Ale jednym z zastrzeżeń było waśnie ograniczenie języków do cepa.

Jak trudne by było. Jeśli dobrze rozumiem, skąd się bierze trudność, to dość upierdliwe. Te programy nie są uruchamiane bezpośrednio, tylko (chyba*) jakby emulowane. Ktoś to napisał dla c++. Dla innych (czy jakoś kombinować przez LLVM) - chętnych chyba nie ma. Jak są chętni, projekt to chyba SIO2.

*) Pewną przesłanką jest to, że kompilujemy wg standardu c++17, a uruchamiane ejst na "komputerach 32 bitowych" :)

Nie zapominajmy, że jeszcze można było wypisać -1 :P

Zadanie próbne było w tym roku dość ambitne, ale naszym zdaniem dla osób mających duże doświadczenie mogło się ono wydać całkiem standardowe i mało ciekawe, by zobaczyć je podczas zwykłych rund. Z tego względu zdecydowaliśmy się użyć go jako zadania próbnego.

Co do ogólnie zadań próbnych, to mogą one być różnego poziomu, może to być to np. jakieś zadanie, które zostanie po ustaleniu co idzie na który dzień.

Nie zapominajmy też, że głównym celem rundy próbnej jest sprawdzenie całego systemu i pozwolenie zapoznać się z SIO nowym uczestnikom :P

To tak dla potomności wyjaśnię, że outy do swoich testów generowałem programem
int n, m;
cin>>n>>m;
if (m == n - 1) {
cout<<(n - 1) * (n - 2) * (n - 3) / 6<<endl;
} else {
cout<<n - 1<<endl;
}
gdyż wygenerowałem trzy drzewa i trzy potrojone drzewa xD. Tak na rozruszanie forum, bo pusto było :P

Taaa, modulo było bardzo podchwytliwe xd

Moim zdaniem zadanie próbne było bardzo fajne, ale nie na rundę próbną. Lepiej, żeby zadanie próbne, było na poziomie zadań z grupy C. W dodatku przez to zostało one trochę "zmarnowane". Można było je dać do normalnej rundy B.

Wygląda to trochę jakby autorzy zadań mieli zbyt dużo ciekawych pomysłów, więc jeden z nich trafił do rundy próbnej :D

Ja robiłem podobnie jak @Krzysztof, tylko jakoś dziwnie skminiłem tę część:
"Dalej zauważmy, że dla ustalonego R optymalnie jest brać kolumny dopóki nie trafimy na kolumnę o mniej niż n-R jedynkach. A więc dla każdego R utrzymujemy pewne optymalne C[R], które rośnie wraz z R, i wynik uzyskiwany przez parę (R, C)." i nie umiałem update'ów robić na drzewie przedziałowym, więc robiłem na jakiejś strukurce pierwiastkowej pewnie bardzo podobne operacje i w sumie miałem O(m log n+ q sqrt(n)) które zmieściło się w limitach czasowych.

Z twierdzenia Halla (czy tam jakiegoś jego uogólnienia) wiemy, że jeśli rozważymy wszystkie pozbiory jedynek, dla każdego weźmiemy zera z którymi są połączone, i znajdziemy maksymalny "niedomiar" (liczba jedynek minus liczba zer), to wynikowy matching całości będzie mniejszy od pełnego matchingu o właśnie tyle.

Teraz zauważamy, że jedyne zbiory jedynek jakie warto brać pod uwagę są postaci: weźmy podzbiór wierszy, podzbiór kolumn, i rozważmy jedynki na ich przecięciu. Do tego jeśli dla wierszy i kolumn zapiszemy ile w nich jest jedynek, i posortujemy oba ciągi malejąco, to interesują nas tylko ich prefiksy (R wierszy o największej liczbie jedynek i odpowiednio C kolumn).

Dalej zauważmy, że dla ustalonego R optymalnie jest brać kolumny dopóki nie trafimy na kolumnę o mniej niż n-R jedynkach. A więc dla każdego R utrzymujemy pewne optymalne C[R], które rośnie wraz z R, i wynik uzyskiwany przez parę (R, C).

Gdy przychodzi update, te wszystkie struktury zmieniają się albo na O(1) pozycji, albo ewentualnie coś dodajemy/odejmujemy na sufiksie, co łatwo załatwiamy drzewem przedziałowym. Trzeba jeszcze zbudować te wszystkie rzeczy (sumy w wierszach/kolumnach, etc) dla początkowego stanu planszy, ale to już standardowe (zamiatanie z leniwym drzewkiem z operacją "flip bitów na przedziale").

Może ktoś zechce się podzielić rozwiązaniem? Ja doszedłem do punktu gdzie moje (niepoprawne) rozwiązanie umiało przejść wszystkie testy z forum w <6s. Ciekawi mnie jak to się robiło poprawnie.