Kto się podzieli?

Do czego?

Ryki? Wielokąty duże testy?

Wielokąty:

Podzadanie 4 (łatwiejsze): Ważny limit jest taki, że wszystkie możliwe kształty wielokątów zawsze mieszczą się w danym prostokącie X x Y, więc każdy możliwy kształt daje do wyniku coś w stylu (X - szerokość) * (Y - wysokość). Zatem trzeba przesumować po wszystkich kształtach cztery sumy: X*Y, X*-wysokosć, -szerokość*Y, -szerokość*-wysokość. Można to zrobić w ten sposób, że dynamikujemy jak w mniejszych podzadaniach (po posortowanych kątowo wektorach) dp[x][y] - liczba sposobów dojścia łamaną do punktu (x, y), ale gdy jesteśmy na samej górze przemnażamy dp[x][y] *= y dla każdego y. W ten sposób zmieniamy definicję dynamika z "liczba możliwych łamanych" na "suma po max_y" dla każdej łamanej. Podobnie trzeba zrobić z szerokością.

Podzadanie 3 (trudniejsze): Trzeba zrozumieć, że to zadanie to plecak. Mamy możliwe przedmioty (wektory) i mamy je zsumować do wartości (0, 0). Otóż niewzięte przedmioty też będą sumować się do (0, 0)! Jeśli suma współrzędnych możliwych wektorów to S, to każdy kształ o szerokości i wysokości (w, h) odpowiada kształtowi (S-w, S-h). Więc zamiast zliczać kształty (2000, 2000), można zliczać coś typu (193, 193), bo S = 2193.

Ryki:

Każdy wymiar robimy niezależnie, potem jakoś da się to złączyć (nie mówię, że trywialnie).

Sortujemy początkowe położenia (wartości x[i]) i zamieniamy to na ciąg różnic sąsiadów. W takim ciągu ryk robi tyle, że po obu stronach najbliższe nie-zera zmniejszą się o 1. Tak można rozwiązać zadanie dla N <= 2000.

Teraz symulujemy całość, ale po drodze dorzucamy tarcze typu L i R (lewe i prawe). Gdy niedźwiedź ryczy, to zmniejsza dwie liczby o 1 i tam właśnie stawiamy dwie tarcze - oznaczają one, że te miejsca mają jednak +1 w przypadku, gdy ten niedźwiedź okaże się być Limakiem. Takie tarcze poruszają się potem w dosyć regularny sposób. Trzeba pomyśleć: gdy potem kolejny niedźwiedź zaryczy, to gdyby jednak poprzedni był Limakiem, to gdzie teraz mamy +1 w porównaniu ze scenariuszem, gdy nikt nie jest Limakiem? Z tego momentu jeszcze daleko do rozwiązania, ale idea jest właśnie taka.

Tbh, trzecie podzadanie z hipotetycznym TL=2min do wielokątów jest moim zdaniem prostsze niż czwarte, bo nie ma wielkiej filozofii w odjęciu złych od dobrych, a odejmuje się praktycznie tym samym kodem co do drugiego subtaska. Niestety aby się wyrabiało w czasie to musiałem skorzystać z rozdzielności mnożenia względem dodawania, która pozwalała spreprocessować dużo rzeczy (co mi zajęło godzinę). No i jeszcze trzeba mieć jedną magiczną stałą, która jest rozwiązaniem bodajże dla X=Y=2193, K=100, którą trzeba albo wziąć z rozwiązania czwartego podzadania albo zobaczyć że jakieś dzbany wrzuciły plaintextem outy do trzeciego subtaska na forum i wtedy zrobienie czwartego subtaska odpada nam jako zależność do zrobienia trzeciego :P.

Czemu w skwarkach limit na n nie był np. do 30000? Da się zrobić w O(n*log^3(n)) :D

Btw, nie zgodzę się z Kamilem i tym, że "Więc zamiast zliczać kształty (2000, 2000), można zliczać coś typu (193, 193), bo S = 2193.". Trzeba zliczać rzeczy typu (2193, 193), typu (193, 2193) i typu (193, 193) (taka prosta zasada właczeń i wyłączeń w pewnym sensie) i to 2193 mocno bruździ w złożoności i trzeba przez to dorzucić ten preprocessing, o którym pisałem w poprzednim poście.

Mateusz, możesz przechwalać się słowami "umiem w lepszej złożoności". Nie musisz jak kierunek-dół pytać czemu nie takie limity.

I nawet gdybyśmy zdawali sobie sprawę z takie złożoności, to pewnie nie chcielibyśmy tego odróżniać od naszego O(n^2 * log(n)).

Wojtkosz, słowa "kształty (2000, 2000)" zdefiniowałem w swoim poście jako kształty o wysokości i szerokości 2000, więc podtrzymuję, co powiedziałem. A zgadza się, że sumowanie takich (szer, wys), że szer, wys >= 2000 wymaga czegoś więcej niż sumowania szer, wys <= 193.

Chętnie poznam jakiekolwiek rozwiązanie do skw.

Skwarki:
Pierwsza sprawa jest taka, że jak K>=11, to out to 0. Jest tak gdyż za każdym razem odpada co najmniej połowa, bo z każdej pary sąsiednich ktoś musi wypaść (nooo, z dokładnością to jakiejs parzystości, costam).
Naszym pobożnym życzeniem jest napisać dynamika dp[n][k], który by mówił, ile jest takich ciągów, że wiadomo co i aby dało się go przeliczać. Jeżeli popatrzymy gdzie stoi n, to widzimy, że problem się rozpada na dwie niezależne problemy dla lewej i prawej części. Niestety nie odpowiadają one dokładnie oryginalnemu problemowi, gdyż jest to n, które będzie zjadało ludzi z tych połówek. Zatem muszę sobie uogólnić problem na taki, gdzie zarówno po lewej jak i po prawej stronie może stać nieskończoność, która co ruch zjada odpowiedni skrajny element. Zatem jak zdefiniuję sobie dynamika dp[a][b][c], gdzie 1<=a<=n, 1<=b<=k, 0<=c<=2, gdzie a oznacza długość ciągu, b oznacza ile zajmuje zjedzenie ciągu i c oznacza z ilu boków stoją nieskończoności, to jego da się już łatwo przeliczać w O(n^2k^2), co jak się pożyłuje to wchodzi. Będąc trochę ostrożniejszym za pomocą jakichś sum sufiksowych czy czegośtam da się zejść do O(n^2k), ale już sobie tym nie zawracałem głowy widząc, że program w n^2k^2, który nazwałem "SkwBrut" działa mi sekundę na maxteśćie.

@Wojtek dzięki, doszedłem do wielu z tych rzeczy, diabeł tkwi w tym dynamiku właśnie, nie udało mi się go wyprowadzić.

Ja to robiłem inaczej. dp - liczyło to, co trzeba (zostaje jeden zwycięzca z N elementów po K rundach), dp1 - liczyło ile jest permutacji tak, żeby cały przedział "zniknął" gdy jest ograniczony z jednej strony (nic nie zostaje), dp2 - to samo, tylko że z 2 stron. Wzory są guzik warte, nie ma co się nad nimi rozwodzić, zresztą pewnie nawet już nie pamiętam/nie ogarniam, czemu działają. Nie mogłem ich bardzo długo dopracować i z każdą godziną, metodą prób i błędów, byłem coraz bliżej poprawnej wersji.

Teraz najlepsze. Wiedziałem już, że ta edycja PA idzie do kosza - nie ma sensu bawić się w jakieś bruty do A i szczątkowe punkty. Nie mogąc zrobić SKW, spojrzałem na GRA i po przeczytaniu, że 2 jednostki nie mogą być nigdy na tym samym polu, odpuściłem. Ale walczyłem dalej ze SKWurczysynem - do końca.

Program zaczął niespodziewanie działać 2 minuty przed końcem, ale nie zdążyłem go wyczyścić z danych testowych i dałem wczytywanie po tym, jak wyliczałem kombinacje % P, które było == 0, więc wszędzie error... Złożoność to O(n^2k^2) ale u mnie działał szybko i innym też chyba wchodził, więc przestawienie linijki dałoby ACC.

Edit. Wzory faktycznie są nieciekawe, ale ogólna idea sprowadza się do przesuwania największego elementu po każdej pozycji. W momencie gdy ten element jest na pozycji i, to są 2 przedziały [1,i-1], [i+1,N] i one są ograniczone z jednej strony i muszą zniknąć w odpowiednim czasie. Z kolei do wyliczenia czasu znikania przedziału ograniczonego z jednej strony, stosuję tę samę koncepcję przesuwania maxa, ale teraz to się rozbija na przedziały: ograniczony z dwóch stron i ograniczony z jednej strony, więc jeszcze raz to samo w postaci dp2 i robi się z tego syf.

Hm, jak się zauważy, że warto sobie rozszerzyć stan dynamika o te nieskończoności, to te przejścia akurat piszą się tak po prostu moim zdaniem. Ale dla jasności załączam mam nadzieję, że całkiem czytelny kodzik, który po zrozumieniu poprzedniego posta powinien być self-explanatory: https://imgur.com/a/WFNmxHa (RE idzie od 1 do n, REP od 0 do n-1, FOR od a do b, wszystko włącznie, a newt[a][b] to symbol Newtona a po b)

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.

Nie, ten dwuwymiarowy dynamik się przydawał tylko do preprocessingu czwartego (i w małym stopniu też trzeciego) podzadania. W subtaskach 1, 2, 3 korzystałem z metody prawie identycznej z tą napisaną przez Ciebie.

Mateusz, możesz przechwalać się słowami "umiem w lepszej złożoności". Nie musisz jak kierunek-dół pytać czemu nie takie limity.
https://run3freegame.com

Nie, ta dwuwymiarowa dynamika służyła jako cenny preprocesor tylko dla czwartego podzadania (iw mniejszym stopniu trzeciego). Zastosowałem technikę, która jest prawie identyczna jak twoja w podkartach 1, 2 i 3. Dziękuję bardzo https://typeracer.onl/