Zadanie Zespoły 2, Letni obóz treningowy OIJ, przed EJOI 2021

Question

Mam problem z takim zdaniem: https://sio2.mimuw.edu.pl/c/oij15-wiekuisty-oboz/p/zes/

Wymyśliłem jedynie bruta w O(N * Q + N lg N), czy coś takiego, że pokażdej zmianie mam na secie liczby jakie mam, i zachłanie od tyłu / przodu dziele je do jednego zespołu. W sensie jeśli | A[i] - A[i+1]| <= 1 -> przydzielam do danego zespołu. Tylko ta złożonność nie jest dobra. No i wsumie tu stanołem jak robić updaty, mam jedno spostrzerzenie, jeśli robimy updata, to liczba zespołow po updacie, nie będzie różnić się o więcej niż jeden, niż przed updatem. Ale nie wiem czy to coś zmienia i czy mogę jakoś to wykorzystać.

Jak ma ktoś jakiś pomysł, to z góry dziękuję!

Answer 1

Wygląda na drzewo przedziałowe. Załóżmy, że nie ma duplikatów. Wtedy zadanie sprowadza się do napisania struktury, która umie dodawać nowe liczy do osi liczbowej i sumować długości odcinków o długości co najmniej 1 (jeśli odcinek ma parzystą długość to trzeba dodatkowo odjąć 1). Powiedzmy, że odcinek to takie kolejne punkty w których każdy jest oddalony od kolejnego o dokładnie 1, a długość odcinka to liczba punktów - 1. Czyli trzeba wymyślić tylko jak napisać funkcję insert

Comments

a co z usuwaniem?, w sensie forma zawodnika sie zmienia, i starą trzeba usunąć i dodać nową.

---

Jak wymyslisz jak obliczać wynik dla podrzewa na podstawie wyniku dla lewego i prawego poddrzewa to usuwanie/dodawanie sprowadzi się tylko do odpowiedniej modyfikacji liścia i uruchomienia tego wymyśloneo algorytmu

---

To będzie podobne do liczenia spójnego podciągu o maksymalnej sumie drzewem

---

około 10h klepania dzisiaj, ale wkońcu wleciała 100pkt(całkiem możliwe, że przez moją złą implementację) ........

Ogólnie sam pomysł na to zadanie nie jest stosunkowo trudny, ale ciężko to zaklepać, trzeba napisać 2 lub 3 (zależy jak napiszesz) drzewa przedziałowe + kompresja z wczytania z wejścia. Mój kod ma około 320 linii.... Chyba, że istnieje inne rozwiązanie niż moje. Moje ma O((N+Q) * lg (N+Q)).

Opiszę, jeszcze krótko szczegóły jak by ktoś się kiedyś męczył, lecimy.

Całe spostrzerzenie, do tego zadania polega na tym, że jak będziemy trzymać grupy z zawodników. Każda grupa musi zawierać zawodników X,X+1,X+2,X+3,X+4.....Y i żeby każda siła zawodnika była maksymalnie w jednej grupie. I do wyniku dodajemy Size_danej_grupy / 2 (zaokrąglając w dół). Np dla dwóch grup, gdzie są zawodnicy o takich siłach:

Liczebność grup może być dowolnego rozmiaru.

Musimy mieć strukturę, która umożliwi nam operacje:

1 - Dodaj zawodnika o danej sile

2 - Usuń zawodnika o danej sile

3 - Odpowiedz ile jest zespołów

Jakie mamy wogóle opcje do zastanowienia się: 1 - set, drzewo przedziałowe, jakieś statystyki. z Setem ciężko będzie coś zrobić, więc połączmy drzewo przedziałowe + statystyki. Problemem jest to, że umiejętności zawodników moga być nawet do 10^9, więc ciężko będzie nam napisać drzewo przedziałowe. Skorzystamy z trika zwanego kompresją (patrz na:

- https://forum.pasja-informatyki.pl/580523/modyfikacja-ciagu-a-o-dlugosci-n-m-razy?show=580523#q580523

- https://forum.pasja-informatyki.pl/579464/zadanie-radiotelegraf-oboz-ilocamp?show=579464#q579464

wogóle tak sobie myślałem, że przy tym zadaniu nastąpiła zabawna sytuacja, są to dokładnie dwa te same zadania, a drugi ma 40 wizyt, a pierwszy ponad 250 wizyt. Pokazuje to samo, ale innaczej jest napisany tytuł i opis, i tak bardzo zwróciło to uwagę ludzi) wczytamy sobię wszystkie możliwe poziomy umiejętności zawodników, i dla każdej wartości (nie idxu, tylko poziomu umiejętności) przypiszemy jej idx w posortowanym vectorze. I teraz zrobimy sobie dwa drzewa przedziałowe, jedno punkt - przedział, zwykłe drzewo przedziałowe sum, umożliwiające opracje:

- Podaj sumę na przedziale [L, P]

- Zamień wartośc w punkcie G.

A drugie to drzewo przedziałowe przedział - punkt, które będzie umożliwiało operacje:

- Odczytaj w punkcie, w jakim przedziale mieści się jego grupa

- Dodaj na przedziale wartość grupy.

Z tym drzewem przedział - punkt grup trzeba uważać, bo trzeba dodać zmienną priorytet, i jak robimy querry to brać tą o największym priorytecie, na początku priorytet = 0, to po każdej operacji będziemy robili priorytet++. Bez tej zmiennej, by nie wiedział co brać w przypadku remisów.

No i trzeci vector(ja nazwałem go dp, ale z dp nie ma nic wspólnego), który mówi nam ile jest aktualnie w naszych strukturach elementów o poziomie umiejętność X, ma size, tyle ile jest elementów po kompresji.

Na początku inicjalizujemy sobie każdy element w tych drzewach. I ustawiamy wynik. I teraz jak będziemy robić kolejne operację, to będziemy nadpisywać wynik. Zajmijmy się najpierw odawaniem nowego zawodnika. Jeśli był już taki zawodnik(odczytujemy z vectora dp lub drzewa przedział - punkt sum) to zwiększamy w vecotrze dp i drzewie przedziałowym w tym punkcie o 1, pytamy się w tym punkcie, gdzie jesteśmy o początek i koniec przedziału, bierzemy sumę,  i jeśli ta suma po dodaniu jest podzielna przez 2, to wyn++ - tworzymy nowy zespół. Podobnie jest z usuwaniem jeśli w punkcie mamy >= 2 zawodników o danej mocy. Teraz zajmijmy się dodawaniem, gdy nie ma zawodnika o danej mocy, to jest trudniejsze. Mogą się zdarzyć 2 sytuacje:

1 - Nie sąsiaduje z dwoma mocami nie różniącej się o więcej niż 1, wtedy robimy praktycznie to samo co w przypadku wyżej

2 - trudniejsza sąsiaduje z dwoma mocami nie różniącej się o więcej niż 1, wtedy musimy połączyć oba przedziały w jeden i dodać wynik.

W przypadku usuwania, gdy sąsiaduje robimy podobnie, co w przypadku dodawania, gdy sąsiaduję, tylko rozdzielamy przedziały.

No i złożonność sortowanie i kompresja ma O((N+Q) * lg (N+Q)), zapytania i updaty na drzewach przedziałowych tak samo, więc cała złożonnośc to również O((N+Q) * lg (N+Q)).

Na koniec pozostaje jeszcze pytanie, czy to, że zespoły są 2 osobowe ma znaczenie, a nie mogły by być np. 3, 4, 5, 6, 20, x osobowe? Odpowiedź jest taka, że nie ma to znaczenia, to rozwiązanie działa dla dowolnej liczebności zespołów. Podejrzewam, że liczebność zespołu jest 2, żeby była łatwiejsza arytmetyka. Przy większej liczebności niż 2, trzeba było by uważać na przypadki brzegowe.

Jest jeszcze jedna obserwacja, jaką miałem, ogólnie w moim pomyśle bezpośrednio się nie przydała, ale po każdym updacie(usunięcie / dodaniu) różnica między wynikiem poprzednim(przed updatem) nie zmieni się o więcej niż 1. Może być jeden więcej / mniej, ale wydaje mi się, że nie zwiększy się o więcej niż 1.

Ogólnie zamiast kompresji można sobie np skorzystać z mapa / unordered_mapa / seta.

Co ciekawe, to co zrobili w tym zadaniu, to wzieli zadanie Zespoły z 2 etapu XV OIJ, w którym trzeba było brać zespoły o liczebności 3, ale nie było tam updatów, i dodali updaty i zmienili liczebność zespołów na 2.

Link do kodu: https://github.com/samek567/ZadaniaAlgorytmiczne/blob/main/EliminacjeEJOI2020_oraz_LetniObozTreningowyOIJprzedEJOI_2021/zespoly2_100pkt_na_pomysl_drzewo_przedzialowe.cpp

Używam tak vectora dp, ale z dynamikami nie ma on nic wspólnego, tylko poprostu tak jest mi łatwiej nazywać, a przechowuje on ile jest zawodników o danym poziomie umiejętności.

Jak ktoś bedzie pisał to zadanie, to polecam sobie przemyśleć dokładnie co jak ma wyglądać. I życzę cierpliwości, nie wiem, czy się opłaca siedzieć nad tym zadaniem, ale napewno warto ;)

Jeszcze raz dzięki za nakierowanie!

---

Cholera takie zadanka, fiu fiu - niezły poziom!