O (n^3)? Tych półpłaszczyzn miałeś O(n), nie O(n^2)?

Według mnie to zadanie było zupełnie nie w klimacie potyczek i nie wydaje mi się że to dobry kierunek. Ogólnie uważam, że tak ja do tej pory, zadania powinny być bardziej ukierunkowane na wymyślenie fajnego algorytmu a mniej na heury (to się tyczy też zadania heros) i rzemieślnictwo programistyczne.

Mi się bardzo podobało, głównie jako zadanie optymalizacyjne, ale też bardzo przystępnie podzielone na subtaski. Dodatkowo system generowania testów był z góry wiadomy, więc tak naprawdę można było napisać generatorkę, checkerkę i lokalnie wszystko symulować nie martwiąc się o przypadki brzegowe, a jedynie o ogólną wydajność

@Wojtek

W MAGu można było napisać brutalnie przecięcie półpłaszczyzn w O( n^3 ), a wtedy kod staję się bardzo prosty.

Ja napisałem to przecinanie od zera i nie było jakoś straszne, zgadzam się, że to było ciekawe zadanie. Podobało mi się też zadanie KON (chociaż trochę słabo, że na forum pojawiły się testy, w których nie można trzymać explicite wszystkich liczb w pamięci, uważam, że zauważenie tego było jednak istotną częścią zadania) i zadanie FUT (zadanie z Algebry Liniowej na Potyczkach, jeeeej :)). Na temat zadania GRA już się wypowiedziałem w innym wątku.... . Nie bardzo też rozumiem co miało na celu danie zadania POD. Reszta zadań jakoś nie porywa, ale była raczej w porządku.

Powiem tyle: chyba jest jakiś powód, że konkurs się nazywa "Potyczki Algorytmiczne", a nie "Potyczki Heuro-Klepackie". Jak zobaczyłem to zadanie (plus jeszcze trochę zadanie WIE), to stwierdziłem, że aż tak mi nie zależy.

C++11 nie jest dużym problemem, ale jest kilka małych myków w nowszych rewizjach, a nawet w C++20, które by się przydały. Podejrzewam, że nie jest to duży nakład pracy, wystarczy zaktualizować kompilator i dodać flagę. Nie wiem, jak z bezpieczeństwem, ale pewnie illegal syscalle i tak są sprawdzane na niższej warstwie, jak np. za pomocą AppArmor.

Dodam, że miałem na tych Potyczkach jeden kod, który kompilował mi się lokalnie z -std=c++11, ale na sprawdzaczce już nie! Dlatego proponuję zaktualizować kompilator tak czy siak. Rozumiecie, że to dość stresująca sytuacja przy limicie 10 zgłoszeń :)

+BONUS: Dodatkowe biblioteki:
Wiem, że mało kto byłby tym zainteresowany, ale byłoby miło, gdyby można używać paru zewnętrznych bibliotek na Potyczkach. Zobaczcie na przykład:
* Eigen - do zadanek z geometrii - głównie super wygodne w użyciu i szybkie wektory (te z matematyki)
* GMP albo MPFR - bignumy + zobaczcie na przykład klasę mpq_class do liczb wymiernych w postaci ułamków, np. do arytmetyki exact w geometrii
* Jakaś klasa do ułamków jak powyżej, ale żeby można trzymać ułamki modulo p pierwsze - żeby odłożyć dzielenie dopiero na wypisywanie wyniku
* Jakaś klasa dla samego modulo p pierwsze
* ...

Większość zawodników zamiast używać takich rzeczy, robi wszystkie obliczenia inline na gołych prymitywnych typach, co jest dość absurdalne.

Natomiast implementowanie wszystkiego samemu jest dość nudne (plus trudno zrobić to naprawdę dobrze).

Mi również brakuje paru ficzerów z nowych C++, jednego nawet z C++20 (Designated initializers).

Jak chcecie popularyzować programowanie Potyczkami, to popularyzujcie, natomiast ja bym zostawił to np. dla CodinGame :)

C++ FTW! Rozumiem, że nie-wymarłe języki dla niektórych to JavaScript, bo robicie strony i apki w robocie (cóż, ja też często), ale nie wyobrażam sobie klepania poważnych algorytmów w czymkolwiek innym niż C++. Na co dzień robię geometrię, rekonstrukcję 3D i takie rzeczy. Jak na przykład wyglądałaby biblioteka do algebry liniowej bez przeciążania operatorów? Zobaczcie np. Eigen. Tak to powinno wyglądać.

Mi się podobało jako "coś innego". Są już rundy rozproszone, które są ogromnym urozmaiceniem. Zwykłe zadanka są w contestach co tydzień na różnych stronkach (ale jakościowo zwykle dużo słabsze).

Jestem za tym, żeby zrobić jeszcze jedną rundę specjalną, właśnie z zadaniem optymalizacyjnym, ew. interaktywnym, ale tylko jednym takim zadaniem na całą rundę (może za 20 punktów) i z sensowną punktacją, np.:
(a) Słabe rozwiązania dostawałyby mało punktów, np. 2/10, a nie 8/10 jak tutaj, a zdobycie maksa graniczyłoby z cudem
(b) Albo najlepiej: liczba punktów byłaby zależna od pozycji w finalnym rankingu dla tego zadania

I jeszcze jedna uwaga - organizatorzy mogliby dostarczyć mini-framework do wizualizacji i testowania gry. Żeby robienie tej nudnej części zadania nie zajmowało 50% czasu zawodnikom ;)

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)

;_;

RIP punkcik.

1a srednio komend = 364.10, liczba komend/linii = 27616
1b srednio komend = 358.80, liczba komend/linii = 27482
2a srednio komend = 361.30, liczba komend/linii = 27592
2b srednio komend = 353.50, liczba komend/linii = 27426
3a srednio komend = 362.70, liczba komend/linii = 27802
3b srednio komend = 363.90, liczba komend/linii = 27947
3c srednio komend = 366.50, liczba komend/linii = 27929
4a srednio komend = 361.80, liczba komend/linii = 27539
4b srednio komend = 361.40, liczba komend/linii = 27572
4c srednio komend = 346.10, liczba komend/linii = 26890
4d srednio komend = 358.60, liczba komend/linii = 27392
4e srednio komend = 366.40, liczba komend/linii = 27626
5a srednio komend = 356.60, liczba komend/linii = 27538
5b srednio komend = 365.30, liczba komend/linii = 27583
5c srednio komend = 361.90, liczba komend/linii = 27775
5d 27806:1: srednia liczba tur przekroczyla k
5e srednio komend = 358.70, liczba komend/linii = 27593
6a srednio komend = 429.60, liczba komend/linii = 37137
6b srednio komend = 408.60, liczba komend/linii = 36364
6c srednio komend = 415.70, liczba komend/linii = 36688
6d srednio komend = 407.00, liczba komend/linii = 36644
6e srednio komend = 408.30, liczba komend/linii = 36729
7a srednio komend = 464.10, liczba komend/linii = 40507
7b srednio komend = 438.50, liczba komend/linii = 39217
7c srednio komend = 427.80, liczba komend/linii = 39494
7d srednio komend = 431.70, liczba komend/linii = 39563
7e srednio komend = 439.80, liczba komend/linii = 39541
8a srednio komend = 449.20, liczba komend/linii = 41471
8b srednio komend = 446.60, liczba komend/linii = 41539
9a srednio komend = 454.50, liczba komend/linii = 41975
9b srednio komend = 462.80, liczba komend/linii = 42274
9c srednio komend = 461.10, liczba komend/linii = 42194
9d srednio komend = 460.10, liczba komend/linii = 42987
10a srednio komend = 497.10, liczba komend/linii = 43890
10b srednio komend = 479.00, liczba komend/linii = 41308
10c srednio komend = 497.80, liczba komend/linii = 43204
10d srednio komend = 491.30, liczba komend/linii = 42871
10e srednio komend = 485.10, liczba komend/linii = 41810

Ogromny zapas na wszystkich testach z kamykami i w 370 ruchach nie zmieścił się tylko 1 test z 25 na tych bez kamyków. W której był paczce? Sad reactions only :P

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.

110 (1 za RYK (było 2, ale nadpisałem 2 minuty przed końcem rozwem dla y=1, który się TLEczy na każdym teście d :P) i 9 za GRA)

Ciężko mi wybrać najciekawsze zadanie z grupy A, bo w zasadzie wszystko poza MAG było bardzo ciekawe. MAG do wykminienia było w porządku, ale jednak było dla mnie dość proste, a trzeba naklepać te przecięcia półpłaszczyzn... Na szczęście ja je miałem w biblioteczce, ale współczuję tym, którzy nie mieli. Ale na pewno też nie było to _złe_ zadanie, było w porządku, ale po prostu reszta fajniejsza.
RYK i WIE to bardzo ciekawe zadania, jak dla mnie prawie idealny zestaw na rundę weekendową.
FUT - bardzo ciekawe, sporą satysfakcję przyniosło mi wykminienie tego zadania po wielu godzinach rozkminy
HER i DRZ - dość prościutkie, ale też fajne. Zobaczyć jakiś miły branching i to jeszcze po czymś co jest małe bo graf jest losowy - supcio.