Traffic light - codeforces

Question

Hej,

Rozwiązuję to zadanie : https://codeforces.com/problemset/problem/1744/C. Ma ktoś może pomysł na rozwiązanie tego? Moje rozwiązanie niestety jest za wolne.

Answer 1

Sposobów na rozwiązanie tego zadania jest cała masa, między innymi: binary search, sumy prefiksowe, set, drzewo przedziałowe, gąsienica.

Najprostszy jest faktycznie chyba ten bin search. Robisz sobie taki vector statystyk. Na jakich idx-ach w ciągu wejściowym jest kolor zielony. I teraz: z każdego pola, które ma taki sam kolor jak kolor pola startowego zakładasz, że z niego chcesz przejść na pierwsze pole zielone. Masz dwie opcje, albo te opcje jest na prawo(albo na tej samej co sprawdzasz) od Ciebie w ciągu, to wtedy szukasz binarnie pierwszego idx-u >= x, albo jest na lewo(przechodzisz wszystkie na prawo i wracasz do poczatku), to wtedy bierzesz odległośc do wystapienia[0].

Na koniec bierzesz max z tych wszystkich kandydatów startowych. -> O(N lg N), ze względu na bin searcha.

Btw. Jak to zrobisz, to zauważ, że łatwo możesz przyśpieszyć to do liniówki gąsienicą z kosztem zamortyzowanym.

Jak byś czegoś nie rozumiał / miał jakieś pytania to śmiało pytaj!