Jak działa przecinanie półpłaszczyzn w O(n log n), o którym wspomniał Konrad?

Jest już znany termin wrzucenia zadań na szkopul.edu.pl?

Znalazłem w swoim kodzie buga i chciałbym sprawdzić jak poradziłby sobie na sprawdzarce.

C++17 - jestem za, codeforces już to robi.
C++20 - jeszcze niestabilne.
Biblioteki z algorytmami i strukturami danych, szczególnie z zaawansowanym aparatem np. algebra liniowa - to by za bardzo zmieniło zawody. To co jest bardzo trudne dziś, mogłoby okazać się bardzo łatwe z aparatem który daje Eigen. A pomysł to chyba zawody w stylu OI, Codeforces.
Ktoś mógłby użyć tych struktur bez zrozumienia ich, a to też jest niezbyt fajne. Przynajmniej niech je przepisze z wikipedii xd.
Polecam dla frajdy w wolnym czasie rozwijać własny katalog algorytmów.

Z rozwiązania Kacpra wynika, że jest O(n) interesujących półpłaszczyn...

@Maciek: patrz na komentarz #5520. Da się mieć liniowo wiele półpłaszczyzn.

Teoretycznie może być O(n^2) półpłaszczyzn więc ich przecinanie w O(n^3) daje O(n^6) co wygląda na dużo za dużo. Nie wiem tylko czy w praktyce da się skonstruować testy z taką dużą liczbą półpłaszczyzn. Ja miałem O(n^2) przecięcie, bo łatwiej takie napisać od zera i trochę się bałem że O(n^4) to będzie za dużo, ale widzę, że O(n^6) wchodziło...

Mam mieszane uczucia co do zadania GRA. Z jednej strony fajnie się to pisało i w sumie dobrze się bawiłem przy klepaniu i oglądaniu jak się ruszają gostki na moim wizualizatorze.

Tylko to trochę inna dyscyplina sportu. Już zadania rozproszone są inne, więc pytanie czy potyczki to ma być wielobój programistyczny, czy jednak konkurs z klasycznego 'sports (competetive) programming'.

No niestety jako że się nigdy nie bawiłem w maratony/deadliny itp. to popłeniłem błędy nowicjusza. (Uwaga na ból dupy).
Wysłałem późno pierwszy submit. I okazało się, że z jakiegoś powodu dopowiedziałem sobie, że w bazie może być jednostek ile chcesz. A jak dopisałem żeby może być tylko jedna, to zaczęły się blokować. Udało się to na szczęście naprawić. Wziąłem się za buldożery, i znowu wysłałem dopiero jak już na moim wizualizatorze zaczęło działać. Już myślałem, że mam pewne 8pkt i zacznę żyłować do 10. A po wysłaniu okazało się, że jest jakiś bug w całym kodzie do tych tanków i dostaje komunikat że ruszam jednostką z pola na którym nie ma jednostki. Ten bug był współdzielony z kodem wizualizacji i przez to wyglądało, że wszystko jest ok. I koniec końców nie znalazłem tego co psuło. Mam 4+0 zamiast 4+4 za to zadanie. I pewnie tych 4pkt braknie.

@Konrad

Jest n^2 punktów przecięcia prostych. Dla każdego patrzysz czy jest wewnątrz każdej półpłaszczyzny. To co zostało to wynik. Jak dla mnie dużo prostsze.

Zadanie GRA było bardzo fajne jak na swój typ, można było wymyślać do niego wiele podejść, trzeba było poradzić sobie z jakimiś zagadkami typu:
- kiedy dokładnie odnosić złoto do bazy? Na początku trzeba szybko żeby budować nowe jednostki, później trzeba z tego zrezygnować i zebrać złoto z drugiego końca planszy.
- co zrobić na koniec, gdy wszyscy odnoszą złoto, aby się nawzajem nie zablokowali?
Nie byliśmy zasypani masą niepotrzebnych komend tak jak to bywa czasem na konkursach 24-godzinnych. Przydałby się rzeczywiście wizualizator od organizatorów, szczególnie że zawodnicy nie byli przygotowani przed zawodami do pisania własnych.

Ja niestety za tego typu zadaniami nie przepadam i uważam, że Potyczki to nie miejsce na takie zadania. Mam też nadzieję, że w przyszłych latach się takie nie pojawią. Sprawdza ono inny zestaw umiejętności, niż ten jakiego zazwyczaj oczekuje się na konkursach algorytmicznych (a te zawody są Algorytmiczne nawet z nazwy). I nie mam tu na myśli ogólnie zadań optymalizacyjnych, czasami zadania optymalizacyjne mają algorytmiczny posmak i nie mam nic przeciwko, żeby w tę stronę Potyczki poszły w przyszłych latach. Zadanie Gra to był po prostu zbyt duży skok na poniższej liście:
- Przeciętne zadanie z Potyczek
- Przeciętne zadanie optymalizacyjne na konkursie algorytmicznym
- Przeciętny TopCoderowy Marathon
- Zadanie Gra
- Przeciętny Deadline 24 (którego już niestety nie ma)

@Konrad Paluszek
Masz 80 punktów za cztery pierwsze rundy i nigdy nie byłeś w finale, zrobiłbyś Skwarki + jakiegoś bruta i miałbyś pewny finał... Nie wiem co masz do zadania WIE, składało się trochę z 3 różnych zadań, ale każde z nich było jak najbardziej algorytmiczne. Mnie osobiście zadanie RYK z nawiązką zrekompensowało nieprzyjemności związane z zadaniem GRA.

Zgadzam się ze Świstakiem co do słowa w kwestii RYK,WIE,HER,DRZ. Co do FUT to mam spory niedosyt, bo co mam zrobić było dla mnie prawie oczywiste dość szybko, ale do końca rundy nie udało mi się znaleźć właściwego wzoru, choć miałam ich ze 4 w tym 2 bardzo podobne do tego "właściwego". Poza tym udało mi się wersję trudniejszą tak zoptymalizować (na 2 węzłach), że na maxteście (k=5*10^8) chodziła tylko 9.97s i mi trochę smutno że wszystkie testy były tak duże że nawet jeden punkt za to nie wpadł.

Ok można. Ale to + przecinanie w O(n^3) chyba nie jest prostsze do naklepania niż przecinanie w O(n log n)

Sam pomysł wrzucenia zadania optymalizacyjnego oceniam zdecydowanie pozytywnie. Podobała mi się też jawna punktacja i jej rozkład (z moimi 3 punktami za to zadanie wcale nie uważam, że grupy były zbyt proste).

Samo zadanie miało moim zdaniem dobry balans między skomplikowaniem problemu (mało komend, jasne cele) a różnorodnością rozwiązań (chyba dość sporo).

Natomiast nie podobały mi się szczegóły. Ograniczenie na jedną jednostkę na pole było chyba najgorszym z nich. Przestrzeganie tego mocno przenosiło ciężar zadania z algorytmu na klepanie przypadków. A zwłaszcza w wersji, gdzie ruch jest natychmiastowy, więc nawet kolejność ruchów jest istotna.

Niektórzy podają tu czasochłonność jako dobrą rzecz, ale dla osób, które nie mogą poświęcić całego weekendu (a nawet i całego tygodnia, bo pewnie niektórzy mieli rundę 4. zrobioną w czwartek i mogli na rundę 5. poświęcić całe 3 dni a nie tylko 2) był to problem. Zwłaszcza jak się nie zrobiło pozostałych zadań to trudno było się przekonać żeby przerwać bezowocne (choć przynajmniej dość przyjemne) rozważania nad WIE/RYK i przejść w tryb N godzin klepania.

Popieram pomysł osobnej rundy optymalizacyjnej, włącznie z propozycją jednego zadania za 20 punktów (być może jako 10 pkt łatwiejszych B oraz 10 trudniejszych A).

Podsumowując, jestem za, ale w wersji bardziej algorytmicznej a mniej implementacyjnej.

To jeszcze pytanie do WIE.
Ten dynamik to jest zawsze u was dwuwymiarowy? jesli tak, to ja nie lapie jak idac do punktu (a,b) pamietac aktualna dlugosc i szerokosc ksztaltu w momencie gdy zaczynamy zawracac. Moglby ktos mi rozjasnic bo chyba tego kroczku mi brakowalo.

No i napisze moze jak ja to nieudolnie probowalem rozwiazac. Podchodzilem do tego w bardziej w jezyku funkcji tworzacych, niz w jezyku dynamikow ale to sie latwo tlumaczy:

0) wyznaczam mozliwe wektorki

1) Dziele wektorki mozliwe na 4 grupy, w zaleznosci od tego w ktorej sa cwiartce. ((1,0) jest tu troche wyjatkowe ale pominmy ten szczegol techniczny). Niech S to bedzie grupa wektorkow w pierwszej cwiartce.

2) ziborowi wektorow T przyporzadkowuje funkcje tworzaca W_T(X, Y) = Prod_(t in T) (1+X^t_x * Y^t_y)
(wspolczynnik przy X^aY^b mowi na ile sposobow moge dojsc do a,b uzywajac wektorow z T.)

3) Zeby policzyc ile jest ksztaltow to trzeba policzyc
W_S(X,Y) * W_S(Y^(-1), X) * W_S(X^(-1), Y^(-1))* W_S(Y,X^(-1))
i popatrzec na wspolczynnik przy (0,0).

4) Problem jest taki, ze gubimy wtedy jak ksztalcik jest wysoki i jak ksztalcik jest szeroki.

5) Mnozac pierwsze dwa czlony W_S(X,Y) * W_S(Y^(-1), X) znam wysokosc ale nie znam szerokosci, bo pierwszy czlon idzie w prawo, a drugi w lewo. Wiec dodaje nowa zmienna Z (wymiar w dynamiku), ktora pamieta jak daleko poszedlem w prawo i mam
Prod_(S in S) (1+X^s_x * Y^s_y Z^s_x) * W_S(Y^(-1), X).
Wspolczynnik przy X^aY^bZ^c to jest na ile sposobow mozna dojsc do (a,b) idac najdalej c krokow w prawo.

6) Teraz mam polowe wielokata. I przez symetrie musze dolozyc druga. Skladaja sie do calosci wyrazy X^aY^bZ^c_1 i X^aY^bZ^c_2
i taki wielokacik ma wysokosc b i szerokosc c_1+c_2-a.

Problem w tym ze mam trzy wymiary. A na domiar zlego na koncu musze rozwazyc wszystkie pary w jednym wymiarze, wiec jest wolmo.

Widzialem ze w 4 tym podzadaniu zawsze sie "zmiesci" i w zwiazku z tym jak licze (X-x_i)*(Y-y_i) to wystarczy mi znac liczbe ksztaltow, sume dlugosci ksztaltow i sume x_i*y_i po ksztaltach. Liczbe ksztaltow to mozna u mnie wyznaczyc w kroku 3) a sume w kroku 5), x_i*y_i jest tylko problematyczne ale pewnie wystarczy pochodna policzyc w paru miejscach.
Ale i tak sam krok 5 byl za wolny.

Gdyby z każdego wierzchołka wybrać kandydatów na odpowiedź i ustalić, czy tak poprowadzony wektor miałby tworzyć figurę zegarowo lub antyzegarowo, to łatwo wtedy dla każdego punktu zostawić 2 skrajne odcinki.

@Bartłomiej Szczygieł: Co do PAL, to ja sobie po prostu upakowalem te literki w:
struct Packed16Chars {
unsigned int c0:5,c1:5,c2:5,c3:5,c4:5,c5:5,c6:5,c7:5,c8:5,c9:5,c10:5,c11:5,c12:5,c13:5,c14:5,c15:5;
} __attribute__((packed));
zeby sie w pamieci zmiescilo. I przeszlo.