Z kamyczkami 400.10, coś dziwny ten test - przeciętnie mi wychodzi koło 550

Z kamyczkami: 755.2

To jeszcze benchmark na losowym teście z grupy 8 (z kamyczkami): http://students.mimuw.edu.pl/~ms360974/stuff/pa/2018/gra-with-stones.in

Ja z kamyczkami: 742.9

333.3

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]++;

Potwierdzam mały test.

To jako mniej błyskotliwy mogę potwierdzić.

Out jest dobry, więc pewnie ktoś potwierdzi.

To ja dla tych mniej błyskotliwych wrzucę mniejszy teścik (n=1000)
http://students.mimuw.edu.pl/~wn341489/Ryksmall.in
http://students.mimuw.edu.pl/~wn341489/Ryksmall.out
Potwierdzi ktoś?

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.

Ja 364.6

Gdzie są te zapowiadane omówienia? Nie widzę :(

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.

Potwierdzam pełnego hasza! :)

Ja 650.7 :/