English
Ostatnie posty
Potwierdzam
Potwierdzam. Jakie macie czasy na tych testach?
Mogą być same inputy
A same inputy spełniające warunki zadania wystarczą, czy masz też ochotę popatrzeć na moje outy?
Na początek skupmy się na jakiejś sensownej charakteryzacji f(A, B). Załóżmy bez straty ogólności, że |A|>=|B|. Okazuje się, że to jakie konkretnie wartości tworzą B nie ma znaczenia, a liczy się tylko i wyłącznie jego długość (ale dla A jak najbardziej wartości mają znaczenie). Konkretniej, niech długości kolejnych monotonicznych przedziałów w A to będą c_1, ..., c_p. okazuje się, że f(A,B)<=x wtedy i tylko wtedy gdy |B| >= sum floor((c_i-2)/(x-1)). W dowód wchodzić nie będę, tym bardziej, że sam go nie dociągnąłem w pełni. Aczkolwiek to że jest to warunek konieczny jest całkiem łatwe i daje intuicję, czemu to może mieć sens.
Skoro już mamy taką charakteryzację to trzeba przejść do zastanowienia się co z tym. Przeiterujemy się po wszystkich wartościach x i wyznaczymy liczbę par A', B' takich że f(A', B')<=x. Dzięki, że liczą się tylko jakieś podłogi przy dzieleniu przez x, okazuje się, że dla ustalonej wartości x jest tak naprawdę tylko O(n/x) nierozróżnialnych grupek początków i końców i nie jest trudno wymyślić zarys algorytmu, który takie coś przetworzy w czasie O(n/x), co daje rozwiązanie O(n log n). Po drodze warto naklepać sobie strukturkę zbioru, która wspiera operacje "dodaj a kopii liczby b do zbioru", "usuń a kopii liczby b ze zbioru", "odejmij 1 od wszystkich liczb w zbiorze", "podaj sumę kwadratów/sumę/liczbę wszystkich liczb w zbiorze" (a tak naprawdę wymagania są bardziej szczegółowe, ale wchodzić w nie nie będę). Owa strukturka ma mniej więcej odpowiadać na ile sposobów można wybrać koniec A' oraz przedział B' dla ustalonego początku A' i ten zbiór się aktualizuje wraz z przesuwaniem początku A'. Ale konkretna implementacja tego wszystkiego jest niesamowicie męcząca i zajęła mi 8h
Skoro już mamy taką charakteryzację to trzeba przejść do zastanowienia się co z tym. Przeiterujemy się po wszystkich wartościach x i wyznaczymy liczbę par A', B' takich że f(A', B')<=x. Dzięki, że liczą się tylko jakieś podłogi przy dzieleniu przez x, okazuje się, że dla ustalonej wartości x jest tak naprawdę tylko O(n/x) nierozróżnialnych grupek początków i końców i nie jest trudno wymyślić zarys algorytmu, który takie coś przetworzy w czasie O(n/x), co daje rozwiązanie O(n log n). Po drodze warto naklepać sobie strukturkę zbioru, która wspiera operacje "dodaj a kopii liczby b do zbioru", "usuń a kopii liczby b ze zbioru", "odejmij 1 od wszystkich liczb w zbiorze", "podaj sumę kwadratów/sumę/liczbę wszystkich liczb w zbiorze" (a tak naprawdę wymagania są bardziej szczegółowe, ale wchodzić w nie nie będę). Owa strukturka ma mniej więcej odpowiadać na ile sposobów można wybrać koniec A' oraz przedział B' dla ustalonego początku A' i ten zbiór się aktualizuje wraz z przesuwaniem początku A'. Ale konkretna implementacja tego wszystkiego jest niesamowicie męcząca i zajęła mi 8h
Cześć, Czy ktoś może użyczyć jakiś test dla Łamigłówki ?
odziwością jest p
To skoro jeszcze nikt nie spytał - jak rozwiązaliście to zadanie?
Potwierdzam
Potwierdzam
@Yehor Kharchenko Możesz skorzystać np. z narzędzia toster, o którym jest mowa w kategorii "Kwestie techniczne", lub też możesz napisać własny skrypt - w bashu to jest dosłownie kilka linijek
A w jaki sposób sprawdzacie te testy? Nigdy tak nie robiłem
Poczekałem do opublikowania właściwych testów i te największe wykonują się u mnie lokalnie 10x szybciej. Kompiluję tym samym poleceniem, ale bez flagi static, bo linker nie znajduje odpowiedniej do tego biblioteki lcrt0.o.
Może to wina architektury ARM64 mojego urządzenia - wiadomo, że zawsze będą różnice, ale nie spodziewałbym się nigdy aż takich dużych i tak wahających. Na kolejne razy postaram się załatwić urządzenie z x86_64
Może to wina architektury ARM64 mojego urządzenia - wiadomo, że zawsze będą różnice, ale nie spodziewałbym się nigdy aż takich dużych i tak wahających. Na kolejne razy postaram się załatwić urządzenie z x86_64
Ja zlokalizowałem dżdżownicę wpisując w google image "codeforce worm image" :D