W wątku pt. Punkciki (nie czytałem go, ale wskazali mi go organizatorzy w odpowiedzi na pytanie) podane jest, że sortowanie kubełkowe jest niebezpieczne, może się nie zmieścić w czasie. I rzeczywiście. Mam takie rozwiązanie i dostałem 6 pkt. Trochę jestem zawiedziony, że rozwiązanie liniowe dostaje TLE. To chyba nowość. Jak dla mnie słabe. Potyczki mikrooptymalizacyjne.

Wzorcowe rozwiązanie jest właśnie napisane na czas lepszy niż O(N). Brawa dla tych, którzy to zauważyli. Ale na dywizjon B takie cuda...

Żeby było bardziej przykro - niektóre testy niby max (100mln, pełny zakres) przechodzą (8a w 5 sekund), a inne nie. Pewnie kwestia dostępu do pamięci w zależności od przekroju danych.

To też jest chyba "dobre" rozwiązanie :)

byte ac1[M];
int ac[M];

rep2(i, istart, istop - 1) {
int e = myGetElem(i);
ac1[e]++;
if (ac1[e] == 0) {
ac[e]++;
}
}
rep(j, M) {
ac[j] = 256 * ac[j] + ac1[j];
}

Minimalizujemy wykorzystanie pamięci poprzez zliczanie w bajtach zamiast w słowach. 4 razy mniej pamięci, zmieści się w cache'u. W skrajnych tylko przypadkach (wielokrotność 256 wystąpień) sięgamy do licznika w intach. Daje zysk czasowy ok. 25%. Przeszłoby przez sito.

Warto przeczytać wątek, o którym chce się dyskutować...

Trzeba się cieszyć, że się przeszło niektóre testy "niby max", a nie smucić!

Zadania na potyczkach przeważnie polegają na wymyśleniu rozwiązania w dobrej złożoności. A że rozwiązania prawie-optymalne czasem są na granicy, to już inna sprawa. Zgadzam się, że lepiej, gdy mikrooptymalizacje nie mają znaczenia. Tu jednak (prawie?) wszyscy z tą samą złożonością dostali 6 punktów, więc nie jest źle.

W zadaniach rozproszonych prawie zawsze wymagamy rozwiązania szybszego niż O(N). Wprowadzenie do takich zadań oraz przykłady można znaleźć na stronie potyczek: https://potyczki.mimuw.edu.pl/l/36/

Ciekawy pomysł z przyśpieszeniem. Może nawet jeszcze szybciej będzie: if(++ac1[e] == 0) ac[e]++;

"Trochę jestem zawiedziony, że rozwiązanie liniowe dostaje TLE. To chyba nowość. Jak dla mnie słabe. Potyczki mikrooptymalizacyjne.

Wzorcowe rozwiązanie jest właśnie napisane na czas lepszy niż O(N). Brawa dla tych, którzy to zauważyli. Ale na dywizjon B takie cuda..." - nie bez kozery ta runda nazywa się ROZPROSZONA

No dobra, macie rację. Ale trochę przeceniliście moją inteligencję, każąc mi się wszystkiego domyślać samemu. Począwszy od tego, że opisy rozwiązań nie były powątkowane po zadaniach i pochowane pod dziwnymi tytułami. Teraz już rozumiem, że walka z kubełkami była słuszna, a rozwiązanie w pewnym sensie lepsze od liniowego (ze współczynnikiem <1) nie jest znowu jakąś magią.

Do czego doszedłem (za późno)? Jeżeli mamy w planie policzyć inwersje pomiędzy przedziałami A i B, a martwimy się, że to potrwa za długo. To zróbmy tak: rozbijmy każdy z tych przedziałów na połówki i wykonajmy 4 podzadania: policzmy inwersje pomiędzy A1-B1, A1-B2, A2-B1 i A2-B2. To pozwoli skrócić czas o 50%, dzięki użyciu 4 równoległych maszyn. Jest to odpowiedź na pytanie, jak rozwiązać zadanie nie czytając wszystkiego w jednym nodzie.

To prawda, dobrze o tym myślisz. Analogicznie ozwiązanie z 14 częściami powinno być już warte 10 pkt. Najwyraźniej zadanie było w Twoim zasięgu tylko po prostu nie byłeś przygotowany na rozproszony format. Powodzenia w następnych zadaniach takiego typu :) (o ile jeszcze będzie jakakolwiek okazja do ich robienia, bo coś gorszy okres rozproszone przeżywają :<)

Nice compilation here! Thnx for sharing.

The compilation code was very helpful. Please keep helping like this in future too https://www.telldunkin.one/

This is a really awesome and helpful article for me. I really appreciate your work for providing such useful information, thank you so much!
https://uvairpurifierltd.com/product/uv-air-sterilizer/