Witam.
Robię kurs main2 już jakiś czas.
Zaczynam się uczyć algorytmów, i mam do Was pytanie.
Jaki wzór, jaki algorytm powinien być zastosowany w zadaniu https://main2.edu.pl/c/konkurs-podstaw-algorytmiki/p/sma/ ?
Bo przy moich próbach, i próba użycia tzw. "gąsienicy" spełza na niczym.
Serdecznie dziękuje za wszelakie rady, pozdrawiam!
0
0
ponad 5 lat a nigdy w pracy nie musialem robic takich zadan...
Wydaje mi sie, ze najlatwiej byloby tu zastosowac liste z poprzednikiem i nastepnikiem
Wtedy idziesz po prostu po wierzcholkach, i idziesz w lewo az nie znajdziesz duplikatu, a pozniej w prawo. Jezeli jest wiecej niz dwa obiekty (pierwszy to zawsze wierzcholek) to masz kombinacje
Do znajdywania duplikatu uzyj std::map (podpowiedz, uzyj <int, int> gdzie pierwszy int bedzie liczba, a drugi ile razy wystapil, lub uzyj metody by sprawdzic czy istnieje w mapie (chyba exist, sprawdz w dokumentacji)). Po sprawdzaniu czysc mape
nie powinno to wziac wiecej niz 10 MB pamieci. Zlozonosc obliczeniowa nie licze, ale pewnie bedzie okolo n do kwadratu, takze zapewne istnieje lepsze rozwiazanie
0
Problemem jest to że zadanie rozwiązujesz za wolno czy że w ogóle nie jesteś w stanie go rozwiązać?
1
Crezer12 napisał(a):
Witam.
Robię kurs main2 już jakiś czas.
Zaczynam się uczyć algorytmów, i mam do Was pytanie.
Jaki wzór, jaki algorytm powinien być zastosowany w zadaniu https://main2.edu.pl/c/konkurs-podstaw-algorytmiki/p/sma/ ?
Bo przy moich próbach, i próba użycia tzw. "gąsienicy" spełza na niczym.
Serdecznie dziękuje za wszelakie rady, pozdrawiam!
Gąsienica jest dobrym tropem. Ale połącz ją jeszcze z std::set.
Dla przykładu [1, 3, 2, 2, 3]
Zaczynasz od b = 0, e = 0, S = std::set(), result = 0;
1 iteracja: rozważasz 1 i S (pusty). result += (1 + 0), e += 1, S += {1}. Dlaczego, bo za każda rozważana liczbę dodajesz 1 oraz liczbę elementów w zbiorze (przed dodaniem obecnego elementu).
2 iteracja: rozważasz 3 i S = {1}. result += (1 + S.size), e += 1, S+= {3}.
3 iteracja: rozważasz 2, S = {1, 3}, result += (1 + S.size), e += 1, S += {2}
4 iteracja: rozważasz 2, S = {1, 3, 2}, result += {1} Dlaczego nie dodalem rozmiaru S? Bo 2 znajduje się już w zbiorze. S \ {1}, tj odejmuje 1 od zbiór, b += 1. Czyli nasza gąsieniczka.
5 iteracja, rozważasz 2, S = {3, 2} result += 0 ** dlaczego zero? bo 2 z pod indeksu 4 już rozważyłem**, ** dlaczego nie dodałem znowu rozmiaru zbioru S? bo 2 nadal jest w S**, b+= 1, S \ {3}
6 iteracja, rozważasz 2, S = {2}. result += 0, S \ {2} b += 1
7 iteracja, rozważasz 2, S = {}, result += S.size ( =0 ), teraz moge isc koncem e do przodu, bo wreszcie w S nie ma liczy z pod indeksu e S += {2}, e += 1
8 iteracja, rozważasz 3, S = {2}, result += 1 + S.size (bo 3 nie ma zbiorze S).
Doszliśmy e do konca, możemy przerwać.
Wychodzi 9, tak jak w przykładzie.
Zasada działania? Będąc na pozycji i, wiemy, że liczba z pod pozycji i dodaje 1, bo sama jest unikalna, oraz rozmiar zbioru po lewej od i składającego się z unikalnych liczb różnych od i. Zbiór po lewej stronie musi "stykać się" z i, więc można go ograniczać tylko z początku. Dlaczego dodajemy rozmiar zbioru? Bo jeżeli po lewej jest n elementów, to i może stworzyć unikalny zbiór o rozmiarze od 2 do n (zbiór jednoelementowy składający się z samego i uwzględniłem we wcześniejszym kroku).
Złożoność O(n logn) przy uzyciu std::set, O(n * h) przy uzyciu unordered_set, gdzie h niech bedzie srednim narzutem zwiazanym z rozwiazywaniem kolizji (prawdopodobnie zamortyzuje się to do O(n)).