SPOJ - NOE

0

Witam,
Mam problem z zadaniem NOE na spoju (https://pl.spoj.pl/problems/NOE/).
W jaki sposób można zrobić to zadanie?
Próbowałem wczytywać do wektora i w trakcie wczytywania usuwać dupilikaty, ale działa to za wolno.
Podpowiecie mi coś ?
Pozdrawiam,
Jan Kowalski

0

Odpowiednio szybkie uporządkowanie elementów powinno wystarczyć.

0

przeedytowane: źle przeczytałem treść ;)
Wczytywać do wektora i usuwać duplikaty? -> O(n^2). Wrzucanie do map<> zamiast do vector daje nam O(nlogn), sensowne wykorzystanie set<>/list<> napisanie własnej hashmapy da O(n), moze się jednak wysilisz?
Ale jak chcesz gotowca to proszę:

  • wersja O(nlogn) -> liczby wrzucamy do map<int,int> i robimy:
map<int,int> liczby;
//wczytujemy liczbę x
liczby[x]++;
//a na koniec przeglądamy sobie mapę iteratorem i szukamy który element ma wartość 1
map<int,int>::iterator mapIterator;
for(mapIterator=liczby.begin(); mapIterator!=liczby.end(); mapIterator++)
  if(mapIterator->second==1){
    printf("%d",mapIterator->first);
    break;
  }
  • druga wersja O(nlogn), ale przypuszczalnie szybsza -> robimy sobie set<int> na liczby które "padły" i własną hashmape na zliczanie.
  • wersja O(n) -> tak jak wyżej, ale liczby trzymamy w list<int> a nie w set<int>, minus jest taki ze będziemy mieli O(2n), ale nie marnujemy czasu na sprawdzanie czy liczba jest unikalna przy wkładaniu do zbioru. Biorąc pod uwagę fakt że najpewniej O(2n) będzie mniejsze od O(nlogn) to to rozwiązanie będzie najszybsze.

Wersje szybsze wymagają własnej implementacji hashmapy z racji tego że max liczba to 109 a takiej tablicy na zliczanie nie zrobimy. Jednak skoro samych liczb ma byc max 5*105 to możemy sobie zrobić tablicę powiedzmy 10^6 i napisać odpowiednia funkcje hashującą. Optymistycznie/średnio da nam to O(1) na dostęp do danych (pesymistycznie oczywiście O(n)).

0

Wystarczy że się zrobi tablicę bitów.

0

Rozwiązanie O(n log n) wystarcza, sam sprawdzałem.

Rozwiązanie O(n) można uzyskać, jak mi się zdaje, wykorzystując modyfikację Radix sort. Można np. zliczać, ile jest zwierząt o numerach modulo M=1000, tam, gdzie liczba zwierząt będzie nieparzysta, tam jest gość nie-do-pary. I rekurencyjnie dalej.

@_13th_Dragon: 109 bitów daje pewniak na przekroczenie limitu czasu (bo trzeba będzie w końcowym etapie przejrzeć całą tablicę w poszukiwaniu pojedynczego osobnika, a w najgorszym przypadku należy przejrzeć wszystkie możliwe z 109 gatunków).
Edit: wiem, można zrobić sobie tablicę, w której zapisać wszystkie wystąpienia gatunku. Jednak wciąż w czasie działania programu tablica bitów zostanie wypełniona losowymi wartościami, a zerowanie potrwa i tak co najmniej 109 operacji (a dokładniej: nie jest inicjalizowana, a jeśli jest, to i tak zajmie to 109 operacji).

0

:) 71 znaków, 0.66 sekundy :)
myślę, że to wystarczająca podpowiedź

0

Nie lubię takich zadań, w których chodzi głównie o szybkość IO. To samo rozwiązanie z gets() dostaje 0.42 s, a z cin jest TLE (rozwiązanie mam chyba najprostsze z możliwych, złożoność O(n), złożoność pamięciowa (O(1)).

0

@Zjarek a ustawiłeś chociaż sync_with_stdio dla tego strumienia? Poza tym nie od dziś wiadomo że strumienie się do takich zadań nie nadają i już.

0
set<unsigned int> unpairedAnimals[HashValueCount];

inline void addUnpairedAnimal(unsigned int id)
{
    set<unsigned int> &group= unpairedAnimals[hashValue(id)];
    set<unsigned int>::iterator it = group.lower_bound(id);
    if (it != group.end() && *it == id) { //pair found so remove it from unpaired animals
        group.erase(it,it);
    } else {
        group.insert(it, id);
    }
}

Cały cymes rozchodzi się o właściwe dobranie funkcji hash'ującej, nie robiłbym naiwnego modulo potęga dwójki, bo prawie na 100% jeden z zestawów danych testowych ma zwierzaki o identyfikatorach o jednakowej wartości modulo jakaś potęga dwójki (ja bym tak zrobił tworząc zestawy testujące).

0

Po kiego hashować skoro w pamięci zmieści się mapa bitowa.
Przy mapie bitowej o ile ją mądrze skonstruować można mieć numer zwierzęcia bez pary natychmiast po odczytaniu.

1 użytkowników online, w tym zalogowanych: 0, gości: 1