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.

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.

Co sądzicie o zadaniu GRA? Najlepiej z argumentami. Wasz feedback bezpośrednio wpłynie na przyszłe edycje!

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

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.

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.

Które zadanie najlepiej się klepało/kminiło:
https://www.strawpoll.me/17058624 (grupa B)
https://www.strawpoll.me/17058644 (grupa A)

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? Wielokąty duże testy?

Do czego?

Prawdziwe pytanie brzmi - dlaczego przez ostatnie dwie godziny debugowałem fakt, że sprawdzaczka sobie postanowiła w losowym miejscu przypisać typ unsigned int do jednego z obliczeń? XD

Kto się podzieli?

Aaaa jeśli to hołd dla Martwej to szanuję.

Potwiedzam ryk-y1 od Soko xddddddd. Szkoda tylko że o 23:58 xddddddd

Ja mam 511 na kamyczkach.