Miałem podobną obserwację, choć trochę inną.

Zliczałem sumy prefiksowe, ile kamieni łącznie zostało dodanych (nawet jeśli potem zostały usunięte) w okresie 1..qi, co pozwala w czasie stałym określić wartość dla dowolnego przedziału [i..j].

Następnie jeśli najlepszy wyliczony wynik w chwili qi to a1_i, a następny - a2_i, to dla następnego j nie trzeba przeliczać wartości a2 dopóki a1_j > a2_i + łączna liczba kamieni dodanych w przedziale [i..j].

Ja mogę udzielić Ci odpowiedzi probabilistycznej, chociaż nie jestem jurorem!

Jeśli liczyłaby się absolutna zgodność z plikiem .out, oznaczałoby to, że każda osoba, która uzyskała 10 punktów za to zadanie, wpadła na dokładnie ten sam ciąg - nie odwrócony, nie zamienione A z P, nie jeden z wielu możliwych, tylko dokładnie ten sam. Zdaje się, że szansa na to jest wykładniczo mała, prawda?

Mam krótkie pytanie techniczne dotyczące sprawdzania zadania "Palindromy".
W treści zadania oraz w wyjaśnieniu do przykładu jest jasno napisane, że może istnieć więcej niż jedno poprawne słowo (np. dla n=4, k=3 wzorzec to AAPA, ale słowo PPPA również w pełni spełnia warunek zadania,
bo jego najdłuższy palindrom ma długość 3).
Mój algorytm generuje poprawne słowa, które jednak różnią się znakami od oficjalnych plików np. pal0.out.
Chciałbym się tylko upewnić. Czy system przy tym zadaniu korzysta ze specjalnego weryfikatora, który po prostu sprawdza właściwości wygenerowanego słowa i akceptuje każdą poprawną odpowiedź, czy wymagana jest absolutna zgodność znaków z plikiem .out?
Z góry dziękuję za odpowiedź!

Ja się pochwalę obserwacją która bardzo mi się spodobała, na której oparłem swoje rozwiązanie:
Jeżeli para (liczba pierwsza, reszta) daje co najwyżej d/3 kamieni, gdzie d to aktualna liczba kamieni, to przez kolejne d/3 jednostek czasu na pewno nie będzie wybijać wyniku.

Czyli jak w jakimś momencie czasu znam wszystkie takie pary, które dają co najmniej jedną trzecią, to wystarczy mi jakiś czas utrzymywać county tylko dla nich. A jak ten czas minie to wyznaczam takich kandydatów od zera. Gdybym miał zrobić takiego rebuilda w czasie O(d) to wtedy takie rozwiązanie się pięknie amortyzuje do liniowki. Randomizowany rebuild w O(50d) działał mi jakieś absurdalne 40 sekund, chyba dlatego że dużo skakał po pamięci, więc musiałem go porzucić. Końcowo mam dwie wersje rebuilda, jedna dla małych d (<=100) w d^2 (nie jest oczywisty! korzystam z bardzo podobnej obserwacji co deterministyczna wzorcowka ale w jej słabszej wersji), druga dla dużych d w O(300+d*C), gdzie C to będzie liczba dużych liczb pierwszych (>n^1/3), które będą dzielić >=10 losowych par z 300 losowań - ciężko zrobić aby C to było więcej niż kilka.

Jeszcze nie wiem czy mi wchodzi, zakładam że nie na wszystkie punkty. Chociaż na uruchomieniach próbnych jeszcze się mieściłem. Powinienem nazwać temat "moje być może działające rozwiązanie" zamiast "rozwiązanie", sorry 😔

(Po tygodniu wstrzemięźliwości nie mogłem odmówić sobie przyjemności skorzystania z AI, przepraszam za slop)

Jak zwykle, wielkie dzięki za zadania! Szczególnie spodobały mi się zadania wdp i spl (choć nie udało mi się doprowadzić rozwiązań do końca). Moim zdaniem trudność zadań C została dobrana idealnie — będę polecać znajomym, którzy wcześniej nie zajmowali się programowaniem sportowym, aby spróbowali swoich sił w przyszłym roku. Bardzo podobały mi się zadania typu run twice, co stało się dla mnie dodatkową motywacją, by w końcu zacząć korzystać z WSL. Świetny balans tematów, zadania są bardzo różnorodne (na pierwszy rzut oka trudno wręcz uwierzyć, że większość z nich wyszła spod pióra jednego autora, Adam orz).

Małe niedociągnięcia/propozycje, które praktycznie nie wpłynęły na satysfakcję z udziału:

Zgadzam się z Wojtkiem, że kolejność nie była do końca optymalna — odczułem to zwłaszcza czwartego dnia, kiedy oba zadania wymagały napisania mnóstwa kodu, podczas gdy trzeciego dnia kodu prawie nie było, a same zadania były znacznie prostsze. Wydaje mi się, że umieszczenie dwóch trudnych implementacyjnie zadań w jednym dniu uderza szczególnie w tych „szaleńców”, którzy na czas zawodów nie biorą urlopu.

W obu zadaniach interaktywnych miałem pewne trudności z testowaniem lokalnym. Otrzymywałem dziwne werdykty przy podawaniu niepoprawnych testów i zajęło mi trochę czasu, zanim zrozumiałem, o co chodzi (nie jestem pewien, czy da się to zrobić lepiej).

Chciałbym widzieć więcej informacji o punktacji w zadaniach, w których łatwo to sprecyzować. Nie zaglądałem do testów, ale wydaje mi się, że w zadaniach na zapytania lub tam, gdzie istnieje wiele rozwiązań z różnymi limitami dla n można by pisać o tym nieco bardziej przejrzyście.

Jeszcze raz dziękuję i do zobaczenia w przyszłym roku!

I to Ci wchodziło tak po prostu? Ja miałem spore problemy, w szczególności najważniejszym (dość szybkim i popularnym z tego co słyszałem) krokiem było rozważanie tak tylko liczb pierwszych większych niż pierwiastek sześcienny z n, żeby rozważać dwie liczby pierwsze zamiast ośmiu (a te mniejsze niż około 200 zrobić osobno). Pomimo to i tak wydawało mi się, że powinienem użyć clock(), żeby zrobić tyle powtórzeń ile zdążę i skrzyżować palce, bo bałem się po prostu zrobić ich np. czterdzieści.

:(

My mamy deterministycznie. Pojawi się pewnie jutro rano ale tldr:

jak popatrzysz sobie na zbior wlaczonych pozycji a1,a2,…,am i na roznice elementow w odleglosc maks 2 lub 3 to kandydat na skok musi byc dzielnikiem O(m) z tych liczb

Mamy zatem juz O(1) dużych kandydatów na skoki. Jak kandydat staje się kandydatem to przeliczamy go w O(m). Jak kandydat przestaje być kandydatem, to i tak go zostawiamy i usuwamy go dopiero jak spadnie poniżej połowy progu na bycie kandydatem. W ten sposób po każdym updacie utrzymujemy O(1) kandydatów na skok, a te dodawania w O(m) się ładnie amortyzują.

Widzę że nie ma nigdzie rozwiązania, a komuś już zacząłem moje wykładać, więc się podzielę.

Cały oznaczał liczbę kamyków aktualnie na planszy przez m.
W danym momencie wynik to co najmniej m/2, bo możemy wziąć kamienie parzyste albo nieparzyste.
Więc jak wylosujemy sobie trochę kamyków to jest duża szansa że któryś jest w odpowiedzi. To chcemy teraz rozwiązać problem znalezienia wyniku z jednym kamieniem.
1) Długość skoku będzie liczbą pierwszą - jeśli nie jest i wynosi d, to dzielniki pierwsze d dają co najmniej taki sam wynik, więc można wziąć któryś z nich.
2) Prosta konsekwencja powyższego jest taka, że jeśli chcemy zebrać dwa wybrane kamienie, to skok musi być dzielnikiem pierwszym odległości między nimi.
Wystarczy więc dla każdego wylosowanego kamienia przeiterować się po wszystkich pozostałych i policzyć ile razy każda liczba pierwsza występuje jako dzielnik jakieś różnicy. Każda różnica może mieć maksymalnie 8 różnych dzielników pierwszych. Jak się dzielniki pierwsze preprocessuje to dla jednego kamienia można ten proces zrobić w O(m * 8).

No ale nie możemy za każdym razem losować nowych kamieni bo będzie q^2*(liczba losowań). Zamiast tego chcemy utrzymywać sobie zbiór A kamieni gwarantując że po i-tej operacji każdy kamień ma taką samą szansę bycia wybranym. Jak dostajemy nowy kamień to mu losujemy priorytet i naszym zbiorem jest zawsze A kamieni z najmniejszym priorytetem. Kameinie które nie są wybrane trzymamy na kolejce priorytetowej czy na czymś żeby móc łatwo wybrać nowy jak zostanie jakiś wybrany usunięty. Czyli po każdej operacji jest szansa A/m że wybierzemy nowy i wtedy musimy przeliczyć wynik dla niego w czasie O(m * 8). Ale w oczekiwaniu to jest po prostu O(A * 8). Dodatkowo jak dodajemy/usuwamy to musimy to dodać/odjąć wszystkim kandydatom, ale to też daje O(A * 8) na zapytanie. No i jeszcze mamy czynnik log(n) z utrzymywania kolejki, chociaż można to było robić bez niej. Całościowo O(q * A * 8).

Pominąłem kilka rzeczy, takich jak utrzymywanie maska dla każdego wylosowanego kamienia, ale to łatwiejsze części. Tylko limity są dość spore, więc dodatkowo trzeba na wszystko uważać. Na przykład nie mogłem trzymać 'ile razy dzielnik d występuje dla tego kandydata' na unordered_map. Zamiast tego musiałem skompresować wszystkie liczby pierwsze do 1,2,...K i potworzyć statyczne tablice żeby mi się w pamięci zmieściło. I jeszcze kilka innych takich spraw

dzieki za wytlumaczenie

A ja mysle, że na 1 i bardzo doceniam żart, uśmiechnąłem się 😁😁😁

Zastanawiam się na ilu poziomach ironii operuje stawel :p... Obstawiam, że zero, ale w Internecie nigdy nie wiadomo xd

No ale to tragedia jakaś, jak ktoś ma jakoś prościej, to ja też chętnie się dowiem xd

Na początek obowiązkowe podziękowania za przygotowanie Potyczek :)

Jedną kwestią, którą chciałem poruszyć było ustawienie zadań względem ich trudności. W tym roku było to prawie prawdą, że (oczywiście po wykluczeniu zadań C) wszystkie zadania z rundy n były trudniejsze niż wszystkie zadania z rundy n-1. Jedynie malutka liczba inwersji dzieli moim zdaniem ten statement od prawdy. 3A zajęło mi sumarycznie około 0.5h (podczas gdy 3A na ostatnich dwóch edycjach zajmowały mi po ~15h), a 5B KOD było pierwszym zadaniem B od wielu lat, którego nie zrobiłem, pomimo długich prób. Do 3 rundy włącznie miałem wrażenie, że to najprostsze Potyczki ever, a za to piąta runda była chyba najtrudniejsza ever. Moim zdaniem byłoby lepiej jakby jednak powykonywać trochę swapów i na pewno byłbym szczęśliwszy jakby np zamienić 3A z 5B WDP i bardziej rozsmarować tę trudność po całym tygodniu, bo jednak rzadko kiedy się widzi, że 5B jest trudniejsze niż 4A, a 4B (a imho nawet 3B xd) niż 3A

Dla konkretów mój ranking trudności: 5A PRU>5A SPL>5B KOD>4A>5B WDP>4B>2A>3B>3A>1A>2B>1B

EDIT: Po przemyśleniach ja bym zadania na rundy podzielił o tak:
1A GRM, 2A WDP, 3A BAL, 4A KOD, 5A PRU SPL
1B KON, 2B STO, 3B KAM, 4B KOS, 5B PKN MUL