Potyczki są bardzo fajne, ale mają bardzo słabe forum, przydałoby się coś co wyświetla nieprzeczytane posty. Najprostszym fixem, który może trochę polepszyć czytelność jest wywalenie podziału na działy.

Przy okazjo zajrzyjcie tutaj: sio2.mimuw.edu.pl/c/pa-2018-1/forum/87/934/

Trzeba było to napisać w Opiniach i Komentarzach. Kto czyta "kwestie techniczne"?

Kwestie techniczne na finale Potyczek Algorytmicznych nie zmieniają się od lat:
- każdy ma do dyspozycji taki sam komputer, dostarczony przez organizatorów (Czasami można było przynieść swoją klawiaturę, czasami nie).
- nie można mieć żadnych materiałów, żadnej biblioteczki, ani w wersji papierowej ani w elektronicznej.

Chciałbym podyskutować, głównie z tegorocznymi finalistami i organizatorami, co sądzicie o potencjalnych zmianach w tych ustaleniach.
Co na przykład gdyby pozwolić zawodnikom na korzystanie z własnych laptopów?

Argumenty za:
- Organizatorzy nie muszą załatwiać dla nas komputerów, ale być może Potyczki mają własne komputery i to nie jest duży problem, aby je przewieźć na miejsce zawodów i podłączyć?
- My nie musimy przyzwyczajać się do nowych klawiatur.

Argumenty nie wiem czy za czy przeciw:
- Rykoszetem pozwalamy zawodnikom korzystać z biblioteczki. Pytanie czemu tego nie chcemy? Przy odpowiednich zadaniach biblioteczka nie powinna być potrzebna. Na rundach zdalnych tylko przecięcie półpłaszczyzn w magicznych wieżach było ewidentnie biblioteczkowym problemem. Ja osobiście napisałem je od zera, jako że w środę było jeszcze na to dużo czasu. Zakazywanie biblioteczki podobno premiuje niedoświadczonych zawodników, którzy nie jej mają. Mnie osobiście wydaje się że jest wręcz przeciwnie. Doświadczony zawodnik drzewo potęgowe, albo KMP pisze bezmyślnie z pamięci, a niedoświadczony najprawdopodobniej ma je gdzieś napisane na swoim komputerze i w razie czego może skopiować, a napisanie od zera zajmie mu dłuższą chwilę.

Argumenty przeciw:
- zawodnicy z daleka będą mieli trudniej przywieźć swój komputer. Pamiętam jak kiedyś Fecebook Hacker Cup wpadł na pomysł z pozwoleniem na własne komputery, tam nie było problemu z biblioteczką, gdyż jest dostęp do internetu nawet w trakcie zawodów (Aktualnie własne komputery są normą na finałach FBHC czy TCO). Okazało się, że dokładnie wszyscy finaliści wybrali pisanie na własnych laptopach, mimo że musieli je przywieźć z innych kontynentów. Podobnie wiele z nas pewnie pamięta, że nasz współfinalista Juliusz Straszyński potrafił nawet przewieźć swój komputer stacjonarny na konkursy przez pół Polski.
- Każdy będzie miał inne warunki pracy, ale czy naprawdę przewaga kilku GB ramu na zawodach Algorytmicznych potrafi coś zmienić? Uważam, że duuużo więcej potrafi zmienić '\' w innym miejscu, niż ten do jakiego jesteśmy przyzwyczajeni.
- Organizatorzy nie będą mieli podglądu na nasze ekrany i będą mieli słabszą zabawę w trakcie zawodów. Ale chyba nie o ich dobrą zabawę tutaj głównie chodzi.

Proponuję następujące głosowanie w komentarzach w tym wątku:
a) Jestem za pozwoleniem na własne komputery.
b) Jestem za pozwoleniem na korzystanie z biblioteczki, ale nie na własne komputery.
c) Dobrze jest jak jest i nic nie należy zmieniać.

Ja jestem za opcją a).

To prawda, dobrze o tym myślisz. Analogicznie ozwiązanie z 14 częściami powinno być już warte 10 pkt. Najwyraźniej zadanie było w Twoim zasięgu tylko po prostu nie byłeś przygotowany na rozproszony format. Powodzenia w następnych zadaniach takiego typu :) (o ile jeszcze będzie jakakolwiek okazja do ich robienia, bo coś gorszy okres rozproszone przeżywają :<)

Bardzo ciekawy wątek! Myślałem, że będzie chodziło o jakąś magiczną kompresję 1. połowy.
Nie tylko pakowanie, ale może wciągnięcie kawałka, zrobienie statystyk itp. i następnie jakiś huffman czy coś.
Liczenie na jakiekolwiek punkty za wersję dla słów o długości do 2 * limit_pamięci (na statycznej tablicy char'ów) było złudne.

@Tomasz Jarosik: To nie wystarczy dla najdłuższych słów. @Jakub Sygnowski obliczył że w 4MB się nie zmieści pół najdłuższego słowa nawet jak upakujesz najgęściej jak się da (w długą liczbę o podstawie 26). Potrzeba na to dokładnie log(26^(10^7))/log(2^(8*2^20)) MB =~ 5.6 MB.

> muu
Czy to już USACO?
Btw fajny pomysł z dublami i modulo P

Dziwnie się kod wkleił, aczkolwiek dobry myk z doublami lokalnie.

@Marek, rozwiń!

A ja jeszcze dodam, że w myśl zasady: "nieważne, jak głosują, ważne jak liczą głosy" taka lista, jaka została ogłoszona, powinna obowiązywać. Jeśli nastąpiła pomyłka, to powinno się ją co najwyżej poszerzyć, a nie modyfikować. Za takie błędy się płaci w każdym cywilizowanym miejscu, a dodanie +1 uczestnika do finału, to nie jest zbyt wysoka cena.

> muu

Sorki, ale: XD

Nie bardzo widzę sens opakowywania samej arytmetyki modulo w klasę, jedyna zaleta jest taka, że nie zapomnę zmodulować albo zrzutować na long longa, ale jak się trochę popisze opakowywania w klasę, to się to nie zdarza. A plus jest taki, że często mogę oszczędzić na liczbie modulowań jak np. dodaję n liczb, to mogę wszystkie dodać na long longach i zmodulować raz, albo jak mnożę przez małe liczby, to moduluję tylko na koniec.
Natomiast tak, zdarza mi się to opakowywać w klasę, ale w taką, która z -DLOCAL liczy modulo p i na doublach, żebym nie musiał się zastanawiać, czy 142857145 to jest 1/7, czy 5/7, czy 1 + 1/7, albo mógł zobaczyć czy rząd wielkości wyniku się mniej więcej zgadza, a bez tego liczy tylko modulo.
A wygląda to tak:
const int mod = 1e9 + 7;
long long inv(long long b) {//To jest oczywiście dla mod pierwszego
assert(b);
int e = mod - 2;
long long r = 1;
while (e) {
if (e & 1)
r = r * b % mod;
b = b * b % mod;
e >>= 1;
}
return r;
}
#ifdef LOCAL
#define loc(r...) r
#else
#define loc(...)
#endif
struct zet_p {
int v;
loc(long double w;)
sim = int> zet_p(c r = 0) : v(r % mod) loc(, w(r)) {}
loc(sim> zet_p(c a, long double b) : v(a % mod), w(b) {})
#define rer(o, f) zet_p operator o (zet_p y) {return zet_p(v f loc(, w o y.w));} \
zet_p & operator o##=(zet_p y) {ris = *this o y;}
rer(+, +y.v) rer(-, -y.v) rer(*, * 1ll * y.v) rer(/, * inv(y.v))
int get() {return ((unsigned int)v + mod) % mod;} //Rzutowanie jest potrzebne tylko, jeśli 2*mod nie mieści się w incie
zet_p operator-(){return zet_p(-v loc(, -w));}
bool operator==(zet_p y) {return (v - y.v) % mod == 0;}
};
#define ccy(o) sim> zet_p operator o(c a, zet_p b) {return zet_p(a) o b;}
ccy(+) ccy(-) ccy(*) ccy(/)
sim> bool operator == (c a, zet_p b) {return zet_p(a) == b;}
loc(muu & operator<<(muu & d, zet_p y) {return d << "<" << y.get() << "=" << y.w << ">";})

>Potwierdź że znasz regulamin.
>Nie przeczytaj go.
>???

* W STL i tak są różne rzeczy, jak np. iterowanie po permutacjach. Albo B-Drzewa, nawet z agregowaniem wartości w poddrzewach (rozszerzenie GCC). Nikt jakoś nie narzeka, że jest to gotowe.
* Nie trzeba przepisywać z Wiki, wystarczy skopiować kod od kogoś z CodeForces albo publicznie dostępny na jakiejś stronce.
* Eigen nic nie zmieni, nie ma tu takich zadanek, gdze przydałby się do czegoś więcej niż jako wygodne wektory (nawet wektory intów do eleganckiego chodzenia po grafach-siatkach), ew. macierze
* Własny katalog algorytmów fajna rzecz, aczkolwiek nie znam nikogo oprócz mnie, kto by chociażby opakowywał arytmetykę modulo w klasę o_0 Nie żebym był jakimś koksem, ale sądzę, że i koksom by to pomogło

Problem tylko, że biblioteczki - własne i niewłasne - nie są za bardzo promowane, bo sporo osób przygotowuje się na różne zawody onsite (w tym nawet finał Potyczków!), gdzie wszystko trzeba klepać od zera, nawet makra. Niestety liczy się raczej umiejętność szybkiego pisania makaronu bez bugów - co jest możliwe... ale to dość dziwna umiejętność :P