Ja inkrementowałem 7 map (7, bo było 7 możliwości podciągów zbalansowanych: zawierających tylko litery kolejno: a, b, c, ab, bc, ca i abc). Indeksem był balans pomiędzy literami zliczanymi przez daną mapę. Jednoliterowe mapy były 0-wymiarowe (1 element), dwuliterowe - jednowymiarowe (różnice ilości wystąpień tych dwóch liter), a trzyliterowa - dwuwymiarowa (2 z 3 indeksów map dwuliterowych). Jak wystąpiła litera nie zliczana przez daną mapę i na koniec, zliczałem dla każdego indeksu wartości v*(v-1)/2 z map i je czyściłem (gdybym miał unordered_map to też by mi się wywaliło na teście 9i). Dla abc konieczna była mapa, bo przestrzeń indeksów była O(n^2), co by się nie zmieściło w pamięci (natomiast różnych indeksów było max n).

Teraz widzę że zamiast czyścić mapy można było użyć nieużywanego wymiaru do zmiany koszyka i zliczać tylko na koniec.

Przy okazji: rozwiązania zniknęły :(

"wzorcówka"? nie widziałem nigdzie żadnego oficjalnego rozwiązania, więc jak na razie chyba ciężko jakieś konkretne nazwać wzorcowym.

Ja robię tak, że robię DP[b-a][c-a] => liczba stringów kończących się na aktualnej pozycji, które mają liczby a,b,c takie, że te różnice są jakie są. Wtedy DP jest mapą z offsetem pomiędzy "logicznymi" a "fizycznymi" kluczami, żeby móc np. przesunąć wszystko o (-1, -1) jak wejdzie nowe a.

Nie wiem czy warto zakładać nowy temat, więc może zapytam tu: jak wygląda rozwiązanie z unordered_map? To jest wzorcówka czy są inne podejścia?

> Problemem jest niewłaściwe używanie unordered_mapy, a dokładniej metody clear(). ...
O, dziękuję. Faktycznie o tym nie wiedziałem, a sprawdziłem, że w moim przypadku wystarczyło po wywołaniu clear() dodać rehash(2), żeby rozwiązać problem z zba9i. Chociaż równie dobrze i prościej można było zamienić unordered_map na map, chyba też by to przeszło.

> Obstawiam, że problemem może być słaba funkcja haszująca generująca wiele kolizji.

Jest to możliwy powód, jednak w ramach dzielenia się wiedzą zdradzę, że nie o to chodziło w większości rozwiązań, które miały problemy na tym teście. Problemem jest niewłaściwe używanie unordered_mapy, a dokładniej metody clear(). Usuwa ona co prawda pary (klucz, wartość) z hashmapy, jednak nie zmniejsza zarezerwowanej pamięci, tzn. bucket_count() pozostaje bez zmian.

Dokładniej mówiąc, jeśli najpierw umieścimy w unordered_mapie dużo kluczy, a następnie dużo razy wyczyścimy ją w niewłaściwy sposób (tzn. jedynie używając metody clear()), to za każdym razem czas czyszczenia zależny będzie od rozmiaru zarezerwowanej pamięci, czyli liniowy, przez co całe rozwiązanie będzie kwadratowe.

Edit: jednak SIP działa świetnie. Polecam każdemu, kto jest fanem dobrych, sprawdzonych rozwiązań zamiast kodu napisanego przez siebie na kolanie.

https://github.com/varqox/sip

Kwestia techniczne? Chyba powinno być "kwestie"?

Zainstalowałem świeżą wersję Google Chrome i cały formularz działą, także to nie wygląda na problem po stronie serwera.

> W rankingu nie ma informacji o tym, kto na jakich testach się wywalił...

No szkoda, ale są rozwiązania, można sobie sprawdzić. W szczególności wszystkie rozwiązania które dostały 9 punktów były oparte na unordered_map i wywalały się na teście 9i.

W rankingu nie ma informacji o tym, kto na jakich testach się wywalił...

Obstawiam, że problemem może być słaba funkcja haszująca generująca wiele kolizji. Standardowe funkcje hashujące zaimplementowane w gcc std::hash są słabe (powiedziałbym nawet mocniej, że błędne).

"How to pick a hash function" https://sortingsearching.com/2020/05/21/hashing.html

Ktoś doszedł czemu większość rozwiązań opartych na unordered_map wywalała się na teście 9i ('a'*150k+'b'*150k)?

To zależy, prosta pętla w shellu przeważnie wystarcza. Tu jest ciekawy plugin dla VSCode: https://codeforces.com/blog/entry/71386 Działa bardzo fajnie. A samemu sobie dopisałem to: https://github.com/tomekjarosik/inout_tester

Potwierdzam, jakby ktoś chciał sprawdzić sobie te testy przed odsłonięciem

Zgadza się. Na Potyczkach, zgodnie z tradycją (w przeciwieństwie do Olimpiady Informatycznej) oceniamy rozwiązania w skali od 0 do 10 punktów.

Innymi odstępstwami jest gwarancja, że testy podzielone są na 10 niezależnych grup (wartych po jednym punkcie), fakt, że po przekroczeniu połowy czasu nie zaczynamy zmniejszać liczby przyznanych punktów za grupę oraz podawanie w treściach limitów czasowych.

Przez dłuższą chwilę myślałem, że odsłoniony wynik 10 oznacza, że mam gdzieś błąd. Okazuje się jednak, że 10 to maksymalna liczba punktów którą można uzyskać. Cytując regulamin:

> nadesłany program jest kompilowany i uruchamiany na 10 grupach danych testowych; na każdą grupę składa się co najmniej jeden test,

> za każdą grupę, w której zostały zaliczone wszystkie testy, program otrzymuje 1 punkt.