Regulamin działu


Zachęcamy do dyskusji na temat zadań z konkursu Zadanie Tygodnia. Można dzielić się uwagami i np. testami do zadań. Pamiętaj, aby nie publikować metody ani samego rozwiązania zadania z bieżącej rundy.



Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 3 ] 
Bokserzy [Runda 20] - rozwiązanie 
Autor Wiadomość
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 7 gru 2010, o 21:24
Posty: 24
Post Bokserzy [Runda 20] - rozwiązanie
Czy ktoś byłby tak uprzejmy i naświetlił sposób rozwiązania tego zadania?


26 maja 2011, o 10:58
Zobacz profil
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post Re: Bokserzy [Runda 20] - rozwiązanie
Moje rozwiązanie:

Mamy sobie strukturę
Kod:
const int st=1<<18;
vector<int> w[2*st+5];
scanf("%d",&n);
for(int i=0;i<n;++i){
    scanf("%d",&c[i]);
    for(int j=st+i;j;j/=2)w[j].push_back(c[i]);
}
for(int i=0;i<2*st+3;++i)sort(w[i].begin(),w[i].end());
Jest to drzewo, które w w[1] trzyma całą tablicę, w w[2] trzyma pierwszą połowę, w w[3] drugą połowę, w w[4] pierwszą ćwiartkę itd. i to wszystko posortowane. Ma to zapewne jakąś nazwę, ale jej nie znam.
Mając taką strukturę, możemy na każde zapytanie odpowiedzieć w O(log^2n) - dla każdego jak największego przedziału zawartego w zadanym * używamy wyszukiwania binarnego.
* czyli np. dla (4,9) przeglądamy (4,7) i (8,9)


Zalążek rozwiązania, na które wpadłem później:
Trzymać posortowane początki przedziałów z zapytań. Przeglądnąć po kolei wszystkich zawodników. Jeśli natrafiamy na początek jakiegoś przedziału, to dla tego zapytania (którego początkiem jest ten, przy którym jesteśmy) zapisujemy ilość remisujących i przegrywających do tego miejsca. To samo z końcami tyle że idąc od tyłu. Jak to zrealizować (to znajdowanie wyników - ilości remisujących i przegrywających)? Nie wiem. Pewnie drzewko jakieś, set może. Nie zastanawiałem się nad tym.

PS.: Może wrzucajmy pytania o rozwiązania zadań w dziale "ciekawe rozwiązania". Może i nie zawsze rozwiązanie będzie "ciekawe", ale zwiększy to porządek na forum - chyba lepiej mieć wszystkie opisy rozwiązań w jednym miejscu.


26 maja 2011, o 17:39
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 7 gru 2010, o 21:24
Posty: 24
Post Re: Bokserzy [Runda 20] - rozwiązanie
Bardzo sprytne.


27 maja 2011, o 23:34
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 3 ] 


Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 1 gość


Nie możesz rozpoczynać nowych wątków
Nie możesz odpowiadać w wątkach
Nie możesz edytować swoich postów
Nie możesz usuwać swoich postów
Nie możesz dodawać załączników

Skocz do:  
cron


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group. Forum style based on STSoftware Hestia.
Przyjazne użytkownikom polskie wsparcie phpBB3 - phpBB3.PL